Νέες τεχνικές ανίχνευσης δεσμευτικών περιορισμών σε προβλήματα γραμμικού προγραμματισμού και εφαρμογές

Abstract

In the real world, given the rapidly evolving circumstances that characterize the modern era, in the sectors of life where linear programming problems are met, an endless effort has been conducted by researchers, as well as by scientific organizations and businesses, to resolve them as quickly and as efficiently as possible. More specifically, it has been noticed that only a small part of the initial constraints participates in the optimal solution of the problem. This creates a necessity either to remove the redundant constraints, that do not participate in the optimal solution of those problems from the resolving process, or to locate the binding constraints that contribute to the optimal solution, before the resolution process. Due to the fact though, that the characterization of those constraints may be of increased difficulty, it is possible to use «proximity» techniques which are able to locate the more possible constraints to be classified in each category. Given the increased complexity of these problems, the present thesis focuses on the presentation of five new algorithms. Through the usage of specific prediction criteria, these algorithms are able to characterize the constraints as binding or non-binding, by focusing on the characterization of the binding ones, in order to reduce the dimension of the Linear Programming Problem (LP). This results in speeding up the solving process of the method used, and thus, reduces the resolution cost of the LP problem. Part of the presented algorithms are implemented in randomly created linear programming problems. Another part is implemented in a class of known Netlib problems of the real world, where the number of variables is significantly larger than the number of the constraints. This contrasts with the randomly created linear programming problems, where the opposite applies, while the last part of the remaining algorithms is implemented in the aforementioned cases. For the accomplishment of the classification of the constraints, the presented algorithms make use of a ranking system, which is calculated individually for each algorithm based on a specific criterion, that allows us to «characterize» the constraints as binding or redundant.

Στον πραγματικό κόσμο δεδομένων των ταχέως εξελισσόμενων συνθηκών που επικρατούν τη σημερινή εποχή στους τομείς της καθημερινότητας που άπτονται των Προβλημάτων Γραμμικού Προγραμματισμού, έχει πραγματοποιηθεί μια αδιάκοπη προσπάθεια από την πλευρά των ερευνητών αυτού του είδους των προβλημάτων, καθώς και από επιστημονικούς οργανισμούς και επιχειρήσεις, για την όσο το δυνατόν ταχύτερη και αποτελεσματικότερη επίλυσή τους. Συγκεκριμένα, έχει παρατηρηθεί ότι μόνο ένα μικρό μέρος των αρχικών περιορισμών των προβλημάτων αυτών συμβάλλει στη βέλτιστη λύση του προβλήματος. Η πραγματικότητα αυτή καθιστά επιτακτική ανάγκη είτε την αφαίρεση των μη-δεσμευτικών περιορισμών που δεν συμβάλλουν στη βέλτιστη λύση των προβλημάτων αυτών από τη διαδικασία της επίλυσής τους, είτε τον εντοπισμό των δεσμευτικών περιορισμών, οι οποίοι συμβάλλουν στη βέλτιστη λύση, πριν από τη διαδικασία επίλυσής τους. Επειδή όμως ο απευθείας χαρακτηρισμός των περιορισμών αυτού του είδους των προβλημάτων σε δεσμευτικούς ή μη μπορεί να είναι αρκετά δύσκολος, κατά τη διάρκεια των ερευνών που πραγματοποιούνται, γίνεται χρήση προσεγγιστικών τεχνικών, οι οποίες ως στόχο έχουν να μπορούν να εντοπίσουν τους πιο πιθανούς για να καταταχθούν σε καθεμία κατηγορία. Δεδομένης της αυξημένης πολυπλοκότητας αυτών των προβλημάτων, στην παρούσα διατριβή παρουσιάζονται πέντε νέοι αλγόριθμοι, οι οποίοι ως στόχο έχουν να κατατάξουν τους περιορισμούς δίνοντας προτεραιότητα σε αυτούς που είναι πιθανότερο να είναι δεσμευτικοί. Αυτό δύναται να συνεισφέρει στην επιτάχυνση μιας μεθόδου επίλυσης ενός Προβλήματος Γραμμικού Προγραμματισμού και κατά επέκταση στη μείωση του κόστουςεπίλυσης του προβλήματος.Κάποιοι από τους αλγόριθμους που παρουσιάζονται εφαρμόζονται σε τυχαίαδημιουργημένα Προβλήματα Γραμμικού Προγραμματισμού (random LP problems), στα οποία το πλήθος των περιορισμών είναι πολύ μεγαλύτερο από το πλήθος των μεταβλητών. Κάποιοι άλλοι αλγόριθμοι, εφαρμόζονται σε ένα σύνολο γνωστών Netlib προβλημάτων του πραγματικού κόσμου, όπου το πλήθος των μεταβλητών είναι κατά πολύ μεγαλύτερο σε σχέση με το πλήθος των περιορισμών, σε αντίθεση με τα τυχαία δημιουργημένα προβλήματα. Τέλος, κάποιοι από τους αλγόριθμους εφαρμόζονται και στις δύο προαναφερθείσες κατηγορίες, δηλαδή και σε Random προβλήματα και σε προβλήματα Netlib. Για την πραγματοποίηση της κατηγοριοποίησης των περιορισμών,οι αλγόριθμοι που παρουσιάζονται κάνουν χρήση μιας σειράς κατάταξης, η οποία παράγεται σε κάθε αλγόριθμο με τη χρήση κάποιου συγκεκριμένου κριτηρίου, βάσει της οποίας είναι σε θέση να χαρακτηρίσουν τους περιορισμούς ως πιθανότερους ή όχι για να είναι δεσμευτικοί.