Ακέραιος προγραμματισμός

Abstract

Ο ακέραιος προγραμματισμός (integer programming), ο οποίος εξετάζεται, όπως και ο γραμμικός, αποτελεί κλάδο του μαθηματικού προγραμματισμού (mathematical programming). Ο ακέραιος προγραμματισμός χρησιμοποιείται σε διάφορες εφαρμογές όπως: Παράλληλη εκτέλεση εργασιών, Χρονοπρογραμματισμός (scheduling), Ανάθεση πόρων (resource allocation), Πρόβλημα k-βασιλισσών, Τηλεπικοινωνίες. Μέσα από αυτή τη μεταπτυχιακή διατριβή θα δοθεί η δυνατότητα της εκτενούς ανάλυσης πολύ γνωστών και ευρείας χρήσης αλγορίθμων, όπως επίσης και παραδειγμάτων που αφορούν προβλήματα ακέραιου προγραμματισμού. Πιο συγκεκριμένα, αντικείμενο μελέτης μας θα είναι οι παρακάτω αλγόριθμοι: Branch and Bound, Cutting-planes, Lagrangian relaxation, Benders decomposition και Heuristics. Εκτός αυτού θα εξεταστούν μερικά πρότυπα χρήσης του ακέραιου προγραμματισμού. Λόγω πολυπλοκότητας, θα γίνει αναφορά σε περιοχές που ο προγραμματισμός ακεραίων αριθμών έχει διαδραματίσει σημαντικό ρόλο όπως (αναφορικά): Κύρια σύνταξη προϋπολογισμού, Τοποθεσία των αποθηκών των εμπορευμάτων