Integer programming — Ακέραιος Προγραμματισμός

Ακέραιος προγραμματισμός (ΑΠ· αγγλ. integer programming, IP) — είναι κλάδος της μαθηματικής βελτιστοποίησης, στον οποίο μελετώνται προβλήματα όπου ορισμένες ή όλες οι μεταβλητές πρέπει να λαμβάνουν μόνο ακέραιες τιμές.

Η πιο μελετημένη ειδική περίπτωση είναι ο ακέραιος γραμμικός προγραμματισμός (ΑΓΠ· αγγλ. integer linear programming, ILP), όπου η αντικειμενική συνάρτηση και οι περιορισμοί είναι γραμμικά. Σε αντίθεση με τον γραμμικό προγραμματισμό, όπου οι μεταβλητές μπορούν να λαμβάνουν οποιεσδήποτε πραγματικές τιμές, η απαίτηση ακεραιότητας καθιστά τα προβλήματα ΑΠ σημαντικά πιο δύσκολα να επιλυθούν.

Ο ακέραιος προγραμματισμός βρίσκει ευρεία εφαρμογή στην οικονομία, την εφοδιαστική, τον προγραμματισμό παραγωγής και σε άλλους τομείς, όπου οι μεταβλητές εκ φύσεώς τους είναι διακριτές (π.χ. ο αριθμός παραγόμενων μονάδων προϊόντος ή ο αριθμός εργαζομένων).

Ορισμός και ορολογία

Το γενικό πρόβλημα ακέραιου γραμμικού προγραμματισμού μπορεί να γραφεί ως εξής:

Να βρεθεί το διάνυσμα $x$, το οποίο:

μεγιστοποιεί (ή ελαχιστοποιεί) $c^{T}x$

υπό τους περιορισμούς:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (όλες οι συνιστώσες του διανύσματος $x$ είναι ακέραιοι αριθμοί)

όπου $x$ — το διάνυσμα μεταβλητών, $c$ και $b$ — διανύσματα, και $A$ — ο πίνακας συντελεστών.

Ανάλογα με τις απαιτήσεις για τις μεταβλητές, διακρίνονται οι εξής τύποι προβλημάτων:

• Καθαρά ακέραιος προγραμματισμός: όλες οι μεταβλητές πρέπει να είναι ακέραιες.
• Μικτός ακέραιος προγραμματισμός (αγγλ. mixed-integer programming, MIP): μόνο ένα μέρος των μεταβλητών πρέπει να είναι ακέραιες.
• Δυαδικός (0-1) προγραμματισμός: οι μεταβλητές λαμβάνουν μόνο τις τιμές 0 ή 1, γεγονός που επιτρέπει την μοντελοποίηση λογικών αποφάσεων τύπου «ναι/όχι».

Βασικές ιδιότητες και πολυπλοκότητα

Υπολογιστική πολυπλοκότητα

Το πρόβλημα ακέραιου γραμμικού προγραμματισμού είναι στη γενική περίπτωση NP-δύσκολο. Αυτό σημαίνει ότι δεν υπάρχει γνωστός αλγόριθμος ικανός να βρει την ακριβή βέλτιστη λύση για ένα αυθαίρετο πρόβλημα ΑΠ σε πολυωνυμικό χρόνο. Η πολυπλοκότητα οφείλεται στη συνδυαστορική φύση του προβλήματος, καθώς ο αριθμός πιθανών ακέραιων λύσεων μπορεί να αυξάνεται εκθετικά με την αύξηση του αριθμού των μεταβλητών.

Σχέση με τον γραμμικό προγραμματισμό (χαλάρωση ΓΠ)

Για οποιοδήποτε πρόβλημα ΑΠ μπορεί να διατυπωθεί η γραμμική χαλάρωσή του — ένα πρόβλημα γραμμικού προγραμματισμού (ΓΠ) στο οποίο έχει απαλειφθεί η απαίτηση ακεραιότητας των μεταβλητών. Η λύση της χαλάρωσης ΓΠ έχει δύο σημαντικές ιδιότητες:

1. Μπορεί να βρεθεί σημαντικά ταχύτερα (σε πολυωνυμικό χρόνο).
2. Η βέλτιστη τιμή της αντικειμενικής συνάρτησης της χαλάρωσης ΓΠ παρέχει εκτίμηση (άνω φράγμα για πρόβλημα μεγιστοποίησης και κάτω για ελαχιστοποίηση) για τη βέλτιστη τιμή του αρχικού ακέραιου προβλήματος.

Ωστόσο, η απλή στρογγυλοποίηση της κλασματικής λύσης της χαλάρωσης ΓΠ στους πλησιέστερους ακέραιους αριθμούς κατά κανόνα δεν οδηγεί σε βέλτιστη ή έστω εφικτή λύση του ακέραιου προβλήματος.

Ιδιότητα πλήρους μονομοδικότητας

Υπάρχει μια σημαντική κατηγορία προβλημάτων ΑΓΠ που επιλύονται εξίσου εύκολα με τις χαλαρώσεις ΓΠ τους. Πρόκειται για προβλήματα στα οποία ο πίνακας περιορισμών $A$ είναι πλήρως μονομοδικός (δηλαδή η ορίζουσα οποιουδήποτε τετραγωνικού υποπίνακά του ισούται με 0, +1 ή −1). Εάν ο πίνακας $A$ είναι πλήρως μονομοδικός και το διάνυσμα $b$ είναι ακέραιο, τότε όλες οι κορυφές του πολυέδρου εφικτών λύσεων της χαλάρωσης ΓΠ θα είναι αυτόματα ακέραιες. Κατά συνέπεια, η λύση που βρίσκεται με τη μέθοδο simplex θα είναι ακέραια. Παραδείγματα τέτοιων προβλημάτων είναι το πρόβλημα μεταφοράς και το πρόβλημα ανάθεσης.

Μέθοδοι επίλυσης

Για την επίλυση γενικών προβλημάτων ΑΠ που δεν διαθέτουν την ιδιότητα πλήρους μονομοδικότητας, έχουν αναπτυχθεί ακριβείς μέθοδοι βασισμένες στην ιδέα της πεπλεγμένης απαρίθμησης.

• Μέθοδος διακλάδωσης και ορίων (αγγλ. Branch and Bound) — η βασική ακριβής μέθοδος, που βασίζεται στη συστηματική διαίρεση του συνόλου εφικτών λύσεων σε υποσύνολα (διακλάδωση) και στην αποκοπή εκείνων των υποσυνόλων που προφανώς δεν περιέχουν τη βέλτιστη λύση. Για την εκτίμηση της υποσχόμενης φύσης των υποσυνόλων χρησιμοποιείται η χαλάρωση ΓΠ.

• Μέθοδος τμημάτων αποκοπής (μέθοδος Gomory· αγγλ. Cutting Plane Method) — επαναληπτική προσέγγιση που προσθέτει διαδοχικά νέους γραμμικούς περιορισμούς («αποκοπές») στο πρόβλημα. Αυτές οι αποκοπές «αποκόπτουν» τις κλασματικές λύσεις της χαλάρωσης ΓΠ χωρίς να θίγουν καμία εφικτή ακέραια λύση, προσεγγίζοντας σταδιακά την περιοχή εφικτών λύσεων της χαλάρωσης ΓΠ προς το κυρτό περίβλημα των ακέραιων λύσεων.

Οι σύγχρονοι επιλύτες χρησιμοποιούν κατά κανόνα υβριδικούς αλγόριθμους, όπως η μέθοδος διακλάδωσης και αποκοπών (αγγλ. Branch and Cut), η οποία συνδυάζει τα πλεονεκτήματα και των δύο προσεγγίσεων.

Παραδείγματα και τομείς εφαρμογής

Ο ακέραιος προγραμματισμός επιτρέπει τη μοντελοποίηση πολλών κλασικών προβλημάτων συνδυαστορικής βελτιστοποίησης.

• Πρόβλημα σακιδίου: κλασικό πρόβλημα 0-1 προγραμματισμού, στο οποίο πρέπει να επιλεγεί σύνολο αντικειμένων με μέγιστη συνολική αξία, χωρίς να υπερβαίνεται ο περιορισμός στο συνολικό βάρος.
• Πρόβλημα του πλανόδιου πωλητή: πρόβλημα εύρεσης της συντομότερης διαδρομής που διέρχεται από ένα δεδομένο σύνολο πόλεων. Μπορεί να διατυπωθεί ως πρόβλημα ακέραιου προγραμματισμού, όπου οι μεταβλητές αντιστοιχούν στη συμπερίληψη ακμών του γράφου στην τελική διαδρομή.

Λόγω της ευελιξίας του, ο ΑΠ αποτελεί ένα από τα πιο ζητούμενα εργαλεία στην επιχειρησιακή έρευνα και βρίσκει εφαρμογή σε τομείς όπως:

• Εφοδιαστική και διαχείριση αλυσίδας εφοδιασμού: βελτιστοποίηση δρομολογίων μεταφοράς, τοποθέτηση αποθηκών, διαχείριση αποθεμάτων.
• Προγραμματισμός παραγωγής: κατάρτιση προγραμμάτων παραγωγής, κατανομή πόρων, φόρτωση εξοπλισμού.
• Χρηματοοικονομικά και οικονομία: διαμόρφωση επενδυτικού χαρτοφυλακίου, κατανομή κεφαλαίων.
• Τηλεπικοινωνίες και ενεργειακός τομέας: σχεδιασμός δικτύων επικοινωνίας, προγραμματισμός λειτουργίας ενεργειακών μονάδων.

Δείτε επίσης

• Γραμμικός προγραμματισμός
• Μέθοδος διακλάδωσης και ορίων

Παραπομπές

</references>