Η επιχειρησιακή έρευνα και η κυρτή βελτιστοποίηση είναι ένα πεδίο εφαρμοσμένων μαθηματικών που έχει βρει πολλές εμπορικές εφαρμογές με την πάροδο των ετών. Καθώς η υπολογιστική ισχύς έγινε πιο προσιτή και ευρέως διαθέσιμη, οι ερευνητές άρχισαν να δημιουργούν ολοένα και πιο εξελιγμένους αλγόριθμους βελτιστοποίησης για να τους βοηθήσουν να λάβουν καλύτερες αποφάσεις. Σήμερα, οι εφαρμογές που βασίζονται σε λειτουργίες ερευνούν τα πάντα, από τη δρομολόγηση στην παγκόσμια εφοδιαστική έως την παραγωγή ηλεκτρισμού εξομάλυνση της βιομηχανίας ενέργειας.

Καθώς η υποκείμενη τεχνολογία μεγάλωσε στην πολυπλοκότητα, δημιουργήθηκε ένα νέο σύνολο εργαλείων για να βοηθήσει τους ερευνητές και τους προγραμματιστές να εργαστούν πιο παραγωγικά. Αυτά τα εργαλεία, όπως τα AMPL, CVXPY και PuLP, επιτρέπουν στους προγραμματιστές να ορίζουν γρήγορα, να δημιουργούν και να εκτελούν αλγόριθμους βελτιστοποίησης και διασύνδεση με μια μεγάλη ποικιλία λύσεων.

Ωστόσο, ενώ οι τεχνολογίες βελτιστοποίησης και οι επιχειρηματικές ανάγκες συνεχίζουν να αυξάνονται με την πολυπλοκότητα, τα περισσότερα από αυτά τα εργαλεία παρέμειναν λίγο πολύ τα ίδια και δεν εξελίχθηκαν αρκετά γρήγορα για να καλύψουν τις ανάγκες της βιομηχανίας. Ως αποτέλεσμα, η ανάπτυξη, η διαχείριση, ο εντοπισμός σφαλμάτων και ο συντονισμός αυτών των αλγορίθμων συχνά απαιτούν μεγάλη ποσότητα γνωστικών γενικών εξόδων, ειδικά σε ένα ταχέως επιχειρηματικό περιβάλλον.

Σήμερα, θα ήθελα να παρουσιάσω HorusLP , προς το Βιβλιοθήκη βελτιστοποίησης Python που βοηθά στην αρχιτεκτονική των ροών εργασίας ανάπτυξης αλγορίθμων. Θα μιλήσουμε για τα προβλήματα που έχει σχεδιαστεί για να λύσει το εργαλείο και, στη συνέχεια, θα παρέχει μια γρήγορη επισκόπηση της βιβλιοθήκης Python και θα δημιουργήσουμε μερικά παραδείγματα αλγορίθμων βελτιστοποίησης.

Προβλήματα που αντιμετωπίζουν οι προγραμματιστές αλγορίθμου βελτιστοποίησης

Ένα από τα πολυετή προβλήματα που αντιμετωπίζουν οι περισσότεροι προγραμματιστές είναι η ισορροπία μεταξύ της δημιουργίας ενός διατηρήσιμου, αποτελεσματικού, ιδιωματικού λογισμικού και της παράδοσης ενός προϊόντος εντός των χρονικών περιορισμών του έργου. Είτε εργάζεστε σε μια εφαρμογή που βασίζεται σε πρόγραμμα περιήγησης, σε ένα διαδικτυακό API ή σε μια μικροεπηρεσία ελέγχου ταυτότητας χρήστη, υπάρχει συχνά μια ανταλλαγή μεταξύ του «σωστού» και του «γρήγορου» τρόπου επίτευξης των στόχων σας. Αυτή η εγγενής ανταλλαγή γίνεται πιο εμφανής καθώς αυξάνεται η πολυπλοκότητα των προϊόντων.

Στους περισσότερους κλάδους, ένας προγραμματιστής μπορεί να ανακουφίσει αυτό το πρόβλημα επιλέγοντας ένα πλαίσιο ή βιβλιοθήκη που βοηθά στην αρχιτεκτονική. Στο front-end που βλέπει στον ιστό, πολλοί προγραμματιστές επιλέγουν React ή Angular. Στον κόσμο της ανάπτυξης API, οι μηχανικοί λογισμικού μπορούν να επιλέξουν μεταξύ άλλων Django, ASP.NET MVC ή Play. Ωστόσο, όσον αφορά τον ταπεινό προγραμματιστή αλγορίθμου βελτιστοποίησης, υπάρχουν πολύ λίγα εργαλεία αρχιτεκτονικής που βοηθούν στη διαχείριση της αρχιτεκτονικής πολυπλοκότητας. Ο προγραμματιστής αφήνεται να διαχειρίζεται μόνοι του μεταβλητές, περιορισμούς και διάφορους στόχους. Επιπλέον, οι αλγόριθμοι έρευνας λειτουργίας είναι γενικά δύσκολο να εντοπιστούν, επιδεινώνοντας το πρόβλημα.

Ο κύριος σκοπός του HorusLP είναι να παρέχει ένα αρχιτεκτονικό πλαίσιο για την ανάπτυξη αλγορίθμων βελτιστοποίησης. Παρέχοντας δομική συνέπεια, το πλαίσιο διευκολύνει την οργάνωση και επιτρέπει στους προγραμματιστές να επικεντρώνονται σε αυτό που κάνουν καλύτερα: δημιουργία αλγορίθμων.

Τυπικές προκλήσεις ροής εργασίας βελτιστοποίησης

Υπάρχουν πολλές σημαντικές πηγές πολυπλοκότητας κατά την ανάπτυξη αλγορίθμων Ή:

Πολυπλοκότητα από μεταβλητές

• Οι μεταβλητές συχνά πρέπει να προστεθούν για να καλύψουν πρόσθετες επιχειρηματικές απαιτήσεις και δεν υπάρχει εύκολος τρόπος να τις παρακολουθήσετε για χρήση σε ορισμούς μοντέλων και αναφορές αργότερα.
• Οι σχετικές μεταβλητές πρέπει να ομαδοποιηθούν και να παρακολουθούνται και δεν υπάρχει προφανής τρόπος για τη διαχείρισή τους.

Πολυπλοκότητα από περιορισμούς

• Οι περιορισμοί πρέπει να προστεθούν και να αφαιρεθούν για να υποστηρίξουν διάφορα σενάρια και για την εκτέλεση εντοπισμού σφαλμάτων, αλλά δεν υπάρχει προφανές μέρος για να προσθέσετε ή να αφαιρέσετε περιορισμούς.
• Οι περιορισμοί συχνά σχετίζονται / εξαρτώνται ο ένας από τον άλλο και δεν υπάρχει φυσικός τρόπος να εκφράσουν τις σχέσεις τους.

Πολυπλοκότητα από τους στόχους

• Οι αντικειμενικές εκφράσεις μπορούν να γίνουν δύσκολες εάν έχουν πολλά στοιχεία. Αυτό μπορεί να επιδεινωθεί εάν τα διάφορα συστατικά σταθμιστούν και τα βάρη πρέπει να προσαρμοστούν με βάση τις επιχειρηματικές απαιτήσεις.

Πολυπλοκότητα από τον εντοπισμό σφαλμάτων

• Δεν υπάρχει εύκολος τρόπος να δείτε τα αποτελέσματα του μοντέλου κατά τη διάρκεια της ανάπτυξης. Ένας προγραμματιστής πρέπει να εκτυπώσει ρητά νέες μεταβλητές και τιμές περιορισμού για να δει τα αποτελέσματα. Αυτό οδηγεί σε διπλότυπο κώδικα και πιο αργή ανάπτυξη.
• Κατά την προσθήκη ενός περιορισμού προκαλεί το μοντέλο να είναι ανέφικτο, μπορεί να μην είναι προφανές γιατί ο περιορισμός προκάλεσε το μοντέλο να γίνει ανέφικτο. Συνήθως, οι προγραμματιστές πρέπει να πάρουν διάφορους περιορισμούς και να αναζητήσουν την ασυμβατότητα μέσω δοκιμής και σφάλματος

Η HorusLP ελπίζει να καταστήσει αυτές τις προκλήσεις πιο εύχρηστες παρέχοντας δομή, εργαλεία, βέλτιστες πρακτικές για τη βελτίωση της παραγωγικότητας του προγραμματιστή και τη συντήρηση των προϊόντων.

Tutorial HorusLP: Αλγόριθμος βελτιστοποίησης και επισκόπηση του API

Χωρίς άλλη παραλλαγή, ας δούμε και να δούμε τι μπορεί να κάνει η βιβλιοθήκη HorusLP για εσάς!

Δομή φακέλου έργου φόρμες των windows

Επειδή το HorusLP βασίζεται σε Python και PuLP, θα θέλαμε να τα εγκαταστήσουμε χρησιμοποιώντας pip. Εκτελέστε τα ακόλουθα στη γραμμή εντολών σας:

Pip install horuslp pulp

Μόλις ολοκληρωθεί η εγκατάσταση, ας προχωρήσουμε και ανοίξτε ένα αρχείο Python. Θα εφαρμόσουμε το πρόβλημα σακιδίων από το δικό μου προηγούμενο άρθρο σχετικά με την έρευνα λειτουργίας .

Η βιβλιοθήκη HorusLP διαθέτει ένα πολύ απλό δηλωτικό API και πολύ λίγο boilerplate. Ας ξεκινήσουμε εισάγοντας τις απαραίτητες τάξεις και μεταβλητές:

from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

Μόλις εισαγάγουμε όλες τις μεταβλητές, ας καθορίσουμε τις μεταβλητές που χρειαζόμαστε για αυτό το πρόβλημα. Το κάνουμε αυτό δημιουργώντας μια υποκατηγορία διαχειριστή μεταβλητών και συμπληρώνοντάς την με τις δυαδικές μεταβλητές:

class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

Τώρα που ορίζονται οι μεταβλητές, ας καθορίσουμε τους περιορισμούς. Δημιουργούμε περιορισμούς με την υποκατηγορία της κύριας κατηγορίας περιορισμών και την εφαρμογή της λειτουργίας 'καθορισμός'.

class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Στη συνάρτηση καθορισμού, μπορείτε να ζητήσετε τις απαιτούμενες μεταβλητές κατά όνομα. Το πλαίσιο θα εντοπίσει τη μεταβλητή στο διαχειριστή μεταβλητών και θα τη μεταφέρει στη λειτουργία καθορισμού.

Μετά την εφαρμογή του περιορισμού, μπορούμε να υλοποιήσουμε τον στόχο. Δεδομένου ότι είναι ένας απλός στόχος, θα χρησιμοποιήσουμε ObjectiveComponent:

class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

Η λειτουργία καθορισμού έχει μια πολύ παρόμοια ρύθμιση με τη συνάρτηση καθορισμού της κλάσης περιορισμού. Ωστόσο, αντί να επιστρέψουμε μια έκφραση περιορισμού, επιστρέφουμε μια συγγενή έκφραση.

Τώρα που καθορίζονται οι μεταβλητές, οι περιορισμοί και οι στόχοι, ας ορίσουμε το μοντέλο:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

Για να δημιουργήσουμε το μοντέλο, δημιουργούμε μια κλάση που είναι υποκατηγορία της κλάσης Πρόβλημα και καθορίζουμε τις μεταβλητές, τους στόχους, τους περιορισμούς και την έννοια. Με το καθορισμένο πρόβλημα, μπορούμε να λύσουμε το πρόβλημα:

prob = KnapsackProblem() prob.solve()

Μετά την επίλυση, μπορούμε να εκτυπώσουμε τα αποτελέσματα χρησιμοποιώντας την κλάση προβλήματος print_results λειτουργία. Μπορούμε επίσης να αποκτήσουμε πρόσβαση στην τιμή συγκεκριμένων μεταβλητών κοιτάζοντας το result_variables τάξη.

prob.print_results() print(prob.result_variables)

Εκτελέστε το σενάριο και θα πρέπει να δείτε την ακόλουθη έξοδο:

KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

Θα πρέπει να δείτε την κατάσταση του προβλήματος, την τελική τιμή των μεταβλητών, την αντικειμενική τιμή και την τιμή της έκφρασης περιορισμού. Βλέπουμε επίσης τις προκύπτουσες τιμές των μεταβλητών ως λεξικό.

Και εκεί το έχουμε, το πρώτο μας πρόβλημα HorusLP σε περίπου 35 γραμμές!

Στα επόμενα παραδείγματα, θα διερευνήσουμε μερικές πιο εξελιγμένες δυνατότητες της βιβλιοθήκης HorusLP.

Χρήση VariableGroups

Μερικές φορές, οι μεταβλητές σχετίζονται και ανήκουν σε μια λογική ομάδα. Στην περίπτωση του προβλήματος του σακιδίου, όλες οι μεταβλητές μπορούν να τοποθετηθούν σε μια ομάδα αντικειμένων. Μπορούμε να αναδιαμορφώσουμε τον κώδικα για να χρησιμοποιήσουμε την ομάδα μεταβλητών. Βεβαιωθείτε ότι έχετε αποθηκεύσει τον κωδικό από την προηγούμενη ενότητα καθώς θα τον αναφέρουμε σε επόμενα μαθήματα!

Αλλάξτε τις δηλώσεις εισαγωγής ως εξής:

from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

Τώρα πρέπει επίσης να αλλάξουμε τις δηλώσεις μεταβλητών σακιδίων όπως έτσι:

class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

Το πρώτο όρισμα είναι το όνομα της μεταβλητής ομάδας, η δεύτερη μεταβλητή είναι μια λίστα ονομάτων για τις μεταβλητές εντός αυτής της ομάδας.

Τώρα πρέπει να αλλάξουμε τους περιορισμούς και τους αντικειμενικούς ορισμούς. Αντί να ζητάμε τα μεμονωμένα ονόματα, θα κάνουμε και για την ομάδα μεταβλητών, η οποία θα μεταδοθεί ως λεξικό όπου τα κλειδιά είναι τα ονόματα και οι τιμές είναι οι μεταβλητές. Αλλάξτε τους περιορισμούς και τους αντικειμενικούς ορισμούς όπως:

class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

Τώρα μπορούμε να χρησιμοποιήσουμε τον ίδιο ορισμό προβλημάτων και να εκτελέσουμε εντολές:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

Θα πρέπει να το δείτε αυτό στην έξοδο σας:

KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

Διαχείριση πολλαπλών περιορισμών

Τα μοντέλα με ένα μόνο περιορισμό είναι σχετικά σπάνια. Όταν εργάζεστε με πολλούς περιορισμούς, είναι καλό να έχετε όλους τους περιορισμούς σε ένα μέρος, έτσι ώστε να μπορούν να παρακολουθούνται και να διαχειρίζονται εύκολα. Το HorusLP το κάνει φυσικό.

Ας υποθέσουμε, για παράδειγμα, θέλαμε να δούμε πώς θα άλλαζαν τα αποτελέσματα εάν αναγκάζαμε το μοντέλο να προσθέσει μια κάμερα στο σακίδιο μας. Θα εφαρμόζαμε έναν επιπλέον περιορισμό και θα τον προσθέσουμε στον ορισμό του προβλήματος.

Επιστρέψτε στο μοντέλο που εφαρμόσαμε στο πρώτο σεμινάριο. Προσθέστε τον ακόλουθο περιορισμό:

class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

Για να προσθέσουμε τον περιορισμό στο μοντέλο, πρέπει απλώς να τον προσθέσουμε στον ορισμό του προβλήματος όπως:

τι είναι ένα αρχείο cpp

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

Εκτελέστε το πρόβλημα και θα πρέπει να δείτε την ακόλουθη έξοδο:

KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Θα πρέπει να δείτε τον νέο περιορισμό να εκτυπώνεται στο stdout και τις μεταβλητές βέλτιστες μεταβλητές τιμές.

Διαχείριση εξαρτώμενων περιορισμών και ομάδων περιορισμών

Οι περιορισμοί σχετίζονται συχνά μεταξύ τους είτε επειδή εξαρτώνται ο ένας από τον άλλο είτε επειδή ανήκουν λογικά στην ίδια ομάδα.

Για παράδειγμα, εάν θέλετε να ορίσετε έναν περιορισμό για να περιορίσετε το άθροισμα της απόλυτης τιμής ενός συνόλου μεταβλητών, πρέπει πρώτα να καθορίσετε περιορισμούς για να εκφράσετε τις σχέσεις απόλυτης τιμής μεταξύ των επιδιωκόμενων μεταβλητών και, στη συνέχεια, να καθορίσετε τα όρια απόλυτης τιμής. Μερικές φορές, πρέπει να εφαρμόσετε παρόμοιους περιορισμούς σε μια ομάδα μεταβλητών για να εκφράσετε μια συγκεκριμένη σχέση μεταξύ των μεταβλητών.

Για να εκφράσουμε αυτές τις ομαδοποιήσεις, μπορούμε να χρησιμοποιήσουμε τη λειτουργία εξαρτώμενων περιορισμών των ορισμών περιορισμών. Για να δείτε πώς μπορεί να χρησιμοποιηθεί η λειτουργία εξαρτώμενου περιορισμού, αναδιαμορφώστε το SizeConstraint του προηγούμενου προβλήματος όπως:

class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

Και τώρα για να ελέγξουμε ότι οι εξαρτημένοι περιορισμοί εφαρμόζονται αυτόματα, ας πάρουμε το MustHaveItemConstraint εκτός του ορισμού του προβλήματος:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

Και εκτελέστε ξανά τον κώδικα και θα πρέπει να δείτε τα ακόλουθα στο stdout:

KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

Μοιάζει με το MustHaveItemConstraint εφαρμόζεται! Για ένα πιο περίπλοκο παράδειγμα του πώς μπορεί να χρησιμοποιηθεί ο εξαρτώμενος περιορισμός, ανατρέξτε στο παράδειγμα στελέχωσης στο τέλος του σεμιναρίου.

Διαχείριση πολλαπλών σταθμισμένων στόχων

Συχνά, κατά την ανάπτυξη των αλγορίθμων βελτιστοποίησης, θα συναντήσουμε μια αντικειμενική έκφραση που αποτελείται από πολλά μέρη. Ως μέρος του πειραματισμού μας, ενδέχεται να αλλάξουμε τη στάθμιση διαφόρων αντικειμενικών στοιχείων για να προκαλέσουμε πόλωση στον αλγόριθμο προς το επιθυμητό αποτέλεσμα. Το CombinedObjective παρέχει έναν καθαρό και απλό τρόπο να το εκφράσετε.

Ας υποθέσουμε ότι θέλαμε να μεροληψήσουμε τον αλγόριθμο για να επιλέξουμε το ειδώλιο και τον μηλίτη. Ας αναδιαμορφώσουμε τον κωδικό από την προηγούμενη ενότητα για να χρησιμοποιήσουμε CombinedObjective.

Πρώτα, εισαγάγετε το CombinedObjective τάξη όπως έτσι:

from horuslp.core import CombinedObjective

Μπορούμε να εφαρμόσουμε ένα ανεξάρτητο αντικειμενικό στοιχείο όπως:

class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

Τώρα μπορούμε να συνδυάσουμε τον στόχο αξίας και τον στόχο μηλίτη / ειδώλιο εφαρμόζοντας ένα CombinedObjective:

class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

Ας αλλάξουμε τον ορισμό του προβλήματος όπως:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

Εκτελέστε το πρόβλημα και θα πρέπει να δείτε την ακόλουθη έξοδο:

KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

Η έξοδος θα περιγράψει τη συνδυασμένη αντικειμενική τιμή, την τιμή καθενός από τα αντικειμενικά συστατικά, το βάρος και φυσικά την αξία όλων των περιορισμών.

Εύρεση ασυμβίβαστων περιορισμών

Κατά την ανάπτυξη αλγορίθμων, αντιμετωπίζουμε συχνά ανέφικτα μοντέλα. Εάν το μοντέλο είναι περίπλοκο, μπορεί να είναι δύσκολο να προσδιοριστεί γιατί το μοντέλο είναι ξαφνικά ανέφικτο. Το HorusLP διαθέτει ένα εύχρηστο εργαλείο για να σας βοηθήσει σε αυτές τις περιπτώσεις.

Ας υποθέσουμε ότι προσθέσαμε περιορισμούς και καταλήξαμε με το ακόλουθο σύνολο περιορισμών:

class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn = 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera>= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

Έχουμε μερικούς περιορισμούς στο συνολικό μέγεθος των αντικειμένων στο σακίδιο, έναν περιορισμό που απαιτεί ότι ο μηλίτης πρέπει να βρίσκεται στο σακίδιο, και ένα ασυμβίβαστο σύνολο περιορισμών που απαιτούν η κάμερα να βρίσκεται εντός και όχι στο σακίδιο. (Φυσικά, σε έναν αλγόριθμο πραγματικού κόσμου, οι περιορισμοί συνήθως δεν είναι τόσο προφανείς και περιλαμβάνουν πολύπλοκες μεταβλητές σχέσεις και περιορισμούς.)

Ας υποθέσουμε επίσης ότι οι περιορισμοί ομαδοποιούνται με τον ακόλουθο τρόπο, καθιστώντας ίσως πιο δύσκολη την ανίχνευση:

class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

Εδώ είναι ο ορισμός του προβλήματος:

class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

Εκτελέστε το πρόβλημα και θα δείτε το ακόλουθο αποτέλεσμα:

KnapsackProblem: Infeasible

Ωχ όχι! Τι κάνουμε? Εάν χρησιμοποιούμε τα περισσότερα εργαλεία, πρέπει να ξεκινήσουμε μια δύσκολη συνεδρία εντοπισμού σφαλμάτων όπου περιορίζουμε τους δυνητικά αντιφατικούς περιορισμούς ένας προς έναν. Ευτυχώς, το HorusLP διαθέτει μια δυνατότητα αναζήτησης ασυμβατότητας για να σας βοηθήσει να περιορίσετε τους ασυμβίβαστους περιορισμούς πιο γρήγορα. Ο απλούστερος τρόπος για να χρησιμοποιήσετε τη δυνατότητα αναζήτησης ασυμβατότητας είναι να αλλάξετε το print_results καλέστε έτσι:

prob.print_results(find_infeasible=True)

Τόσο απλό! Εκτελέστε τον κώδικα και τώρα θα πρέπει να δείτε τα ακόλουθα ως έξοδο:

KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

Εξαιρετική! Τώρα έχουμε διαπιστώσει ότι MustHaveItemConstraint δεν είναι η αιτία της αδυναμίας και ότι το ζήτημα οφείλεται στο CombinedConstraints1 και CombinedConstraints2.

Αυτό μας δίνει μερικές πληροφορίες, αλλά μεταξύ των συνδυασμένων περιορισμών υπάρχουν τέσσερις εξαρτημένοι περιορισμοί. Μπορούμε να προσδιορίσουμε ποιοι από τους τέσσερις περιορισμούς είναι ασύμβατοι; Λοιπον ναι. Τροποποιήστε το print_results καλέστε έτσι:

prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

Αυτό θα κάνει την αναζήτηση αδυναμίας να επεκτείνει τους εξαρτώμενους περιορισμούς, έτσι ώστε να έχουμε μια πολύ πιο λεπτομερή εικόνα για το τι προκαλεί την αδυναμία. Εκτελέστε αυτό και θα πρέπει να δείτε την ακόλουθη έξοδο:

KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

Ενώ είναι δελεαστικό να εκτελείτε βαθιά αναζήτηση αδυναμίας κάθε φορά, για ρεαλιστικά προβλήματα με μεγάλο αριθμό συνολικών περιορισμών, η βαθιά αναζήτηση αδυναμίας μπορεί να γίνει πολύ εντατική σε πόρους και χρονοβόρα. Επομένως, είναι καλύτερο να εκτελέσετε τη βασική αναζήτηση αδυναμίας για να περιορίσετε την πιθανότητα και να εκτελέσετε την αναζήτηση βαθιάς αδυναμίας σε ένα μικρότερο υποσύνολο αφού κάνετε κάποια χειροκίνητη έρευνα.

Δημιουργία αλγορίθμων από αρχεία δεδομένων

Όταν κατασκευάζουμε μοντέλα, σπάνια έχουμε την πολυτέλεια να κάνουμε σκληρό κώδικα κάθε περιορισμού και μεταβλητής. Συχνά, το πρόγραμμά μας πρέπει να είναι αρκετά ευέλικτο ώστε να αλλάζει το μοντέλο ανάλογα με τα δεδομένα εισόδου. Ας υποθέσουμε ότι αντί για κωδικοποιημένη είσοδο θέλαμε να δημιουργήσουμε το πρόβλημα του σακιδίου μας από το ακόλουθο JSON:

Παράδειγμα node.js express rest api

{ 'items': [ {'name': 'camera', 'value': 5, 'weight': 2}, {'name': 'figurine', 'value': 7, 'weight': 4}, {'name': 'apple', 'value': 2, 'weight': 7}, {'name': 'horn', 'value': 10, 'weight': 10}, {'name': 'banana', 'value': 9, 'weight': 2} ], 'capacity': 15 }

Μπορούμε να το κάνουμε αυτό στηριζόμενοι στην υποστήριξη των kwargs της λειτουργίας 'καθορισμός' που εφαρμόζουμε για περιορισμούς και στόχους.

Ας τροποποιήσουμε τον κώδικα από το απλό πρόβλημα σακιδίου (το πρόβλημα που εφαρμόσαμε στην ενότητα 1 του σεμιναρίου). Αρχικά, ας βάλουμε τη συμβολοσειρά JSON στο αρχείο. Φυσικά, συνήθως το διαβάζαμε από εξωτερική πηγή, αλλά για λόγους απλότητας ας τα κρατήσουμε όλα σε ένα αρχείο. Προσθέστε τα ακόλουθα στον κωδικό σας:

JSON = ''' { 'items': [ {'name': 'camera', 'value': 5, 'weight': 2}, {'name': 'figurine', 'value': 7, 'weight': 4}, {'name': 'apple', 'value': 2, 'weight': 7}, {'name': 'horn', 'value': 10, 'weight': 10}, {'name': 'banana', 'value': 9, 'weight': 2} ], 'capacity': 15 } '''

Ας βεβαιωθούμε επίσης ότι το πρόγραμμά μας θα είναι σε θέση να το αναλύσει. Προσθέστε τα ακόλουθα στις δηλώσεις εισαγωγής σας:

Import json

Τώρα, ας τροποποιήσουμε τον μεταβλητό κώδικα ρύθμισης έτσι:

mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

Αυτό θα καθορίσει μια μεταβλητή για κάθε ένα από τα στοιχεία του JSON και θα το ονομάσει κατάλληλα.

Ας αλλάξουμε τους περιορισμούς και τους αντικειμενικούς ορισμούς όπως:

class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

Ζητώντας **kwargs αντί για συγκεκριμένες μεταβλητές, το define Η συνάρτηση παίρνει ένα λεξικό που περιέχει όλες τις μεταβλητές με όνομα. Η συνάρτηση ορισμού περιορισμού μπορεί στη συνέχεια να έχει πρόσβαση στις μεταβλητές από το λεξικό.

Σημείωση: Για μεταβλητές ομάδες, θα είναι ένα ένθετο λεξικό όπου το πρώτο επίπεδο είναι το όνομα της ομάδας και το δεύτερο επίπεδο είναι το όνομα της μεταβλητής.

Τα υπόλοιπα είναι αρκετά απλά:

class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Εκτελέστε αυτό το πρόγραμμα και θα δείτε την ακόλουθη έξοδο:

KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

Καθορισμός προσαρμοσμένων μετρήσεων στο HorusLP

Μερικές φορές, τόσο για εντοπισμό σφαλμάτων όσο και για σκοπούς αναφοράς, θα δημιουργήσουμε προσαρμοσμένες μετρήσεις που δεν εκφράζονται απευθείας στον στόχο ή ως περιορισμός. Το HorusLP έχει μια δυνατότητα να απλοποιεί τον καθορισμό προσαρμοσμένων μετρήσεων.

Ας υποθέσουμε ότι θέλαμε να παρακολουθούμε πόσα φρούτα έβαλε το μοντέλο από την προηγούμενη ενότητα στο σακίδιο. Για να το παρακολουθήσουμε, μπορούμε να ορίσουμε μια προσαρμοσμένη μέτρηση. Ας ξεκινήσουμε εισάγοντας την βασική κλάση Μετρήσεων:

From horuslp.core import Metric

Τώρα ας καθορίσουμε την προσαρμοσμένη μέτρηση:

class NumFruits(Metric): name = 'Number of Fruits' def define(self, apple, banana): return apple + banana

Όπως μπορείτε να δείτε, η καθορισμένη διεπαφή μοιάζει πολύ με εκείνη της κατηγορίας συστατικών περιορισμών και αντικειμενικών. Εάν έχετε παρακολουθήσει το σεμινάριο μέχρι στιγμής, αυτό θα σας είναι αρκετά οικείο.

Τώρα πρέπει να προσθέσουμε τη μέτρηση στον ορισμό του προβλήματος. Η διεπαφή εδώ είναι πάλι πολύ παρόμοια με τον ορισμό περιορισμού:

class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

Εκτελέστε αυτό και θα πρέπει να δείτε την ακόλουθη έξοδο:

KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

Μπορείτε να δείτε τον αριθμό των φρούτων που εκτυπώνονται στο κάτω μέρος.

Εργασία σε ένα πιο σύνθετο πρόβλημα: Δύο σακίδια

Ας δούμε ένα ελαφρώς πιο περίπλοκο παράδειγμα. Ας υποθέσουμε ότι αντί για ένα σακίδιο, έχουμε μια τσάντα και μια βαλίτσα. Έχουμε επίσης δύο κατηγορίες αντικειμένων, ανθεκτικά και εύθραυστα. Η βαλίτσα, που είναι πιο προστατευτική, μπορεί να συγκρατεί εύθραυστα και ανθεκτικά προϊόντα. Η τσάντα, από την άλλη πλευρά, μπορεί να κρατήσει μόνο ανθεκτικά προϊόντα. Ας υποθέσουμε επίσης ότι τα δεδομένα για τα στοιχεία δίνονται στο ακόλουθο JSON:

{ 'fragile': [ {'name': 'camera', 'value': 5, 'weight': 2}, {'name': 'glasses', 'value': 3, 'weight': 4}, {'name': 'apple', 'value': 2, 'weight': 7}, {'name': 'pear', 'value': 5, 'weight': 3}, {'name': 'banana', 'value': 9, 'weight': 2} ], 'durable': [ {'name': 'figurine', 'value': 7, 'weight': 4}, {'name': 'horn', 'value': 10, 'weight': 10}, {'name': 'leatherman', 'value': 10, 'weight': 3} ], 'suitcase_capacity': 15, 'bag_capacity': 20 }

Ας δούμε πώς αυτό αλλάζει το μοντέλο. Ας ξεκινήσουμε με μια κενή πλάκα καθώς το μοντέλο θα είναι πολύ διαφορετικό. Ξεκινήστε με τη ρύθμιση του προβλήματος:

τι είναι η ιεραρχία στη γραφιστική

import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { 'fragile': [ {'name': 'camera', 'value': 5, 'weight': 2}, {'name': 'glasses', 'value': 3, 'weight': 4}, {'name': 'apple', 'value': 2, 'weight': 7}, {'name': 'pear', 'value': 5, 'weight': 3}, {'name': 'banana', 'value': 9, 'weight': 2} ], 'durable': [ {'name': 'figurine', 'value': 7, 'weight': 4}, {'name': 'horn', 'value': 10, 'weight': 10}, {'name': 'leatherman', 'value': 10, 'weight': 3} ], 'suitcase_capacity': 15, 'bag_capacity': 20 } ''' mip_cfg = json.loads(JSON)

Τώρα ας ρυθμίσουμε τις μεταβλητές. Θα δημιουργήσουμε μια δυαδική μεταβλητή για κάθε πιθανό συνδυασμό στοιχείων / κοντέινερ.

class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

Τώρα θέλουμε να εφαρμόσουμε περιορισμούς βάρους τόσο για τη βαλίτσα όσο και για την τσάντα.

class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

Τώρα πρέπει να εφαρμόσουμε έναν ελαφρώς πιο περίπλοκο περιορισμό - τον περιορισμό που διασφαλίζει ότι ένα είδος δεν μπαίνει τόσο στη βαλίτσα όσο και στην τσάντα - δηλαδή, εάν η μεταβλητή 'στην βαλίτσα' είναι 1, τότε η 'στην τσάντα' η μεταβλητή πρέπει να είναι μηδέν και το αντίστροφο. Φυσικά, θέλουμε να διασφαλίσουμε ότι επιτρέπονται περιπτώσεις όπου το στοιχείο δεν καταλήγει ούτε σε κοντέινερ.

Για να προσθέσουμε αυτόν τον περιορισμό, πρέπει να επαναλάβουμε όλα τα ανθεκτικά αντικείμενα, να βρούμε τη μεταβλητή 'στη βαλίτσα' και τη μεταβλητή 'στην τσάντα' και να βεβαιώσουμε ότι το άθροισμα αυτών των μεταβλητών είναι μικρότερο από 1.

Μπορούμε να ορίσουμε δυναμικά εξαρτώμενους περιορισμούς στο HorusLP:

class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = 'Uniqueness_%s' % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

Τώρα που ορίζονται οι περιορισμοί, ας χτίσουμε τον στόχο. Ο στόχος είναι απλό το άθροισμα όλων των τιμών που λαμβάνουμε από όλα τα αντικείμενα που βρίσκονται σε κοντέινερ. Ετσι:

class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

Ας ορίσουμε επίσης ορισμένες προσαρμοσμένες μετρήσεις, ώστε να μπορούμε να δούμε με μια ματιά πόσο βάρος τοποθετήθηκε στην τσάντα και τη βαλίτσα, καθώς και πόσο το βάρος της βαλίτσας προήλθε από ανθεκτικά και εύθραυστα προϊόντα:

class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

Τώρα έχουμε ολοκληρώσει όλα τα κομμάτια, ας δημιουργήσουμε το πρόβλημα και τρέξουμε το μοντέλο:

class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

Εκτελέστε αυτό και θα πρέπει να δείτε την ακόλουθη έξοδο στο stdout σας:

KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

Έτσι, η κάμερα, τα γυαλιά, το μήλο και η μπανάνα μπαίνουν στη βαλίτσα για συνολικά 15 μονάδες βάρους, το ειδώλιο, το κέρατο και ο δερμάτινος άντρας πάνε στην τσάντα για συνολικό βάρος 17. Η συνολική αξία των αγαθών ανέρχεται σε 32 μονάδες αξίας. Είναι ενδιαφέρον ότι κανένα από τα ανθεκτικά αγαθά δεν κατέληξε στη βαλίτσα, πιθανότατα επειδή η τσάντα είχε αρκετή χωρητικότητα για να χωρέσει όλα τα ανθεκτικά αγαθά.

Ένα μεγαλύτερο και πιο ρεαλιστικό σενάριο: Το πρόβλημα στελέχωσης

Εάν το έχετε φτάσει μέχρι τώρα στο φροντιστήριο HorusLP, συγχαρητήρια! Τώρα έχετε μια καλή ιδέα για το πώς να χρησιμοποιήσετε το HorusLP.

Ωστόσο, όλα τα παραδείγματα που έχουμε εργαστεί μέχρι στιγμής ήταν παραλλαγές του προβλήματος σακιδίου και ορισμένες από τις απαιτήσεις και τις παραμέτρους είναι λίγο ρεαλιστικές. Ας δούμε ένα ακόμη πρόβλημα μαζί για να δούμε πώς το HorusLP μπορεί να λύσει ένα πιο ρεαλιστικό πρόβλημα. Θα επιλύσουμε το πρόβλημα στελέχωσης που περιγράφεται στο δεύτερο μισό του το προηγούμενο άρθρο μου στο ApeeScape .

Προς το συμφέρον του χρόνου, θα προχωρήσουμε κατευθείαν για την τελική έκδοση του μοντέλου (με προσωπικές συγκρούσεις, εργασιακούς κανονισμούς και προσωρινά επιδόματα εργαζομένων), αλλά η εφαρμογή του αρχικού απλούστερου μοντέλου είναι επίσης διαθέσιμη στο GitHub.

Ας ξεκινήσουμε ρυθμίζοντας το πρόβλημα:

from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { 'Melisandre': { 'availability': [0, 1, 4], 'cost': 20 }, 'Bran': { 'availability': [1, 2, 3, 4], 'cost': 15 }, 'Cersei': { 'availability': [2, 3], 'cost': 35 }, 'Daenerys': { 'availability': [3, 4], 'cost': 35 }, 'Theon': { 'availability': [1, 3, 4], 'cost': 10 }, 'Jon': { 'availability': [0, 2, 4], 'cost': 25 }, 'Tyrion': { 'availability': [1, 3, 4], 'cost': 30 }, 'Jaime': { 'availability': [1, 2, 4], 'cost': 20 }, 'Arya': { 'availability': [0, 1, 3], 'cost': 20 } } # the following people can't work together, sadly. ban_list = { ('Daenerys', 'Jaime'), ('Daenerys', 'Cersei'), ('Jon', 'Jaime'), ('Jon', 'Cersei'), ('Arya', 'Jaime'), ('Arya', 'Cersei'), ('Arya', 'Melisandre'), ('Jaime', 'Cersei') } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Τώρα ας καθορίσουμε τις μεταβλητές, οι οποίες σε αυτήν την περίπτωση θα ήταν δυαδικές μεταβλητές που θα καθορίσουν εάν ένας εργαζόμενος πρέπει να κάνει τη βάρδια του και ακέραιες μεταβλητές που καθορίζουν πόσα dothrakis προσλαμβάνουμε για κάθε shift:

class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

Τώρα ας εφαρμόσουμε τον περιορισμό που απαιτεί από εμάς να εργαζόμαστε επαρκώς για κάθε βάρδια:

class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = 'shift_requirement_%d' % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

Τώρα, πρέπει να εφαρμόσουμε τους περιορισμούς που εμποδίζουν συγκεκριμένα άτομα να συνεργάζονται μεταξύ τους:

class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = 'Conflict_%s_%s_%d' % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

Και τέλος ο περιορισμός των εργασιακών προτύπων. Θα το εφαρμόσουμε λίγο διαφορετικά για αποδεικτικούς σκοπούς:

class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = 'labor_standard_%s' % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

Και τώρα ας καθορίσουμε τους στόχους. Το κόστος dothraki και το κανονικό κόστος των εργαζομένων υπολογίζονται πολύ διαφορετικά, οπότε θα τα τοποθετήσουμε σε ξεχωριστά αντικειμενικά στοιχεία:

class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

Και τώρα μπορούμε να ορίσουμε και να τρέξουμε το πρόβλημα:

class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Εκτελέστε το σενάριο και θα δείτε τα εξής:

StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

Εάν το συγκρίνετε με το πρόβλημα που εφαρμόσαμε στο προηγούμενο σεμινάριο, θα πρέπει να δείτε ότι τα αποτελέσματα ταιριάζουν.

Τυλίγοντας

Συγχαρητήρια για την επιτυχία μέσω του πρώτου μας οδηγού HorusLP! Είστε πλέον ικανός επαγγελματίας του HorusLP.

Ελπίζω ότι αυτό το άρθρο σας έπεισε τα οφέλη της δημιουργίας σας Μοντέλα MIP και ότι θα χρησιμοποιήσετε το HorusLP στα επόμενα έργα σας. Μπορείτε να βρείτε τον πηγαίο κώδικα HorusLP, καθώς και τον κωδικό για όλα τα σεμινάρια GitHub . Πρόσθετη τεκμηρίωση HorusLP και σελίδα εκμάθησης θα προστεθούν στο GitHub πολύ σύντομα.

Καθώς το HorusLP είναι ένα αρκετά νέο έργο, θα θέλαμε πολύ να ακούσουμε από εσάς και να ενσωματώσουμε τη συμβολή σας. Εάν έχετε οποιεσδήποτε ερωτήσεις, σχόλια ή προτάσεις, παρακαλώ ρίξτε μου μια γραμμή είτε μέσω του ApeeScape είτε χρησιμοποιώντας τα στοιχεία επικοινωνίας που μπορείτε να βρείτε στο GitHub. Ελπίζω να ακούσω νέα σου σύντομα!

Κατανόηση των βασικών

Τι είναι το HorusLP;

Το HorusLP είναι μια βιβλιοθήκη βελτιστοποίησης Python που έχει σχεδιαστεί για να σας βοηθά στη ροή εργασιών ανάπτυξης αλγορίθμων αρχιτέκτονα. Διαθέτει ένα απλό, δηλωτικό API και πολύ λίγο boilerplate.

Ποιο είναι το πρόβλημα Knapsnack;

Το πρόβλημα Knapsnack είναι ένα πρόβλημα βελτιστοποίησης που επικεντρώνεται στη συνδυαστική βελτιστοποίηση. Όταν παρουσιάζεται με ένα σύνολο αντικειμένων με διαφορετικά βάρη και τιμές, ο στόχος είναι να 'ταιριάζει' πολλά από αυτά σε ένα σακίδιο που είναι περιορισμένο και δεν υπόκειται σε αλλαγές.