Data di Pubblicazione:
2014
Citazione:
MATHEMATICAL PROGRAMMING ALGORITHMS FOR NETWORK OPTIMIZATION PROBLEMS / F. Colombo ; tutor: M. Trubian ; co-tutor: R. Cordone ; coordinator: G. Naldi. DIPARTIMENTO DI INFORMATICA, 2014 Mar 28. 26. ciclo, Anno Accademico 2013. [10.13130/colombo-fabio_phd2014-03-28].
Abstract:
In the thesis we consider combinatorial optimization problems that are defined by means of networks. These problems arise when we need to take effective decisions to build or manage network structures, both satisfying the design constraints and minimizing the costs.
In the thesis we focus our attention on the four following problems:
- The Multicast Routing and Wavelength Assignment with Delay Constraint in WDM networks with heterogeneous capabilities (MRWADC) problem: this problem arises in the telecommunications industry and it requires to define an efficient way to make multicast transmissions on a WDM optical network. In more formal terms, to solve the MRWADC problem we need to identify, in a given directed graph that models the WDM optical network, a set of arborescences that connect the source of the transmission to all its destinations. These arborescences need to satisfy several quality-of-service constraints and need to take into account the heterogeneity of the electronic devices belonging to the WDM network.
- The Homogeneous Area Problem (HAP): this problem arises from a particular requirement of an intermediate level of the Italian government called province. Each province needs to coordinate the common activities of the towns that belong to its territory. To practically perform its coordination role, the province of Milan created a customer care layer composed by a certain number of employees that have the task to support the towns of the province in their administrative works. For the sake of efficiency, the employees of this customer care layer have been partitioned in small groups and each group is assigned to a particular subset of towns that have in common a large number of activities. The HAP requires
to identify the set of towns assigned to each group in order to minimize the redundancies generated by the towns that, despite having some activities in common, have been assigned to different groups.
Since, for both historical and practical reasons, the towns in a particular subset need to be adjacent, the HAP can be effectively modeled as a particular graph partitioning problem that requires the connectivity of the obtained subgraphs and the satisfaction of nonlinear knapsack constraints.
- Knapsack Prize Collecting Steiner Tree Problem (KPCSTP): to implement a Column Generation algorithm for the MRWADC problem and for the HAP, we need also to solve the two corresponding pricing problems. These two problems are very similar, both of them require to find an arborescence, contained in a given directed weighted graph, that minimizes the difference between its cost and the prizes associated with the spanned nodes. The two problems differ in the side constraints that their feasible solutions need to satisfy and in the way in which the cost of an arborescence is defined. The ILP formulations and the resolution methods that we developed to tackle these two problems have many characteristics in common with the ones used to solve other similar problems.
To exemplify these similarities and to summarize and extend the techniques that we developed for the MRWADC problem and for the HAP, we also considered the KPCSTP. This problem requires to find a tree that minimizes the difference between the cost of the used arcs and the profits of the spanned nodes. However, not all trees are feasible: the sum of the weights of the nodes spanned by a feasible tree cannot exceed a given weight threshold. In the thesis we propose a computational comparison among several optimization methods for the KPCSTP that have been either already proposed in the literature or obtained modifying our ILP formulations for the two previous pricing problems.
- The Train Design Optimization (TDO) problem: this problem was the topic of the
Tipologia IRIS:
Tesi di dottorato
Keywords:
Operations Research ; Network Optimization; Column Generation ; Column and Row Generation
Elenco autori:
F. Colombo
Link alla scheda completa:
Link al Full Text: