Back to search

National Technical University of Athens (NTUA)

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

Abstract

dc:description

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.

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

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/39568

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Pappas, Christos; Παππάς, Χρίστος. Αλγόριθμοι σχεδίασης δικτύων τοπολογίας δέντρου με ποικίλους περιορισμούς χωρητικότητας. National Technical University of Athens (NTUA), 2013. http://hdl.handle.net/10442/hedi/39568