M119.CS Θεωρία Γραμμικού Προγραμματισμού

ΠΜΣ Πληροφορική (M119.CS) -- ΑΛΜΑ
Τμήμα Πληροφορικής και Τηλεπικοινωνιών
Πανεπιστήμιο Αθηνών
Χειμερινό Εξάμηνο 2024-2025

Γενικές Πληροφορίες

Δημόσια Ιστοσελίδα μαθήματος: http://www.di.uoa.gr/~sgk/teaching/grad/LP/
Εδώ υπάρχουν γενικές πληροφορίες για το μάθημα και οι σημειώσεις. Υπάρχει και σελίδα στο eclass.uoa.gr στην οποία θα πρέπει όλοι οι ενδιαφερόμενοι να εγγραφούν. Εκεί θα δημοσιεύονται οι ανακοινώσεις και οι ασκήσεις του μαθήματος. Για την εγγραφή είναι απαραίτητος λογαριασμός στο ΕΚΠΑ.

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

Δεν απαιτείται προηγούμενη εξοικείωση με γραμμικό ή μη γραμμικό προγραμματισμό, πέρα από συνήθεις γνώσεις αλγορίθμων και γραμμικής άλγεβρας. Tο μάθημα απευθύνεται αποκλειστικά σε μεταπτυχιακούς φοιτητές.

• Κυρτά σύνολα, πολύεδρα, κώνοι, πολύτοπα
• Δυϊκότητα
• Θεώρημα Minkowski-Weyl
• Χαρακτηρισμοί όψεων και εδρών πολυέδρων
• Total unimodularity
• Total dual integrality
• Υπολογιστική πολυπλοκότητα ακέραιου γραμμικού προγραμματισμού
• Δύο σημαντικά πολύτοπα: ταιριάσματα & κατευθυνόμενα δένδρα (arborescences)
• Extended Formulations

• A. Schrijver. Combinatorial Optimization - Polyhedra and Efficiency (Springer-Verlag, Berlin, 2003).
• A. Schrijver. Theory of Linear and Integer Programming (Wiley, 1986)
• W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver. Combinatorial Optimization (Wiley, 1997)
• D. Bertsimas, J. N. Tsitsiklis. Introduction to Linear Optimization (Athena Scientific, 1997)

Πολλές άλλες πηγές κάθε είδους είναι διαθέσιμες στο διαδίκτυο.

Διαδικαστικά

Εξετάσεις - Ασκήσεις - Βαθμολογία: 50% της βαθμολογίας θα προκύψει από ασκήσεις και 50% από παρουσίαση ερευνητικής εργασίας από τη βιβλιογραφία. Τα σετ των ασκήσεων δεν θα είναι απαραίτητα ισοδύναμα, o συνολικός βαθμός στις ασκήσεις θα υπολογιστεί ως (\sum_{i=1}^{N} d_i)/(\sum_{i=1}^{N} t_i), όπου d_i η επίδοση στο iστό σετ, t_i οι συνολικές μονάδες του iστού σετ, και Ν το πλήθος των σετ.

Η παρουσίαση πρέπει να βασίζεται σε διαφάνειες που θα έχουν παραχθεί ηλεκτρονικά. Η διάρκεια της θα είναι μέχρι 45 λεπτά ώστε να υπάρχει χρόνος για ερωτήσεις. Μετά την προφορική παρουσίαση πρέπει να στείλετε στο διδάσκοντα τα εξής αρχεία, αποκλειστικά σε μορφή pdf: 1) το αρχείο με τις διαφάνειες 2) κριτική περίληψη της εργασίας που παρουσιάσατε, το πολύ μέχρι 2 σελίδες χωρίς τις αναφορές 3) την εργασία ή τις εργασίες που παρουσιάσατε.

Δεν θα ανατεθεί παρουσίαση, ούτε θα σταλεί βαθμός για όσους/ες δεν έρχονται τακτικά, κατά την κρίση του διδάσκοντα, στις παραδόσεις ή για όσους/ες δεν συγκεντρώσουν το 60% της συνολικής βαθμολογίας στις ασκήσεις.

Σημειώσεις

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

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

Ασκήσεις