Applications of Combinatorial Optimization

Preface

This revised and updated second edition of Applications of Combinatorial Optimization is the third and last volume of the Combinatorial Optimization series. It deals with the applications of combinatorial optimization. These are what fully justify the relevance of this scientific domain and widen its fundamental concepts. The subjects of this volume deal with various and diverse problems, more or less classic, but still relevant today. Its chapters are devoted to various problems such as:

In Chapter 1, the problem of optimizing the rotation of airline crews is dealt with. This problem consists of covering, with minimum cost, all the flights of the company scheduled in a given time window, with teams made up from cockpit personnel (pilots, copilots) and cabin personnel (hostesses, stewards). With a frequency of several days (of the order of one week), each team leaves the base to which it is assigned, carries out a certain number of flights sequentially, and comes back to the base (this is what we call “turnover”). Drawing up the team turnover for an airline is highly restricted by international, national and internal work regulations, and by the availability of resources. Because of this, the problem dealt with in this chapter is particularly difficult to solve.

The aim of Chapter 4, entitled Production Planning, is to highlight some specific models in production planning and management that are very interesting and relevant from a combinatorial optimization point of view. It is structured according to a hierarchical planning approach, and introduces three main themes:

Chapter 5 is devoted to a vast subject – one of the most central to research operations – the problem of goods transportation. The main topics studied here concern both the level of planning of the transport operations and steps in the supply chain. Various subjects are introduced:

Chapter 6 introduces optimization models for transportation planning. The theory and applications of these models are vast and complicated subjects, especially when concerning the transport of passengers in an urban zone or region (applications to the problems of planning the movement of goods are more recent, and rely heavily on the results of passenger transport). A wide variety of econometric and optimization models and methods is used to formulate and calibrate the models. In this chapter, four categories of optimization models are introduced: spatial interaction models, network balancing models, public transport route choices and planning models for multimode, multiproduct goods transportation networks.

In Chapter 7 a model for the design of a telecommunications network is presented that simultaneously computes capacities and routings, two problems that are generally handled separately. First, the main difficulties of this problem are presented and discussed. Next, a mathematical model and an algorithm for its solution are proposed.

In Chapter 2, the problem of task assignment for parallel programs is studied. This problem, one of the most important in parallelism, comes about when we seek to improve the performance of a program run on several machines. Given the heterogeneity of the architectures available, it is impossible to give a model appropriate for all situations (architectures, objectives, program executions, etc.). Because of this, for more than 30 years, a lot of research has tackled several aspects of this problem. The authors of the chapter introduce the different elements to be taken into account in order to model this type of problem, and present a number of results.

Chapter 3 is devoted to a comparison of some valid inequality generation methods for general 0–1 integer problems. The authors compare different valid inequality generation techniques for linear 0–1 programs. The approaches studied include classic techniques (for example “lift & project”), disjunctive programming and “reformulation linearization” techniques. Careful comparisons of the results of calculations are carried out on multidimensional knapsack benchmarks by considering three main criteria: the quality of the generated inequalities measured by the ratio between the two members of the inequality, the quality of the inequalities measured by the reinforcement brought to the continuous relaxation, and, finally, the computation time for the generation of valid inequalities.

Optimization of several aspects of network design problems, presented in Chapter 9, has taken on particular importance in operations research and combinatorial optimization in the last 20 years because of the spectacular growth of computer science and telecommunications and, to a lesser degree, of transportation and production systems. This chapter reviews a large number of methods, tools and results in this domain.

Chapter 10, Network Design Problems: Models and Applications, completes Chapter 9 by introducing a large number of models and applications concerning network synthesis.

Chapter 8 is dedicated to parallel combinatorial optimization and focuses on the history and advances of the parallel solution of one of the most paradigmatic problems in combinatorial optimization: the quadratic assignment problem. Through this problem, we see how classic combinatorial optimization tools are used in parallelism, namely metaheuristics and exact search-tree methods. We also examine several parallelization strategies.

Finally, the problem considered in Chapter 11 is the multicriteria assignment of tasks to heterogenous processors under constraints of capacity and mutual exclusion. This is a generalization of the classic assignment problem by taking into account the mutual exclusion constraints that restrict the assignment possibilities of tasks to processors because of incompatible groups of tasks. These groups are defined with respect to each processor, each processor only being able to process at most one task for the group under consideration. Each processor can usually process a certain number of tasks for zero cost, its capacity being able to increase for marginal nondecreasing costs. Each task must be assigned to one, and only one, processor, with certain “preferences”. These are formalized by means of “dissatisfaction indices”. The quality of an assignment is evaluated via three criteria: the maximum dissatisfaction of tasks, the total dissatisfaction of tasks and the total cost of processing. This chapter provides additional proof of the contribution of combinatorial optimization to the sister domain of operations research and decision making.

Like the other volumes in this set, this book is intended for senior or junior researchers, or even Master’s students. Master’s students will probably need a little basic knowledge of graph theory and mathematical (especially linear) programming, even though the authors have been careful to give definitions of all the concepts they use in their chapters. In any case, to improve his/her knowledge of graph theory, readers are invited to consult a seminal book from one of our gurus, Claude Berge (Graphs and Hypergraphs, North Holland, 1973). For linear programming, there is a multitude of good books that the reader could consult, for example Vašek Chvátal, Linear Programming, W.H. Freeman, 1983, or Michel Minoux, Programmation Mathématique: Théorie et Algorithmes, Dunod, 1983.

For the exciting adventure that the editing of this revised book has been, all my thanks again go firstly to the authors who, despite their many responsibilities and commitments (which is the lot of any university academic), agreed to participate in the book by writing chapters in their areas of expertise and, at the same time, to take part in a very tricky exercise: writing chapters that are simultaneously both educational and high-level science.

For the French version of the handbook, Bruno Escoffier, Chico Della Croce, Hadrien Hugo, Jérôme Monnot, Stratos, my TEXpert brother, Olivier Pottié and Dominique Quadri helped me to solve several problems, dealing with proofreading, translation and LATEX. Thank you guys.

A major part of the three last volumes of the French edition were finalized during my sabbatical at the Computer Science...