You are previewing Applications of Combinatorial Optimization, 2nd Edition.
O'Reilly logo
Applications of Combinatorial Optimization, 2nd Edition

Book Description

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.

Table of Contents

  1. Cover
  2. Table of Contents
  3. Title Page
  4. Copyright
  5. Preface
  6. Chapter 1: Airline Crew Pairing Optimization
    1. 1.1. Introduction
    2. 1.2. Definition of the Problem
    3. 1.3. Solution Approaches
    4. 1.4. Solving the Subproblem for Column Generation
    5. 1.5. Conclusion
    6. 1.6. Bibliography
  7. Chapter 2: The Task Allocation Problem
    1. 2.1. Presentation
    2. 2.2. Definitions and Modeling
    3. 2.3. Review of the Main Works
    4. 2.4. A Little-Studied Model
    5. 2.5. Conclusion
    6. 2.6. Bibliography
  8. Chapter 3: A Comparison of Some Valid Inequality Generation Methods for General 0–1 Problems
    1. 3.1. Introduction
    2. 3.2. Presentation of the Various Techniques Tested
    3. 3.3. Computational Results
    4. 3.4. Bibliography
  9. Chapter 4: Production Planning
    1. 4.1. Introduction
    2. 4.2. Hierarchical Planning
    3. 4.3. Strategic Planning and Productive System Design
    4. 4.4. Tactical Planning and Inventory Management
    5. 4.5. Operations Planning and Scheduling
    6. 4.6. Conclusion and Perspectives
    7. 4.7. Bibliography
  10. Chapter 5: Operations Research and Goods Transportation
    1. 5.1. Introduction
    2. 5.2. Goods Transport Systems
    3. 5.3. Systems Design
    4. 5.4. Long-distance Transport
    5. 5.5. Vehicle Routing Problems
    6. 5.6. Exact Models and Methods for the VRP
    7. 5.7. Heuristic Methods for the VRP
    8. 5.8. Conclusion
    9. 5.9. Appendix: Metaheuristics
    10. 5.10. Bibliography
  11. Chapter 6: Optimization Models for Transportation Systems Planning
    1. 6.1. Introduction
    2. 6.2. Spatial Interaction Models
    3. 6.3. Traffic Assignment Models and Methods
    4. 6.4. Transit Route Choice Models
    5. 6.5. Strategic Planning of Multimodal Systems
    6. 6.6. Conclusion
    7. 6.7. Bibliography
  12. Chapter 7: A Model for the Design of a Minimum-cost Telecommunications Network
    1. 7.1. Introduction
    2. 7.2. Minimum Cost Network Construction
    3. 7.3. Mathematical Model, General Context
    4. 7.4. Proposed Algorithm
    5. 7.5. Critical Points
    6. 7.6. Conclusion
    7. 7.7. Bibliography
  13. Chapter 8: Parallel Combinatorial Optimization
    1. 8.1. Impact of parallelism in Combinatorial Optimization
    2. 8.2. Parallel Metaheuristics
    3. 8.3. Parallelizing Tree Exploration in Exact Methods
    4. 8.4. Conclusion
    5. 8.5. Bibliography
  14. Chapter 9: Network Design Problems: Fundamental Methods
    1. 9.1. Introduction
    2. 9.2. The Main Mathematical and Algorithmic Tools for Network Design
    3. 9.3. Models and Problems
    4. 9.4. The Steiner-Extended problem
    5. 9.5. Conclusion
    6. 9.6 Bibliography
  15. Chapter 10: Network Design Problems: Models and Applications
    1. 10.1. Introduction
    2. 10.2. Models and Location Problems
    3. 10.3. Routing Models for Telecommunications
    4. 10.4. The Design or Dimensioning Problem in Telecommunications
    5. 10.5. Coupled Flows and Multiflows for Transport and Production
    6. 10.6. A Mixed Network Pricing Model
    7. 10.7. Conclusion
    8. 10.8. Bibliography
  16. Chapter 11: Multicriteria Task Allocation to Heterogenous Processors with Capacity and Mutual Exclusion Constraints
    1. 11.1. Introduction and Formulation of the Problem
    2. 11.2. Modeling the Set of Feasible Assignments
    3. 11.3. The Concept of a Blocking Configuration and Analysis of the Unblocking Means
    4. 11.4. The Multicriteria Assignment Problem
    5. 11.5. Exploring a Set of Feasible Non-Dominated Assignments in the Plane g2 × g3
    6. 11.6. Numerical Example
    7. 11.7. Conclusion
    8. 11.8. Bibliography
  17. General Bibliography
  18. List of Authors
  19. Index