Applications of Combinatorial Optimization

Cover

Applications of Combinatorial Optimization

ISBN 9781848211490

Table of Contents

Preface

Chapter 1 Airline Crew Pairing Optimization

1.1. Introduction
1.2. Defnition of the problem
1.2.1. Constructing subnetworks
1.2.2. Pairing costs
1.2.3. Model
1.2.4. Case without resource constraints
1.3. Solution approaches
1.3.1. Decomposition principles
1.3.2. Column generation, master problem and subproblem
1.3.3. Branching methods for fnding integer solutions
1.4. Solving the subproblem for column generation
1.4.1. Mathematical formulation
1.4.2. General principle of effective label generation
1.4.3. Case of one single resource: the bucket method
1.4.4. Case of many resources: reduction of the resource space
1.5. Conclusion
1.6. Bibliography

Chapter 2 The Task Allocation Problem

2.1. Presentation
2.2. Defnitions and modeling
2.2.1. Defnitions
2.2.2. The processors
2.2.3. Communications
2.2.4. Tasks
2.2.5. Allocation types
2.2.6. Allocation/scheduling
2.2.7. Modeling
2.3. Review of the main works
2.3.1. Polynomial cases
2.3.2. Approximability
2.3.3. Approximate solution
2.3.4. Exact solution
2.3.5. Independent tasks case
2.4. A little-studied model
2.4.1. Model
2.4.2. A heuristic based on graphs
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.2.1. Exact separation with respect to a mixed relaxation
3.2.2. Approximate separation using a heuristic
3.2.3. Restriction + separation + relaxed lifting (RSRL)
3.2.4. Disjunctive programming and the lift and project procedure
3.2.5. Reformulation-linearization technique (RLT)
3.3. Computational results
3.3.1. Presentation of test problems
3.3.2. Presentation of the results
3.3.3. Discussion of the 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.3.1. Group technology
4.3.2. Locating equipment
4.4. Tactical planning and inventory management
4.4.1. A linear programming model for medium-term planning
4.4.2. Inventory management
4.4.3. Wagner and Whitin model
4.4.4. The economic order quantity model (EOQ)
4.4.5. The EOQ model with joint replenishments
4.5. Operations planning and scheduling
4.5.1. Tooling
4.5.2. Robotic cells
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.3.1. Location with balancing requirements
5.3.2. Multiproduct production-distribution
5.3.3. Hub location
5.4. Long-distance transport
5.4.1. Service network design
5.4.2. Static formulations
5.4.3. Dynamic formulations
5.4.4. Fleet management
5.5. Vehicle routing problems
5.5.1. Defnitions and complexity
5.5.2. Classical extensions
5.6. Exact models and methods for the VRP
5.6.1. Flow model with three indices
5.6.2. Flow model for the symmetric CVRP
5.6.3. Set partitioning model
5.6.4. Branch-and-cut methods for the CVRP
5.6.5. Column generation methods for the VRPTW
5.7. Heuristic methods for the VRP
5.7.1. Classical heuristics
5.7.2. Metaheuristics
5.7.3. The VRP in practice
5.8. Conclusion
5.9. Appendix: metaheuristics
5.9.1. Tabu search
5.9.2. Evolutionary algorithms
5.10. Bibliography

Chapter 6 Optimization Models for Transportation Systems Planning

6.1. Introduction
6.2. Spatial interaction models
6.3. Traffc assignment models and methods
6.3.1. System optimization and user optimization models
6.3.2. Algorithms for traffc assignment for the user optimization model
6.3.3. The user problem as variational inequality
6.4. Transit route choice models
6.5. Strategic planning of multimodal systems
6.5.1. Demand
6.5.2. Mode choice
6.5.3. Representing transport supply and assigning demand
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.2.1. The diffculties of solving jointly or globally
7.2.2. Why tackle the global problem?
7.2.3. How to circumvent these diffculties
7.3. Mathematical model, general context
7.3.1. Hypotheses
7.3.2. The original problem
7.3.3. Solution principle
7.4. Proposed algorithm
7.4.1. A bit of sensitivity in an NP-hard world
7.4.2. The initial solution
7.4.3. Step-by-step exploration
7.5. Critical points
7.5.1. Parametric diffculties
7.5.2. Realities not taken into account
7.5.3. Complexity in size of the problem
7.6. Conclusion
7.7. Bibliography

Chapter 8 Parallel Combinatorial Optimization

8.1. Impact of parallelism in combinatorial optimization
8.2. Parallel metaheuristics
8.2.1. Notion of walks
8.2.2. Classifcation of parallel metaheuristics
8.2.3. An illustrative example: scatter search for the quadratic assignment or QAP
8.3. Parallelizing tree exploration in exact methods
8.3.1. Return to two success stories
8.3.2. B&X model and data structures
8.3.3. Different levels of parallelism
8.3.4. Critical tree and anomalies
8.3.5. Parallel algorithms and granularity
8.3.6. The BOB++ library
8.3.7. B&X on grids of machines
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.2.1. Decomposition in linear programming and polyhedra
9.2.2. Flows and multiflows
9.2.3. Queuing network
9.2.4. Game theory models
9.3. Models and problems
9.3.1. Location problems
9.3.2. Steiner trees and variants
9.4. The STEINER-EXTENDED problem
9.5. Conclusion

Chapter 10 Network Design Problems: Models and Applications

10.1. Introduction
10.2. Models and location problems
10.2.1. Locating the network access device
10.2.2. Locating machines and activities at the core of a production space
10.3. Routing models for telecommunications
10.3.1. Numerical tests
10.4. The design or dimensioning problem in telecommunications
10.4.1. Numerical tests
10.5. Coupled flows and multiflows for transport and production
10.5.1. Analysis of the COUPLED-FLOW-MULTIFLOW (CFM) problem
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.1.1. Example a: organizing non-compulsory lesson choices by students
11.1.2. Example b: temporal activity programming
11.1.3. Example c: task scheduling on machines
11.2. Modeling the set of feasible assignments
11.3. The concept of a blocking confguration and analysis of the unblocking
11.3.1. A reminder of a few results from fow theory
11.3.2. Analysis of the minimum cut revealed by labeling a maximum fow on N
11.3.3. The concept of blocking confguration
11.3.4. Unblocking actions
11.4. The multicriteria assignment problem
11.4.1. Defnition of the criteria family
11.4.2. Satisfactory compromise selection strategy
11.5. Exploring a set of feasible non-dominated assignments in the plane
11.5.1. The bicriteria assignment problem with mutual exclusion constraints
11.5.2. Finding supported solutions of problem P
11.5.3. Matrix representation of problem P
11.5.4. Finding unsupported solutions of problem P
11.6. Numerical examples
11.6.1. Example with a blocking confguration present
11.6.2. Example without a blocking confguration
11.7. Conclusion
11.8. Bibliography

List of Authors

Index

Summary of Volume 1 Concepts of Combinatorial Optimization

Summary of Volume 2 Paradigms of Combinatorial Optimization