National Technical University of Athens (NTUA)
Αλγόριθμοι σχεδίασης δικτύων τοπολογίας δέντρου με ποικίλους περιορισμούς χωρητικότητας
Abstract
dc:descriptionDesigning 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.
Degree
thesis:*- Grantor dc:publisher
- National Technical University of Athens (NTUA)
- Year dc:date
- 2013
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Pappas, Christos
- Παππάς, Χρίστος
Subjects
dc:subject × 16- Σχεδίαση δικτύων
- Δέντρα επικάλυψης ελάχιστου κόστους
- Συνδυαστική βελτιστοποίηση
- Μεικτός ακέραιος γραμμικός προγραμματισμός
- Ευρετικοί αλγόριθμοι
- Εξελικτικοί αλγόριθμοι
- Network desig
- Minimum cost spanning trees
- COMBINATORIAL OPTIMIZATION
- Mixed integer linear programming
- Heuristics
- Evolutionary algorithms
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Natural Sciences
- Computer and Information Sciences
Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/39568