Πώς να λύσετε γραμμικά προβλήματα με μεγάλο αριθμό μεταβλητών απόφασης που απεικονίζεται με ένα παράδειγμα Python
Ορισμένα προβλήματα Γραμμικού Προγραμματισμού (LP) που προκύπτουν από συνδυαστικά προβλήματα καθίστανται δυσεπίλυτα λόγω του μεγάλου αριθμού των μεταβλητών που εμπλέκονται (Gilmore & Gomory, 1961). Σε τέτοια προβλήματα, η καθυστερημένη δημιουργία στήλης είναι μια πιθανή εναλλακτική λύση, καθώς δεν περιλαμβάνει όλες τις πιθανές μεταβλητές απόφασης στο πρόβλημα από την αρχή. Μια κλασική εφαρμογή είναι στο πρόβλημα του υλικού κοπής, στο οποίο πρέπει κανείς να αποφασίσει πώς να κόψει ένα ρολό δεδομένου πλάτους σε μικρότερα κομμάτια για να καλύψει τις απαιτήσεις για καθορισμένα μεγέθη κοπής.
Σε όλο αυτό το άρθρο, μερικές από τις κύριες θεωρητικές πτυχές της δημιουργίας στηλών θα παρουσιαστούν και θα απεικονιστούν με το πρόβλημα του μονοδιάστατου αποθέματος κοπής. Στη λύση, θα χρησιμοποιηθεί η scipy βιβλιοθήκη Python. Οι ενδιαφερόμενοι μπορούν επίσης να βρουν τον πλήρη κωδικό σε αυτό το git repository.
Σε περίπτωση που δεν είστε ακόμη εξοικειωμένοι με τον Γραμμικό Προγραμματισμό, ίσως κατανοήσετε καλύτερα αυτό το άρθρο αφού διαβάσετε την προηγούμενη εισαγωγή μου σχετικά με το θέμα.
Εάν είστε έτοιμοι για βαθύτερες έννοιες μαζί με ένα πρακτικό παράδειγμα, καλώς ήρθατε στο πλοίο.
Δημιουργία στηλών: μια επισκόπηση
Όταν χρησιμοποιείται η καθυστερημένη δημιουργία στηλών για την επίλυση ενός LP, σε κάθε επανάληψη, λαμβάνεται υπόψη ένα πρόβλημα μόνο με ένα υποσύνολο στηλών. Ονομάζεται Περιορισμένο κύριο πρόβλημα (RMP). Σε κάθε επανάληψη, λύνεται το RMP και προκύπτει το αντίστοιχο διάνυσμα βέλτιστων μεταβλητών διπλής απόφασης π. Στη συνέχεια, ο αλγόριθμος χρησιμοποιεί αυτό το αποτέλεσμα για να λύσει το υποπρόβλημα ή το πρόβλημα τιμολόγησης, το οποίο στοχεύει στην εύρεση νέων μεταβλητών απόφασης με αρνητικό μειωμένο κόστος. Ας θυμηθούμε έναν ορισμό του μειωμένου κόστους.
Για οποιαδήποτε μη βασική μεταβλητή, το μειωμένο κόστος για τη μεταβλητή είναι το ποσό κατά το οποίο πρέπει να βελτιωθεί ο συντελεστής αντικειμενικής συνάρτησης της μη βασικής μεταβλητής προτού αυτή η μεταβλητή γίνει βασική μεταβλητή σε κάποια βέλτιστη λύση του LP. Winston & Goldberg (2004)
Επομένως, με τη συμπερίληψη μεταβλητών με αρνητικό μειωμένο κόστος, ενδέχεται να περιμένουμε οριακή συμβολή στη βελτίωση της αντικειμενικής αξίας. Θυμηθείτε την οικονομική ερμηνεία των διπλών μεταβλητών ως σκιώδες κόστος. Μια νέα μεταβλητή θα μπορούσε ενδεχομένως να οδηγήσει σε εξοικονόμηση πόρων ανάλογη με τη συμβολή της στην εκπλήρωση των περιορισμών δεδομένων των αντίστοιχων διπλών τους, αυξάνοντας παράλληλα το συνολικό κόστος κατά τον συντελεστή κόστους της.
Επιλύοντας το υποπρόβλημα, προσδιορίζουμε ένα σύνολο S στηλών με το χαμηλότερο μειωμένο κόστος δεδομένου του διπλού κόστους. Εάν δεν εντοπιστεί στήλη με αρνητικό μειωμένο κόστος, σταματάμε αφού το πείναι μια βέλτιστη διπλή λύση στο αρχικό πρόβλημα και μαζί με τη βέλτιστη πρωταρχική λύση στο RMP, έχουν ένα βέλτιστο πρωτεύον/διπλό ζεύγος. Διαφορετικά, προσαρτούμε στήλες στο S στο RMP και επαναλαμβάνουμε (Klabjan, 2005). Αυτή η διαδικασία αντιπροσωπεύεται από το παρακάτω σχήμα.
Παρατηρήστε ότι το υποπρόβλημα είναι συγκεκριμένο για το πρόβλημα και σε ορισμένες περιπτώσεις μπορεί να είναι αρκετά υπολογιστικά ακριβό για να διατυπωθεί ως πρόβλημα προγραμματισμού μεικτού ακέραιου αριθμού. Μπορεί να είναι χρήσιμο στη συνέχεια να εξετάσουμε ευρετικές ή/και δυναμικές προσεγγίσεις προγραμματισμού που ενδέχεται να επιστρέφουν, σε κάθε επανάληψη, περισσότερες από μία αρνητικές στήλες μειωμένου κόστους. Στην περίπτωση προβλημάτων δρομολόγησης οχημάτων, συχνά το υποπρόβλημα είναι ένα περιορισμένο πρόβλημα συντομότερης διαδρομής. Όσοι ενδιαφέρονται για μια βαθύτερη κατάδυση μπορούν να ανατρέξουν στους Irnich & Desaulniers (2005) για να αποκτήσουν πληροφορίες σχετικά με τις τεχνικές λύσης.
Τώρα θυμηθείτε ότι η προσέγγιση καθυστερημένης δημιουργίας στήλης που παρουσιάζεται επιλύει ένα πρόβλημα Γραμμικού Προγραμματισμού με μεταβλητές απόφασης πραγματικής αξίας. Με στόχο την επίλυση μεγάλων προγραμμάτων ακέραιου ή μικτού ακέραιου, θα μπορούσε κανείς να καταφύγει είτε σε κάποια ευρετικά μετά την επίλυση της χαλάρωσης είτε σε Branch & Price για να επιβάλει περιορισμούς ακεραιότητας. Στην τελευταία προσέγγιση, θα πρέπει να ληφθούν υπόψη όχι μόνο εκείνες οι στήλες που έχουν δημιουργηθεί στη λύση του αρχικού LP, αλλά δημιουργούν και νέες στήλες κατά τη διάρκεια της επίλυσης των LP σε όλο το δέντρο. Μια βαθύτερη συζήτηση για το Branch & Price παρουσιάζεται από τους Barnhart et al. (1998). Οι συγγραφείς εξετάζουν κοινά ζητήματα, μελέτες περιπτώσεων και ενδιαφέρουσες γνώσεις σχετικά με τους κανόνες διακλάδωσης.
Το πρόβλημα του κοπτικού αποθέματος
Σκεφτείτε ότι έχουμε ένα σύνολο απαιτήσεων I, το καθένα για ένα ποσό d τεμαχίων πλάτους w. Επίσης, σκεφτείτε ότι έχουμε ένα ρολό πλάτους W από το οποίο θα παραχθούν τα κοψίματα. Το σύνολο των γνωστών μοτίβων κοπής θα συμβολίζεται P. Κάθε κομμάτι ενός σχεδίου κοπής p καταναλώνει μία μονάδα του ρολού (c= 1) και παράγει aᵢₚ μονάδες πλάτους wᵢ. Στόχος μας είναι να προσδιορίσουμε τον αριθμό των περικοπών x κάθε μοτίβου p που θα πρέπει να χρησιμοποιηθεί για την ικανοποίηση των απαιτήσεων, ελαχιστοποιώντας παράλληλα τον αριθμό των μονάδων που καταναλώνονται. Μπορούμε να διατυπώσουμε αυτό το πρόβλημα ως εξής.
Οι μεταβλητές διπλής απόφασης που σχετίζονται με περιορισμούς ζήτησης πχρησιμοποιούνται στη συνέχεια στο πρόβλημα τιμολόγησης (υποπρόβλημα) για την εύρεση νέων μοτίβων με αρνητική μειωμένη κόστος. Στην περίπτωση του προβλήματος του αποθέματος κοπής, πρέπει να βρούμε ένα νέο σχέδιο που να συνδυάζει κομμάτια διαφορετικού πλάτους που ταιριάζουν στο συνολικό πλάτος W και, συμβάλλοντας στην κάλυψη των απαιτήσεων υλικών, θα οδηγούσε σε μεγαλύτερη εξοικονόμηση πόρων από νέο κόστος. Αυτό είναι ένα πρόβλημα σακιδίου, το οποίο μπορεί να διατυπωθεί ως εξής.
Στο οποίο το yᵢ αντιστοιχεί στον αριθμό των τεμαχίων πλάτους wᵢ που παράγονται στο νέο σχέδιο κοπής.
Καθώς γνωρίζουμε ότι κάθε νέο μοτίβο θα έχει ένα μοναδιαίο κόστος c ίσο με 1, μπορούμε να υπολογίσουμε το μειωμένο κόστος του νέου μοτίβου ως εξής:
Το οποίο, στην περίπτωση των μη αρνητικών τιμών, θα πρέπει να σταματήσει τον αλγόριθμο δημιουργίας στηλών.
Για να ληφθούν ακέραιες λύσεις στο πρόβλημα του αποθέματος κοπής, μια απλή ευρετική μέθοδος είναι απλώς η στρογγυλοποίηση των κλασματικών τιμών που λαμβάνονται στη γραμμική χαλάρωση. Εναλλακτικά, θα μπορούσε κανείς επίσης να λύσει το γραμμικό πρόβλημα με το σύνολο των μοτίβων που παράγονται στη γραμμική χαλάρωση επιβάλλοντας περιορισμούς ακεραιότητας. Θα χρησιμοποιήσουμε και τις δύο στρατηγικές σε αυτό το άρθρο. Για περιπτώσεις στις οποίες η γραμμική χαλάρωση είναι κοντά στο μοντέλο πλήρους ακέραιου αριθμού, αυτές οι στρατηγικές μπορεί να είναι πολύ επιτυχημένες. Ορισμένες διαφορές ενδέχεται να προκύψουν σε άλλες περιπτώσεις στις οποίες ο αριθμός των απαιτήσεων για κάθε μοτίβο είναι σχετικά μικρός.
Εάν κάποιος στοχεύει να αποκτήσει τις ακριβείς ακέραιες λύσεις, το Branch & Price μπορεί να είναι μια καλή εναλλακτική. Σε αυτή την προσέγγιση, μετά τη διακλάδωση σε ορισμένες από τις αρχικές μεταβλητές, ενδέχεται να συμπεριληφθούν νέες στήλες με μειωμένο κόστος στον τρέχοντα κόμβο. Όσοι ενδιαφέρονται για περισσότερες λεπτομέρειες μπορούν να ανατρέξουν στον Carvalho (1998) και στον Vance (1998).
Τώρα ας βάλουμε μερικά χέρια!
Λύση
Ας ξεκινήσουμε την εφαρμογή Python του προβλήματος του αποθέματος κοπής, στο οποίο η χαλάρωση LP επιλύεται με βέλτιστο τρόπο και λύνεται ένα ακέραιο μοντέλο με τα μοτίβα που έχουν παραχθεί μέχρι τώρα. Θα χρησιμοποιήσουμε numpy για να κάνουμε πράξεις γραμμικής άλγεβρας, pandas για εργασία με πλαίσια δεδομένων, scipy στους αλγόριθμους βελτιστοποίησης και matplotlib em> για να οπτικοποιήσετε τα μοτίβα κοπής σε μια πλοκή.
import numpy as np import pandas as pd from scipy.optimize import linprog import matplotlib.pyplot as plt
Ας εισάγουμε ένα σύνολο δεδομένων που είναι μια τροποποιημένη έκδοση του προβλήματος που προτείνεται στην τεκμηρίωση JuMP.
dataset = pd.read_csv("data.txt", sep=" ")
Και ας παρουσιάσουμε τις παραμέτρους του προβλήματος
# Total width W = 100.0 # Width and amount associated with each demand w = dataset.w.values d = dataset.d.values # LP parameters A = np.eye(dataset.shape[0]) * (W // w) c = np.ones_like(w)
Παρατηρήστε ότι για να αρχικοποιήσω τον πίνακα A, εισήγαγα κοπή απλών μοτίβων που παράγουν τον μέγιστο δυνατό αριθμό κυλίνδρων για κάθε πλάτος από τις απαιτήσεις. Ας υποθέσουμε ότι υπάρχει κάποια ζήτηση για ρολά πλάτους 24. Θα οδηγούσε σε ένα αρχικό σχέδιο κοπής με συντελεστή 4, δεδομένου του συνολικού πλάτους W100.
Τώρα ας ορίσουμε μια συνάρτηση για να λύσουμε το υποπρόβλημα δεδομένου του συνολικού πλάτους W, ενός διανύσματος πλάτη που σχετίζεται με κάθε ζήτηση w και το τρέχον διάνυσμα διπλών μεταβλητών duals.
def solve_knapsack(W, w, duals):
return linprog(
-duals, A_ub=np.atleast_2d(w), b_ub=np.atleast_1d(W),
bounds=(0, np.inf), integrality=1,
)
Στον κύριο βρόχο, για κάθε λύση του περιορισμένου βασικού προβλήματος, θα χρησιμοποιήσουμε τη συνάρτηση linprog από το scipy. Ο πίνακας A καθώς και το διάνυσμα απαιτήσεων μεταβιβάζονται και τα δύο ως αρνητικά τους καθώς κατά σύμβαση η scipy θεωρεί μόνο ανισότητες "μικρότερες από ή ίσες με".
linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))
Η λύση θα πρέπει να έχει το αρνητικό των διπλών μεταβλητών που σχετίζονται με τις απαιτήσεις που είναι αποθηκευμένες στο χαρακτηριστικό ineqlin.marginals.
Εξερευνώντας τις έννοιες της δυαδικότητας, θα μπορούσε κανείς επίσης να αποκτήσει διπλές μεταβλητές λύνοντας την ακόλουθη LP.
linprog(-d, A_ub=A.T, b_ub=c, bounds=(0, None))
Και ας τα βάλουμε όλα μαζί στον κύριο βρόχο.
# Initial solution
sol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))
sol_dual = linprog(-d, A_ub=A.T, b_ub=c, bounds=(0, None))
diff = np.abs(sol_dual.x + sol.ineqlin.marginals).sum()
print(f"Compare duality difference: {diff}")
# Iterate
for _ in range(1000):
duals = -sol.ineqlin.marginals
price_sol = solve_knapsack(W, w, duals)
y = price_sol.x
if 1 + price_sol.fun < -1e-4:
print(f"Iteration: {_}; Reduced cost: {(1 + price_sol.fun):.3f}")
A = np.hstack((A, y.reshape((-1, 1))))
c = np.append(c, 1)
sol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, None))
else:
break
Στο τέλος, ας προσπαθήσουμε να στρογγυλοποιήσουμε τη λύση της γραμμικής χαλάρωσης και να λάβουμε την ακέραια λύση λαμβάνοντας υπόψη μόνο τις στήλες που παράγονται στο LP.
sol_round = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, np.inf), integrality=0)
print(f"Rounding solution {np.ceil(sol_round.x).sum()}")
sol = linprog(c, A_ub=-A, b_ub=-d, bounds=(0, np.inf), integrality=1)
print(f"Integer solution: {sol.x.sum()}")
Που πρέπει να επιστρέψει:
- Λύση στρογγυλοποίησης 339.0
- Λύση ακέραιου αριθμού: 334.0
Σε αυτήν την περίπτωση, θα μπορούσαμε να βελτιώσουμε το αποτέλεσμα σχεδόν κατά 2% απλώς επιβάλλοντας περιορισμούς ακεραιότητας στο LP αντί απλώς στρογγυλοποιώντας τη χαλάρωση. Απλά ένα spoiler για όσους θέλουν να δοκιμάσουν το Branch & Price: 334 είναι η ακριβής λύση για αυτήν την περίπτωση.
Επιτέλους, ας προσπαθήσουμε να οπτικοποιήσουμε τα νέα μοτίβα κοπής:
fig, ax = plt.subplots(figsize=[7, 3], dpi=100)
hmap = ax.imshow(A > 1e-6, cmap="Blues")
plt.axis('off')
fig.tight_layout()
plt.show()
Και λύσαμε το πρόβλημα του αποθέματος κοπής χρησιμοποιώντας τη δημιουργία στήλης.
Περαιτέρω ανάγνωση
Το πρόβλημα δρομολόγησης χωρητικότητας οχημάτων (CVRP) προτάθηκε για πρώτη φορά από τους Dantzig & Ramser (1959) και είναι ιδιαίτερα προκλητικό λόγω της συνδυαστικής του φύσης. Οι συγγραφείς δείχνουν στην αρχική τους εργασία ότι ακόμη και για μικρά προβλήματα ο αριθμός των πιθανών διαδρομών είναι απίστευτα μεγάλος. Για παράδειγμα, ένα συμμετρικό πρόβλημα με 15 σημεία ζήτησης έχει περισσότερες από 6 × 109 πιθανές διαδρομές. Θεωρώ ότι είναι ιδιαίτερα ενδιαφέρον να δω πώς εξερευνήθηκε η δημιουργία στηλών με την πάροδο του χρόνου σε αυτό και τα σχετικά προβλήματα.
Αν και για το πρόβλημα δρομολόγησης οχημάτων με αυστηρά περιορισμένα χρονικά παράθυρα, η δημιουργία στηλών είχε καθιερωθεί καλά από την εργασία των Desrochers et al. (1992), Branch & Price συχνά αποτυγχάνουν σε λιγότερο περιορισμένες περιπτώσεις. Επομένως, η καθαρή δημιουργία στήλης δεν έχει θεωρηθεί ως μια πολλά υποσχόμενη προσέγγιση για το CVRP. Ωστόσο, οι Fukasawa et al. (2006) συνδύασε τη δημιουργία στηλών σε έναν αλγόριθμο Branch & Cut, αποδεικνύοντας τη βέλτιστη χρήση πολλών περιπτώσεων από τη βιβλιογραφία. Το Branch-cut-and-Price για το CVRP βελτιώθηκε περαιτέρω από άλλους συγγραφείς και πιστεύω ότι η εργασία των Pecin et al. (2017) μπορεί να είναι ιδιαίτερα συναρπαστικό για τον ενδιαφερόμενο αναγνώστη.
συμπεράσματα
Σε αυτό το άρθρο, η καθυστερημένη δημιουργία στηλών εισήχθη ως στρατηγική για την επίλυση γραμμικών προγραμμάτων με μεγάλο αριθμό μεταβλητών απόφασης χωρίς να λαμβάνονται ρητά όλες οι μεταβλητές. Το κλασικό μονοδιάστατο πρόβλημα του αποθέματος κοπής παρουσιάστηκε για την απεικόνιση της μεθόδου και εφαρμόστηκε μια εναλλακτική λύση στην Python. Ο πλήρης κώδικας είναι διαθέσιμος σε αυτό το git repository.
βιβλιογραφικές αναφορές
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H., 1998. Branch-and-price: Column Generation for solving τεράστια ακέραια προγράμματα. Έρευνα επιχειρήσεων, 46(3), 316–329.
de Carvalho, J. V., 1998. Ακριβής επίλυση προβλημάτων αποθεμάτων κοπής με χρήση στήλης δημιουργίας και διακλάδωσης και δέσμευσης. Διεθνείς συναλλαγές στην επιχειρησιακή έρευνα, 5(1), 35–44.
Dantzig, G. B., & Ramser, J. H., 1959. The truck dispatching problem. Management Science, 6(1), 80–91.
Desrochers, M., Desrosiers, J., & Solomon, M., 1992. Ένας νέος αλγόριθμος βελτιστοποίησης για το πρόβλημα δρομολόγησης οχημάτων με χρονικά παράθυρα. Έρευνα επιχειρήσεων, 40(2), 342–354.
Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. D., Reis, M., Uchoa, E., & Werneck, R. F., 2006. Στιβαρή διακλάδωση και κοπή και τιμή για το όχημα με χωρητικότητα πρόβλημα δρομολόγησης. Μαθηματικός προγραμματισμός, 106, 491–511.
Gilmore, P. C., & Gomory, R. E., 1961. Μια γραμμική προσέγγιση προγραμματισμού στο πρόβλημα των αποθεμάτων. Έρευνα επιχειρήσεων, 9(6), 849–859.
Irnich, S., & Desaulniers, G., 2005. Προβλήματα συντομότερης διαδρομής με περιορισμούς πόρων (σελ. 33–65). Springer US.
Klabjan, D., 2005. Μοντέλα μεγάλης κλίμακας στην αεροπορική βιομηχανία. Δημιουργία στήλης, 163–195.
Pecin, D., Pessoa, A., Poggi, M., & Uchoa, E., 2017. Βελτιωμένη διακλάδωση και τιμή για δρομολόγηση οχημάτων με χωρητικότητα. Υπολογισμός Μαθηματικού Προγραμματισμού, 9, 61–100.
Vance, P. H., 1998. Αλγόριθμοι διακλάδωσης και τιμής για το μονοδιάστατο πρόβλημα κοπής αποθεμάτων. Υπολογιστική βελτιστοποίηση και εφαρμογές, 9, 211–228.
Winston, W. L. & Goldberg, J. B., 2004. Έρευνα λειτουργιών: εφαρμογές και αλγόριθμοι. 4η έκδ. Belmont, CA: Thomson Brooks/Cole Belmont.
