Acceleration of benders decomposition method for the solution of mixed integer linear programming problems

Abstract

In the current thesis, the Benders Decomposition method for the solution of Mixed-Integer Linear Problems (MILP) is studied and four novel techniques are introduced for its acceleration. Two of these techniques are problem-specific, while the other two are generalized and can be applied to any MILP. The first technique is a generalized one and addresses the case where the application of Benders decomposition method to a MILP results into a subproblem including integer variables. In this case, it is not possible to apply the classical Benders algorithm and, for this reason, a Branch-and-Cut algorithm is proposed. The integrality constraints of the subproblem are relaxed and the Benders algorithm is applied in a branch-and-bound framework. Benders cuts generated in a node of the branch-and-bound tree are proved to be valid for all its descendants. These “Local Cuts”, can be used to warm start the master problem of each descendant node, thus leading to better initial bounds. Furthermore, a novel way is presented for generalizing the “Local Cuts” (“Generalized/Global Cuts”), offering the ability to reuse the generated cuts in the whole tree. The proposed algorithm is tested on the classical Capacitated Fixed Charge Multiple Knapsack Problem (CFCMKP) and it offers a significant reduction in CPU time compared to the corresponding algorithm without “Local Cuts”. The second technique is a problem-specific one, that addresses the Maximal Covering Location Problem (MCLP). Specifically, a Double-type Double-standard Model (DtDsM), with several applications in determining the location of public emergency services (ex. ambulance, fire-fighting and police vehicles), is proposed. In DtDsM two types of resources are considered: normal resources, which offer full service with small coverage distance in a predetermined time, and backup resources, which offer only a primary service with greater coverage distance. Each demand point must lie within the coverage distance of a backup resource, if it does not lie in the coverage distance of a normal resource, ensuring it receives minimal primary services. For the solution of the DtDsM for MCLP an accelerated Benders decomposition algorithm is proposed, based on the exploitation of the special structure of the problem. The suggested algorithm outperforms both the commercial solver CPLEX and the classical Benders algorithm, as regards speed and accuracy. The third technique is a generalized one, that aims at producing more efficient feasibility and optimality Benders cuts, in order to reduce the bound fluctuation and accelerate the algorithm. The main advantage of the proposed technique is that it can be easily used in every problem of the Mathematical Programming, where Benders Decomposition is applied, without any restrictions. Four different variants of the proposed algorithm are applied on a Crude Oil Scheduling formulation and promising computational results are derived. Finally, the fourth technique is a problem-specific one, addressing the Multi-Trip Time-Dependent Vehicle Routing Problem with Time-Windows (MTTDVRPTW), which is a challenging problem of the last-mile-delivery logistics companies. Based on a literature model, a new reformulation with reduced size is suggested. The reformulation is Benders decomposed in an effective way, resulting into a subproblem with no duality gap. By exploiting the special features of the problem, several novel valid inequalities are introduced, in order to warm start the relaxed master problem and achieve less infeasible solutions and better lower bounds. For the solution of the problem, an innovative algorithm is proposed, including suboptimal master solutions and a multi-cut generation procedure, which is based on the careful observation of the values of the Benders dual subproblem variables. Two variants of the suggested algorithm are tested on benchmark data showing improved efficiency and stronger bounds than the non-decomposed models.

Στην παρούσα διδακτορική διατριβή μελετάται η μέθοδος μαθηματικής αποσύνθεσης Benders για την επίλυση Προβλημάτων Μικτού Ακέραιου Γραμμικού Προγραμματισμού (ΜΑΓΠ) και εισάγονται τέσσερις νέες τεχνικές για την επιτάχυνσή της. Δύο από αυτές τις τεχνικές αφορούν συγκεκριμένα προβλήματα, ενώ οι άλλες δύο είναι γενικευμένες και μπορούν να εφαρμοστούν σε οποιοδήποτε πρόβλημα. Η πρώτη τεχνική είναι γενικευμένη και αντιμετωπίζει την περίπτωση όπου η εφαρμογή της μεθόδου αποσύνθεσης Benders σε ένα πρόβλημα ΜΑΓΠ οδηγεί σε ένα υποπρόβλημα που περιλαμβάνει ακέραιες μεταβλητές. Σε αυτήν την περίπτωση, δεν είναι δυνατή η εφαρμογή του κλασικού αλγορίθμου Benders και, για το λόγο αυτό, προτείνεται ένας αλγόριθμος Branch-and-Cut. Οι περιορισμοί ακεραιότητας του υποπροβλήματος χαλαρώνουν και ο αλγόριθμος Benders εφαρμόζεται σε ένα πλαίσιο Branch-and-Bound. Οι τομές Benders που δημιουργούνται σε έναν κόμβο του δέντρου Branch-and-Bound αποδεικνύεται ότι είναι έγκυρες για όλους τους απόγονους κόμβους. Αυτές οι τομές, που αναφέρονται ως «Τοπικές Τομές», μπορούν να χρησιμοποιηθούν στην αρχικοποίηση του κύριου προβλήματος κάθε απόγονου κόμβου, οδηγώντας έτσι σε καλύτερα αρχικά όρια. Επιπλέον, παρουσιάζεται ένας καινοτόμος τρόπος για τον ορισμό των «Τοπικών Τομών» σε μια γενική μορφή («Γενικευμένες / Καθολικές Τομές»), προσφέροντας τη δυνατότητα επαναχρησιμοποίησής τους σε ολόκληρο το δέντρο Branch-and-Bound. Ο προτεινόμενος αλγορίθμος εφαρμόζεται στο κλασικό Πρόβλημα Capacitated Fixed Charge Multiple Knapsack (CFCMK) και προσφέρει σημαντική μείωση του υπολογιστικού χρόνου σε σύγκριση με τον αντίστοιχο αλγόριθμο χωρίς «Τοπικές Τομές». Η δεύτερη τεχνική αφορά το Πρόβλημα Τοποθεσιών Μέγιστης Κάλυψης (ΠΤΜΚ). Συγκεκριμένα, προτείνεται ένα Μοντέλο Double-type Double-standard (DtDsM), με εφαρμογή στον προσδιορισμό της βέλτιστης τοποθεσίας των δημόσιων υπηρεσιών έκτακτης ανάγκης (π.χ. ασθενοφόρα, πυροσβεστικά και αστυνομικά οχήματα). Στο DtDsM εξετάζονται δύο τύποι οχημάτων: τα κανονικά και τα εφεδρικά οχήματα. Τα κανονικά οχήματα προσφέρουν πλήρη εξυπηρέτηση, αλλά έχουν μικρή απόσταση κάλυψης σε προκαθορισμένο χρόνο, ενώ τα εφεδρικά έχουν μεγαλύτερη απόσταση κάλυψης, αλλά προσφέρουν μόνο μια βασική εξυπηρέτηση. Κάθε σημείο ζήτησης πρέπει να βρίσκεται εντός της απόστασης κάλυψης ενός εφεδρικού οχήματος, εάν δεν βρίσκεται εντός της απόστασης κάλυψης ενός κανονικού οχήματος, διασφαλίζοντας ότι λαμβάνει τις ελάχιστες βασικές υπηρεσίες. Για τη λύση του DtDsM για το ΠΤΜΚ προτείνεται ένας επιταχυνόμενος αλγόριθμος αποσύνθεσης Benders, βασισμένος στην αξιοποίηση της ειδικής δομής του προβλήματος. Ο προτεινόμενος αλγόριθμος ξεπερνά τόσο το εμπορικό λογισμικό βελτιστοποίησης CPLEX όσο και τον κλασικό αλγόριθμο Benders, αναφορικά με την ταχύτητα και την ακρίβεια. Η τρίτη τεχνική είναι μια γενικευμένη, που στοχεύει στην παραγωγή πιο αποτελεσματικών τομών εφικτότητας και βελτιστότητας Benders, προκειμένου να μειωθεί η διακύμανση του ορίου και να επιταχυνθεί ο αλγόριθμος. Το κύριο πλεονέκτημα της προτεινόμενης τεχνικής είναι ότι μπορεί να χρησιμοποιηθεί εύκολα σε κάθε πρόβλημα του Μαθηματικού Προγραμματισμού, όπου εφαρμόζεται η αποσύνθεση Benders, χωρίς κανέναν περιορισμό. Τέσσερις διαφορετικές παραλλαγές του προτεινόμενου αλγορίθμου εφαρμόζονται σε ένα Μαθηματικό Μοντέλο Προγραμματισμού Μεταφοράς Αργού Πετρελαίου και προκύπτουν υποσχόμενα αποτελέσματα από υπολογιστικής άποψης. Τέλος, η τέταρτη τεχνική αφορά το Πρόβλημα Δρομολόγησης Οχημάτων με Πολλαπλές Διαδρομές, Ταχύτητα Εξαρτώμενη από το Χρόνο και Χρονικά Παράθυρα, το οποίο είναι ένα δύσκολο πρόβλημα που αντιμετωπίζουν καθημερινά οι εταιρείες logistics που δραστηριοποιούνται στα αστικά κέντρα. Συγκεκριμένα, προτείνεται μια αναδιαμόρφωση ενός μοντέλου της βιβλιογραφίας, με σκοπό τη μείωση του μεγέθους του. Στην εν λόγω αναδιαμόρφωση εφαρμόζεται η μέθοδος αποσύνθεσης Benders με αποτελεσματικό τρόπο, με αποτέλεσμα το υποπρόβλημα που προκύπτει να μην έχει χάσμα δυϊκότητας. Με την αξιοποίηση των ιδιαίτερων χαρακτηριστικών του προβλήματος, εισάγονται αρκετές νέες έγκυρες ανισώσεις, προκειμένου να περιοριστεί το χαλαρό κύριο πρόβλημα και να επιτευχθούν λιγότερες μη εφικτές λύσεις και καλύτερα κατώτερα όρια. Για τη λύση του προβλήματος, προτείνεται ένας καινοτόμος αλγόριθμος που περιλαμβάνει υποβέλτιστες κύριες λύσεις και μια διαδικασία παραγωγής πολλαπλών τομών, η οποία βασίζεται στην προσεκτική παρατήρηση των τιμών των μεταβλητών του δυϊκού υποπροβλήματος Benders. Δύο παραλλαγές του προτεινόμενου επιταχυνόμενου αλγορίθμου αποσύνθεσης Benders εφαρμόζονται σε δεδομένα συγκριτικής αξιολόγησης και εμφανίζουν βελτιωμένη απόδοση και ισχυρότερα όρια από τα μη αποσυντιθέμενα μοντέλα.