Integrated methods and systems for optimization and decision support

Abstract

This thesis falls within the scope of Combinatorial Optimization and Decision Support Systems (DSS). Its purpose is to introduce algorithmic components for different optimization problems along with a DSS for each problem as further result. Motivated by the so-called integrated methods for optimization, we study three different optimization problems, and present new algorithms that combine the complementary strengths of the three major types of optimization methods, i.e., Mathematical Programming, Constraint Programming and Heuristics. The first problem we focus on, is the multi-index assignment. In this part of work we propose several components that can be employed across different types of assignment, i.e, a constraint propagation mechanism, a tabu-search meta-heuristic, a new variant of the Feasibility Pump heuristic that employs cutting planes, along with a new Branch & Cut method for the problem at hand. The computational experimentation shows that indeed these components when employed together reduce the time to optimality or the integrality gap for large instances where a competitivecommercial solver runs out of memory. An important aspect of this approach is its versatility, for example in terms of including a subset of the selected components or an alternative FP variant as a primal heuristic. Furthermore, the existence of these components in terms of code paves the way towards the development of a DSS for the problem at hand, which can facilitate several types of use, given its general-purpose design and the various applications of the multi-index assignment problem.The second problem is the energy-aware production scheduling. Here, we present an energy-aware production scheduling DSS as designed, implemented and evaluated in a real context. In short, this work contributes to decision support for energy-efficient manufacturing by a meta-heuristic algorithm that hierarchically optimizes flexible job-shop scheduling problems, a set of data requirements, the integrated deployment of this DSS as a web-service and the evaluation of the DSS in real settings. The adopted scheduling framework incorporates various operational issues, while the data entities accompanying it meet generic energy-related requirements, as obtained from the literature and the textile industry. Apart from examining theoretical aspects regarding the design of energy-aware DSS, this work presents the significant tangible benefits obtained from the use of such systems within the textile manufacturing industry. Hence, the applicability of the proposed DSS, as deployed in two significantly different users and production environments, is shown to be both feasible and effective.Last, we focus on the the binary multi-dimensional knapsack problem. Motivated by our research on the multi-index assignment problem and the new variant of the Feasibility pump heuristic that has been designed and tested, we broaden our focus on the multi-dimensional knapsack problem, where its structure is general enough to encompass all binary optimization problems. Here, we describe a new primal-dual method for this problem, which is a strongly NP-hard combinatorial optimization problem with many applications. Current exact approaches and commercial solvers run into difficulties even for a small-to-medium number of constraints and variables. The proposed primal-dual method employs the linear relaxation of the problem at hand, enhanced by global lifted cover inequalities to improve the upper bound and a new version of the Feasibility Pump heuristic that uses this family of inequalities in the pumping procedure to obtain better and feasible lower bounds. Since this is only preliminary work, this new variant of feasibility-pump is tested on literature instances, for a good portion of which there are still no optimal solutions available. The results of the heuristic are interesting enough to trigger further research and development for the proposed primal-dual method.The contribution of this effort, given that we focus on two such large research areas, is multi-fold. Intuitively, an optimization algorithm on its own is not a DSS, while a DSS without an efficient algorithm cannot support efficiently decision making. The examination of different optimization problems in terms of structure and applications, has motivated the generation of quite diverse integrated optimization methods, while for the two of the problems two DSS have been developed and tested, with one of these in a real and demanding context. Given that there are various choices of algorithmic components towards optimization, this thesis could shed some light on the design of efficient optimization algorithms given the structure and the applications of the problem, while also demonstrating the use and study of such algorithms not only from a computational or analytical perspective, but from a DSS viewpoint.

Η συγκεκριμένη διδακτορική διατριβή εντάσσεται στις ερευνητικές περιοχές της Συνδυαστικής Βελτιστοποίησης και των Συστημάτων Υποστήριξης Αποφάσεων. Δεδομένης της χρήσης μεθόδων βελτιστοποίησης στο χώρο της λήψης αποφάσεων, κίνητρο αυτής της έρευνας είναι η αντιμετώπιση υπαρχόντων προβλημάτων βελτιστοποίησης όχι μόνο από μία αλγοριθμική-μαθηματική σκοπιά, αποτέλεσμα της οποίας είναι μία αλγοριθμική μέθοδος ή ένα νέο μαθηματικό μοντέλο, αλλά και από τη χρήση των παραπάνω, μέσα από κάποιο πληροφοριακό σύστημα υποστήριξης αποφάσεων. Αποτέλεσμα μίας τέτοιας προσπάθειας αναμένεται να είναι κάποιος νέος αλγόριθμος βελτιστοποίσης, συμπεριλαμβανομένων των δεδομένων, των περιπτώσεων χρήσης και της αρχιτεκτονικής που απαιτούνται ως μέρος ενός ολοκληρωμένου συστήματος που θα έθετε σε εφαρμογή κάποιος χρήστης. Η διατριβή αρχικά παρουσιάζει το θεωρητικό υπόβαθρο και τις εφαρμογές τριών διαφορετικών προβλημάτων βελτιστοποίησης. Για το κάθε ένα παρουσιάζεται το μαθηματικό μοντέλο και μία μέθοδος βελτιστοποίησης ενώ για δύο από αυτά περιγράφεται η ανάλυση, ο σχεδιασμός και τα αποτελέσματα χρήσης ενός συστήματος υποστήριξης αποφάσεων που υλοποιήθηκε για αυτά. Τα βήματα της ανάλυσης και του σχεδιασμού περιλαμβάνουν τις περιπτώσεις χρήσης, το μοντέλο δεδομένων καθώς και την αρχιτεκτονική του κάθε συστήματος. Πιο αναλυτικά, τα προβλήματα αυτά είναι: Προγραμματισμός εργασιών παραγωγής λαμβάνοντας υπόψη ενεργειακά κριτήρια (Energy-aware production scheduling). Για το εν λόγω πρόβλημα παρουσιάζονται ένας μετα-ευρετικός αλγόριθμος (του οποίου ο σχεδιασμός και ανάπτυξη δεν αποτελούν μέρος της διατριβής) μαζί με τις απαιτήσεις χρηστών όπως συλλέχθηκαν από τη βιβλιογραφία και από το χώρο της παραγωγής υφασμάτων, μαζί με τα απαραίτητα δεδομένα και την αρχιτεκτονική του συστήματος που χρησιμοποιεί τον αλγόριθμο αυτό. Το τελικό σύστημα δοκιμάστηκε σε δύο διαφορετικά εργοστάσια παραγωγής υφασμάτων στην Ευρώπη και παρουσιάζονται τα οφέλη σε ενεργειακό κόστος από τη χρήση του συτήματος καθώς και η αξιολόγηση της χρηστικότητας ενός τέτοιου συστήματος.Πολυδιάστατη αντίστοιχιση (Multi-index assignment). Για το εν λόγω πρόβλημα παρουσιάζονται τέσσερις ακριβείς (exact) αλγόριθμοι που δεν υπάρχουν στην βιβλιογραφία, έξι υπάρχοντες ευρεστικοί αλγόριθμοι για μικτό ακέραιο προγραμματισμό (Mixed-Integer Programming) πάνω στους οποίους δοκιμάστηκαν 'επίπεδα αποκοπής' (cutting planes) οδηγώντας στην παραγωγή τριών νέων εκδόσεων των αλγορίθμων αυτών καθώς κι ένας ευρετικός αλγόριθμος που επίσης δεν υπάρχει στη βιβλιογραφία. Για κάθε έναν από αυτούς τους αλγορίθμους παρουσιάζονται πειραματικά αποτελέσματα. Δεδομένων των πολλαπλών εφαρμογών που έχει το πρόβλημα της πολυδιάστατης αντιτοίχισης και σε συνέχεια αυτής της έρευνας, παρουσιάζεται ένα σύστημα που περιλαμβάνει κάποιους από αυτούς τους αλγορίθμους, μαζί με τις περιπτώσεις χρήσης, το μοντέλο δεδομένων και την αρχιτεκτονική που χτίζουν ένα τέτοιο σύστημα υποστήριξης αποφάσεων.Πολυδιάστατο δυαδικό πρόβλημα σακιδίου (Multi-dimensional binary knapsack). Για το εν λόγω πρόβλημα δοκιμάστηκαν τρεις υπάρχουσες εκδόσεις ενός αλγορίθμου για μικτό ακέραιο προγραμματισμό (Mixed-Integer Programming) καθώς και μία συγκεκριμένη οικογένεια επιπέδων αποκοπής (cutting planes), ο συνδυασμός των οποίων δοκιμάστηκε πειραματικά. Τα αποτελέσματα αυτών των πειραμάτων οδήγησαν με τη σειρά τους στον σχεδιασμό ενός νέου ακριβή (exact) αλγορίθμου.