Μοντελοποίηση και Προγραμματισμός Περιορισμών

Μοντέλα περιορισμών και εφαρμογές.  Δίκτυα περιορισμών: βασικό πλαίσιο, ορισμοί. Γραφήματα περιορισμών. Διάδοση και εξαγωγή συμπερασμάτων –επίλυση. Συνέπεια δικτύου: συνέπεια ακμής, μονοπατιού, k-συνέπεια, γενικευμένη συνέπεια, καθολικοί περιορισμοί. Κατευθυνόμενη συνέπεια και επαγώμενο βάθος γραφήματος. Προσαρμοσμένη συνέπεια. Στρατηγικές εξερεύνησης του χώρου των λύσεων. Εξερεύνηση προς τα εμπρός,  επιλογή μεταβλητής  και τιμής. Οπισθοδρόμηση και αναπήδηση προς τα πίσω. Περιορισμοί και βελτιστοποίηση: η δηλωτική δύναμη του ακέραιου προγραμματισμού. Μοντέλα και εφαρμογές. Βασικές έννοιες και εισαγωγή στη θεωρία κυρτότητας: διάσταση και όψεις πολυέδρων. Αλγόριθμοι κλάδου και φράγματος, επιπέδων τομών και έμμεσης απαρίθμισης. Εισαγωγή στη συνδυαστική βελτιστοποίηση.

Βιβλιογραφία

• Rina Drechter, Constraint processing, Morgan Kaufmann, 2003
• Hooker, Logic-based methods for optimization, John Wiley, 2000.
• Schrijver, Theory of Integer and Linear Programming, John Wiley,