ABSTRACT
Department of Management Science, Lancaster University, Lancaster, United Kingdom
Xavier Gandibleux
Laboratoire d’Informatique de Nantes Atlantique, Universite´ de Nantes, Nantes, France
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 8.2 Definitions and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 8.3 Two Easy Problems: Multi-objective Shortest Path and
Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313 8.4 Nice Problems: The Two-Phase Method . . . . . . . . . . . . . . . . . . . . . . . . 315
8.4.1 The Two-Phase Method for Two Objectives . . . . . . . . . . . . 315 8.4.2 The Two-Phase Method for Three Objectives . . . . . . . . . . 319
8.5 Difficult Problems: Scalarization and Branch and Bound . . . . . . . 320 8.5.1 Scalarization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 8.5.2 Multi-objective Branch and Bound . . . . . . . . . . . . . . . . . . . . . 324
8.6 Challenging Problems: Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 8.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
Mathematical optimization and operations research have, over a period of almost 75 years, contributed tremendously to progress in engineering, finance, medicine, transportation, to name just a few. Combinatorial optimization, which deals with optimization over discrete sets of objects, has been particularly successful in solving many difficult and large-scale planning problems in real-world applications. However, in many real-world decision-making situations, people have to deal with conflicting objectives that need to be optimized
simultaneously. It is therefore evident that multi-objective combinatorial optimization has tremendous potential for contributing to further development of decision support systems built on optimization tools.
