Integrated methods and systems for optimization and decision support

Abstract

First we focus on the multi-index assignment. 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. Results show that these components when employed together reduce the time to optimality or the integrality gap for large instances compared to a commercial solver. Furthermore, this work paves the way towards the development of a DSS, which can facilitate several types of use. 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 metaheuristic algorithm that hierarchically optimizes flexible job-shop scheduling problems, a set of data requirements and the DSS evaluation in real settings. Last, we focus on the the binary multi-dimensional knapsack problem. Here, we describe a new primal-dual method. 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, enhanced by global lifted cover inequalities to improve the upper bound and a new version of the Feasibility Pump heuristic that uses these cuts in the pumping procedure to obtain better and feasible lower bounds.

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