MATHEMATICAL PROGRAMMING ALGORITHMS FOR NETWORK OPTIMIZATION PROBLEMS

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 second problem solving competition, sponsored in 2011 by the Railway Application Section (RAS) of the Institute for Operations Research and the Management Sciences (INFORMS). We participated to the contest and we won the second prize. After the competition, we continued to work on the TDO problem and in the thesis we describe the improved method that we have obtained at the end of this work. The TDO problem arises in the freight railroad industry. Typically, a freight railroad company receives requests from customers to transport a set of railcars from an origin rail yard to a destination rail yard. To satisfy these requests, the company first aggregates the railcars having the same origin and the same destination in larger blocks, and then it defines a trip plan to transport the obtained blocks to their correct destinations. The TDO problem requires to identify a trip plan that efficiently uses the limited resources of the considered rail company. More formally, given a railway network, a set of blocks and the segments of the network in which a crew can legally drive a train, the TDO problem requires to define a set of trains and the way in which the given blocks can be transported to their destinations by these trains, both satisfying operational constraints and minimizing the transportation costs.