Συγγραφέας: Αραβαντινού Άννα
Λέξεις Κλειδιά: Πιθανοτική ικανοποιησιμότητα, Ικανοποιησιμότητα μέγιστη, Υπολογιστική πολυπλοκότητα, Συχνά στοιχειοσύνολα, Γραμμικός προγραμματισμός, Προσεγγιστικοί αλγόριθμοι

Σύνοψη: Στην εργασία αυτή ασχοληθήκαμε με το πρόβλημα της Πιθανοτικής Ικανοποιησιμότητας. Παρουσιάσαμε ανάλυση της πολυπλοκότητας του προβλήματος και το επιλύσαμε με την βοήθεια του λογισμικού πακέτου CPLEX. Περιγράψαμε προσεγγιστικούς αλγόριθμους για το πρόβλημα της Μέγιστης Ικανοποιησιμότητας που χρησιμοποιείται στην διαδικασία της Column Generation. Τέλος, πριγράψαμε το αντίστροφο πρόβλημα των συχνών στοιχειοσυνόλων και την σχέση του με το πρόβλημα της Μέγιστης Ικανοποιησιμότητας.

Αρχείο Διπλωματικής Εργασίας