Η μέθοδος Branch and Bound στην επίλυση προβλημάτων συνδυαστικής βελτιστοποίησης
(EL)
Πεχλιβανίδου, Κατερίνα-Γκλόρια
aegean
Στην παρούσα διπλωματική εργασία γίνεται ανάλυση της μεθόδου βελτιστοποίησης Branch and Bound, καθώς και η εφαρμογή της σε γνωστό πρόβλημα, το πρόβλημα της τετραγωνικής αντιστοίχισης Quadratic Assignment Problem (QAP).
Αυτή η μέθοδος (ή αλγόριθμος) είναι μία σύγχρονη μέθοδος βελτιστοποίησης. Πέραν της εφαρμογής της μεθόδου, αναλύονται σχολαστικά τα βήματα της, και οι προσαρμογές που πραγματοποιούνται, ανάλογα με τις παραμέτρους του προβλήματος. Η αποτελεσματικότητα της μεθόδου κρίνεται σύμφωνα με τον χρόνο εκτέλεσης της, και την ορθότητα της στην επιστροφή της λύσης.
Το πρόβλημα τετραγωνικής αντιστοίχισης που αναλύεται, αποτελεί ένα υπολογιστικά δύσκολο πρόβλημα. Όσο αυξάνονται οι παράμετροι του προβλήματος αυξάνεται και η δυσκολία του. Έχουν γίνει δοκιμές επίλυσης του προβλήματος με την εφαρμογή διάφορων μεθόδων βελτιστοποίησης, και αποδοτικότερη έως τώρα έχει αποδειχθεί η μέθοδος βελτιστοποίησης Branch and Bound.
