Applications of Combinatorial Optimization E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 758

Veröffentlichungsjahr: 2014

Beschreibung

Combinatorial optimization is a multidisciplinary scientific area, lying in the interface of three major scientific domains: mathematics, theoretical computer science and management. The three volumes of the Combinatorial Optimization series aim to cover a wide range of topics in this area. These topics also deal with fundamental notions and approaches as with several classical applications of combinatorial optimization. Concepts of Combinatorial Optimization, is divided into three parts: - On the complexity of combinatorial optimization problems, presenting basics about worst-case and randomized complexity; - Classical solution methods, presenting the two most-known methods for solving hard combinatorial optimization problems, that are Branch-and-Bound and Dynamic Programming; - Elements from mathematical programming, presenting fundamentals from mathematical programming based methods that are in the heart of Operations Research since the origins of this field.

Leseprobe

Table of Contents

Preface

Chapter 1 Airline Crew Pairing Optimization

1.1. Introduction

1.2. Definition of the problem

1.3. Solution approaches

1.4. Solving the subproblem for column generation

1.5. Conclusion

1.6. Bibliography

Chapter 2 The Task Allocation Problem

2.1. Presentation

2.2. Definitions and modeling

2.3. Review of the main works

2.4. A little-studied model

2.5. Conclusion

2.6. Bibliography

Chapter 3 A Comparison of Some Valid Inequality Generation Methods for General 0–1 Problems

3.1. Introduction

3.2. Presentation of the various techniques tested

3.3. Computational results

3.4. Bibliography

Chapter 4 Production Planning

4.1. Introduction

4.2. Hierarchical planning

4.3. Strategic planning and productive system design

4.4. Tactical planning and inventory management

4.5. Operations planning and scheduling

4.6. Conclusion and perspectives

4.7. Bibliography

Chapter 5 Operations Research and Goods Transportation

5.1. Introduction

5.2. Goods transport systems

5.3. Systems design

5.4. Long-distance transport

5.5. Vehicle routing problems

5.6. Exact models and methods for the VRP

5.7. Heuristic methods for the VRP

5.8. Conclusion

5.9. Appendix: metaheuristics

5.10. Bibliography

Chapter 6 Optimization Models for Transportation Systems Planning

6.1. Introduction

6.2. Spatial interaction models

6.3. Traffic assignment models and methods

6.4. Transit route choice models

6.5. Strategic planning of multimodal systems

6.6. Conclusion

6.7. Bibliography

Chapter 7 A Model for the Design of a Minimum-cost Telecommunications Network

7.1. Introduction

7.2. Minimum cost network construction

7.3. Mathematical model, general context

7.4. Proposed algorithm

7.5. Critical points

7.6. Conclusion

7.7. Bibliography

Chapter 8 Parallel Combinatorial Optimization

8.1. Impact of parallelism in combinatorial optimization

8.2. Parallel metaheuristics

8.3. Parallelizing tree exploration in exact methods

8.4. Conclusion

8.5. Bibliography

Chapter 9 Network Design Problems: Fundamental Methods

9.1. Introduction

9.2. The main mathematical and algorithmic tools for network design

9.3. Models and problems

9.4. The STEINER-EXTENDED problem

9.5. Conclusion

9.6 Bibliography

Chapter 10 Network Design Problems: Models and Applications

10.1. Introduction

10.2. Models and location problems

10.3. Routing models for telecommunications

10.4. The design or dimensioning problem in telecommunications

10.5. Coupled flows and multiflows for transport and production

10.6. A mixed network pricing model

10.7. Conclusion

10.8. Bibliography

Chapter 11 Multicriteria Task Allocation to Heterogenous Processors with Capacity and Mutual Exclusion Constraints

11.1. Introduction and formulation of the problem

11.2. Modeling the set of feasible assignments

11.3. The concept of a blocking configuration and analysis of the unblocking means

11.4. The multicriteria assignment problem

11.5. Exploring a set of feasible non-dominated assignments in the plane g2 × g3

11.6. Numerical example

11.7. Conclusion

11.8. Bibliography

General Bibliography

List of Authors

Index

First edition published 2010 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.© ISTE Ltd 2010First published 2014 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

www.iste.co.uk

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.wiley.com

© ISTE Ltd 2014The rights of Vangelis Th. Paschos to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Control Number: 2014942905

British Library Cataloguing-in-Publication DataA CIP record for this book is available from the British LibraryISBN 978-1-84821-658-7

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:

– airline crew scheduling;

– transport of goods and planning;

– scheduling of tasks in parallel programming;

– applications of polyhedral combinatorics;

– production planning;

– modeling and optimization of network synthesis and design problems;

– parallel optimization;

– multicriteria task assigning to heterogenous processors, and its robustness.

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:

– strategic planning and productive system design;

– tactical production planning and inventory control;

– operational production planning and scheduling.

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:

– important models of transport and logistics systems conception, deployed on a large (region, country, world) or small (district, city, region) scale;

– models for designing service networks, as well as models aiming to manage fleets;

– the vehicle routing problem; this is a central transport, distribution and logistics problem, also linked to operational car fleet management; more specifically, the authors deal with three main variants of this problem: capacity constraints, length and capacity constraints, and time windows; the main models for these variants as well as exact and heuristic approaches for these models are presented.

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 departments of the University of Athens and of Athens University of Economics and Business. Elias Koutsoupias and Vassilis Zissimopoulos, on the one hand, and Giannis Milis, on the other, invited and welcomed me and put at my disposal all the available means and resources I needed to work efficiently. To them, I would once again like to express my warmest thanks and my humblest gratitude and friendship.

This work could never have come into being without the initial proposal of Jean-Charles Pomerol, President of the scientific board at ISTE, and Sami Ménascé, President of ISTE. I give my warmest thanks to them for their insistence and encouragement. I would also like to thank Raphael Ménascé, Vice-President of ISTE, for his kindness and his patience. While I was already friends with Jean-Charles, editing this work made me three more friends: Chantal, Sami and Raphael. I hope our collaboration will continue. It is a pleasure for me to work with them.

As with the first edition, I would like to finish this Preface on a personal note concerning two losses that touched our scientific community. Between April 2002, when the writing of the original French edition of the handbook started, and today, the international community of operations research and combinatorial optimization lost two of its greatest spiritual fathers: Claude Berge and Peter Hammer. They were both great scientists in discrete mathematics and combinatorial optimization.

Claude Berge was the president of the committee of my habilitation thesis. I will always remember our discussions, in his office at the EHESS, on mathematics, on American detective novels from the first half of the 20th Century, and on OULIPO, of which I learned the history through the Greek literary magazine Λ ξη when I was still a student at the Polytechnic School of Athens.

Peter Hammer was to be one of the authors of both (French and English) editions of the original book. He did not have time to send me his chapter.

In them, we have lost two of the great figures of our discipline. We will always remember them.

Vangelis Th. PASCHOSJune 2014

Chapter 1

Airline Crew Pairing Optimization

1.1. Introduction

In the airline industry, optimizing and automating the building of crew pairings is a major financial and organizational issue. The problem consists of covering all the company’s flights, programmed in a given time window, with teams made up of cockpit personnel (pilots, copilots) and of cabin personnel (stewardesses, stewards) at a minimum cost. With a frequency of several days (in the order of a week), each crew leaves from the base to which it is assigned, carries out a certain number of flights, and comes back to the base. This sequence of flights with a return to the base is called a rotation, or pairing. Drawing up the pairings of an airline company is highly constrained by international, national and internal work regulations, and by the limited availability of resources. These constraints make the problem particularly hard to solve. Besides the gains in terms of organization, security and calculation time, the use of optimization programs and models for this problem allows big companies to make substantial financial gains. It is not unusual for a reduction of 1% in the total cost of the rosters to result in savings of several tens of millions of dollars for big companies [DES 97], which is one reason for the abundant fundamental and applied research on this subject. The general crew pairing problem with resource constraints problem (CPP-RC) can be formulated as a minimum cost multicommodity flow problem with additional variables and resource constraints. Even though in most applications the cost of a rotation is non-linear [DES 97, LAV 88], in this chapter we will restrict ourselves to the case where the cost function is a linear approximation. The ways of constructing a network of feasible pairings, and calculating the cost of the rosters, along with the associated mathematical program, are presented in section 1.2. Section 1.3 gives an overview of classical solution techniques, with a focus on the column generation method, whose associated subproblem is studied in section 1.4. Section 1.5 concludes the chapter.

1.2. Definition of the problem

i) the departure time ;

ii) the arrival time ;

iii) the departure airport ;

iv) the destination airport .

A rotation must start and end at one of the company’s bases. The set of bases is generally made up of large interconnection platforms called hubs. The CPP often has resource constraints on the pairings. In order to take the pairing validity constraints into account, a classical modeling associates a subnetwork, constructed in the following way, with each crew.

1.2.1. Constructing subnetworks

where, for k ∈ :

– the origin ok (or the destination dk respectively) refers to the source (or the sink respectively) of network Gk;

– k ⊆ refers to the set of flights programmed by the company that can be covered by crew k.

The arc set is

where

Passing through arc (ok, dk) will denote that crew k will not be used. is the set of pairs of flights (i, j) that satisfy the following necessary conditions for making the sequence of flights (l, j) possible for the same crew:

i) the arrival airport of flight i is the departure airport of flight j;

ii) the departure time of flight j is later than the arrival time of flight i, with a gap greater than or equal to a value tmin(i, j) fixed by the company or by the transit constraints of the airport.

Generally, k ≠ because the work regulations of the company impose a certain number of additional constraints (meal slots, breaks, overnight stops) that restrict the connection possibilities between flights. Furthermore, global constraints, which vary from one company to another, are generally associated with each rotation. Let us cite the following possible constraints:

These constraints can be modeled by the following parameters:

1.2.2. Pairing costs