Αλγόριθμοι σχεδίασης δικτύων τοπολογίας δέντρου με ποικίλους περιορισμούς χωρητικότητας

Abstract

Designing centralized networks often involves finding minimum cost spanning trees. One of the well-known problems that have been examined extensively in the literature is the Capacitated Minimum Spanning Tree (CMST) problem. In the CMST problem we are given a set of terminal nodes producing constant traffic that must be transferred to a central node. The goal is to design a minimum cost tree network where the flow on each link shall not exceed a predefined capacity. However, in many real world cases links of different capacities may be provided. A generalization of the CMST problem which considers a set of different types of links, each with its own capacity and cost, has been introduced as the Multi-Level Capacitated Minimum Spanning Tree (MLCMST) problem. To this day, research on the MLCMST problem has been restricted to a specific class of instances involving unary traffic demands and low maximum capacity values. The goal of the present thesis is to study the MLCMST problem and suggest algorithms addressing a variety of problem instances. At first, mixed integer linear programming techniques are applied and restricted size instances are solved to optimality within reasonable time limits. Since the MLCMST problem is NP-complete, the effort regarding larger problems is shifted to finding good, but not necessarily optimal, solutions. Based on work previously done in the field, upgrade heuristics are presented, addressing a variety of instances. In addition, the proposed heuristics are integrated with the Branch and Cut algorithm of a popular optimization package. Finally, the application of evolutionary algorithms on the MLCMST problem is examined. Heuristic solutions are used as seeds at the initialization phase of the evolutionary populations.

Κατά τη σχεδίαση κεντρικοποιημένων δικτύων συχνά προκύπτει η ανάγκη για τη εύρεση δέντρων ελάχιστου κόστους. Ένα πρόβλημα που έχει μελετηθεί εκτενώς στη βιβλιογραφία είναι το πρόβλημα εύρεσης Ελάχιστου Δέντρου Επικάλυψης με Περιορισμό Χωρητικότητας (Capacitated Minimum Spanning Tree ή CMST). Στο πρόβλημα CMST στόχος είναι να σχεδιαστεί δίκτυο τοπολογίας δέντρου ελάχιστου κόστους, το οποίο να εξυπηρετεί την προώθηση της κίνησης που παράγει ένα σύνολο τερματικών κόμβων προς ένα κεντρικό κόμβο, με τον περιορισμό η συνολική κίνηση σε οποιαδήποτε ζεύξη να μην υπερβαίνει μία ενιαία προκαθορισμένη τιμή-χωρητικότητα. Ωστόσο, κατά τη σχεδίαση πραγματικών δικτύων συχνά επιλέγεται η εγκατάσταση ζεύξεων διαφορετικών χωρητικοτήτων. Γενικεύοντας το πρόβλημα CMST, έτσι ώστε να υπάρχει η δυνατότητα επιλογής από μία γκάμα διαφορετικών τύπων ζεύξεων, οι οποίοι διαφοροποιούνται μεταξύ τους ως προς τη χωρητικότητα αλλά και το κόστος, οδηγούμαστε στο πρόβλημα εύρεσης Ελάχιστου Δέντρου Επικάλυψης με Περιορισμούς Χωρητικότητας Πολλαπλών Επιπέδων (Multi-Level Capacitated Minimum Spanning Tree ή MLCMST). Η έρευνα γύρω από το πρόβλημα MLCMST είχε μέχρι σήμερα περιοριστεί σε μία συγκεκριμένη κλάση στιγμιότυπων όπου η παραγόμενη από κάθε κόμβο κίνηση είναι μοναδιαία αλλά και η μέγιστη επιτρεπτή χωρητικότητα λαμβάνει χαμηλές τιμές.Η παρούσα διδακτορική διατριβή έχει ως αντικείμενο τη μελέτη του προβλήματος MLCMST και την ανάδειξη αλγορίθμων που να αντιμετωπίζουν ένα ευρύ φάσμα στιγμιότυπων του. Αρχικά εξετάζεται η δυνατότητα επίλυσης προβλημάτων με τεχνικές μεικτού ακέραιου γραμμικού προγραμματισμού. Η πλήρης επίλυση των γραμμικών μοντέλων μέσα σε λογικά χρονικά πλαίσια αποδεικνύεται δυνατή μόνο για στιγμιότυπα περιορισμένου μεγέθους. Σε μεγαλύτερα προβλήματα, και δεδομένου ότι το πρόβλημα MLCMST ανήκει στη κλάση των NP-complete προβλημάτων, η προσπάθεια αναπόφευκτα μετατοπίζεται στην εύρεση ποιοτικών, αλλά όχι απαραίτητα βέλτιστων λύσεων. Βασιζόμενοι σε προηγούμενες εργασίες στον τομέα παρουσιάζουμε ευρετικούς αλγορίθμους αναβαθμίσεων, με στόχο την αντιμετώπιση στιγμιότυπων ποικίλων χαρακτηριστικών και μεγεθών. Εν συνεχεία, οι προτεινόμενοι αλγόριθμοι αναβαθμίσεων ενσωματώνονται σε αλγόριθμο Διακλάδωσης και Αποκοπής (Branch and Cut) δημοφιλούς πακέτου βελτιστοποίησης. Τέλος, εξετάζεται η εφαρμογή εξελικτικών αλγορίθμων στο πρόβλημα. Σε αυτή την προσέγγιση οι προτεινόμενοι αλγόριθμοι αναβαθμίσεων αξιοποιούνται ως τροφοδότες λύσεων καλής ποιότητας κατά την αρχικοποίηση των πληθυσμών.