Multiple objective optimization and implications for single objective optimization

Taking the right decisions is one of the main aspects in everyday life. If a decision has to be made with respect to only a single criterion, it is often quite simple to find a satisfactory solution for the problem. However, only in rare cases important decisions are influenced by a single criterion. Often several independent and conflicting aspects have to be taken into account. Based on these different criteria, one is faced with the problem to find the ‘‘best’’ alternative among many possible decisions. This idea leads to the concept of multiple objective optimization, where optimality a of feasible solution is defined based on the Pareto-concept. In more detail, a solution of such a problem is called efficient, when there does not exist any other solution that is as good as the given one in all considered criteria and strictly better in at least one criterion. While traditionally, methods from single objective optimization are used to determine efficient solutions of a given multiple objective problem, the reverse approach is taken in this book. In more detail, it is discussed how ideas from multiple objective optimization can be used to solve single objective problems, mainly focusing on two different aspects. On the one hand, solution concepts from multiple objective optimization are used to directly derive optimal solutions for single objective problems in the context of combinatorial optimization. On the other hand, improved versions of existing solution concepts for single objective problems are presented that exploit additional information induced by a multiple objective description of the considered single objective problem. In this context, problems from biconvex optimization are discussed in further detail. In addition to this main topic several related aspects, especially from the field of (multiple objective) combinatorial optimization are discussed. For example, the connectedness of the efficient set for combinatorial problems like the shortest-path, the assignment or the knapsack problem is investigated. From a theoretical point of view the connectedness of efficient solutions is a powerful property since it allows the construction of the complete efficient set using simple neighborhood search techniques. It is shown in this book that the efficient set is non-connected for many classes of combinatorial problems but that there exist special versions of matroid and knapsack problems that satisfy this property.