In decision making processes in complex organizational contexts it is often insufficient to make a decision based on a single criterion and it is more realistic to consider different goals simultaneously, often in conflict with each other. An important class of multi-criteria problems is represented by the multi-objective combinatorial optimization problems, especially on networks, in which all or part of decision variables can assume only integer values and where the criteria and constraints that define the problem are expressed by linear functions. In this project we face a fundamental problem in this area: the bi-objective minimum spanning tree problem occurring in several applications and in particular in telecommunication (TLC) networks, where the spanning tree represents the topological structure ensuring connectivity among all nodes with minimum number of arcs. Currently, the TLC area is willing to adopt more sustainable (that is, less energy consuming) transmission networks (see for example [1], [2], [3], [4] and [5]), and, at best of our knowledge, in literature works modelling simultaneously two criteria (quality of the service and energy consumption) and where the whole Pareto frontier is explored, are not present. Our objective is to design and implement a new solution techniques for finding a complete set of Pareto optimal solutions. The algorithms will be tested on networks taken from real TLC environment.
Energy-efficiency is one of the most challenging research areas in telecommunication networks. Researchers have focused their attention to this problem in several works (see for example [1], [2], [3] and [4]) but, at the best of our knowledge, a bi-objective approach was not considered. Indeed, in the previous works, the energy-saving problems were treated like a single objective mathematical programming model through aggregations of the two criteria that characterize the problem. This led to a single optimal solution which does disregarding other solutions that are equally valid from a mathematical point of view and that could be taken into account from the decision maker. As said, this set is quite large and in most of the cases contains solutions representing the perfect compromise the decision maker is looking for.
Thus, for providing a more useful decision support tool for the telecom operators for choosing their energy saving policy, this project will approach to the problem, cosidering its biobjective nature and designing an exact algorithm able to generate all the possible Pareto optimal solutions.