Bi-criteria network optimization: problems and algorithms

Several approaches, exact and heuristics, have been designed in order to generate the Pareto frontier for multi-objective combinatorial optimization problems. Although several classes of standard optimization models have been studied in their multi- objective version, there still exists a big gap between the solution techniques and the complexity of the mathematical models that derive from the most recent real world applications. In this thesis such aspect is highlighted with reference to a specific application field, the telecommunication sector, where several emerging optimization problems are characterized by a multi-objective nature. The study of some of these problems, analyzed and solved in the thesis, has been the starting point for an assessment of the state of the art in multicriteria optimization with particular focus on multi-objective integer linear programming. A general two-phase approach for bi-criteria integer network flow problems has been proposed and applied to the bi-objective integer minimum cost flow and the bi-objective minimum spanning tree problem. For both of them the two-phase approach has been designed and tested to generate a complete set of efficient solutions. This procedure, with appropriate changes according to the specific problem, could be applied on other bi-objective integer network flow problems. In this perspective, this work can be seen as a first attempt in the direction of closing the gap between the complex models associated with the most recent real world applications and the methodologies to deal with multi-objective programming. The thesis is structured in the following way: Chapter 1 reports some preliminary concepts on graph and networks and a short overview of the main network flow problems; in Chapter 2 some emerging optimization problems are described, mathematically formalized and solved, underling their multi-objective nature. Chapter 3 presents the state of the art on multicriteria optimization. Chapter 4 describes the general idea of the solution algorithm proposed in this work for bi-objective integer network flow problems. Chapter 5 is focused on the bi-objective integer minimum cost flow problem and on the adaptation of the procedure proposed in Chapter 4 on such a problem. Analogously, Chapter 6 describes the application of the same approach on the bi-objective minimum spanning tree problem. Summing up, the general scheme appears to adapt very well to both problems and can be easily implemented. For the bi-objective integer minimum cost flow problem, the numerical tests performed on a selection of test instances, taken from the literature, permit to verify that the algorithm finds a complete set of efficient solutions. For the bi-objective minimum spanning tree problem, we solved a numerical example using two alternative methods for the first phase, confirming the practicability of the approach.