Applications of Combinatorial Optimization

✍ Scribed by Vangelis Th. Paschos

• Publisher: Wiley-ISTE
• Year: 2014
• Tongue: English
• Leaves: 449
• Series: ISTE
• Edition: 2nd ed
• Category: Library

✦ Synopsis

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

Content: Cover
Title Page
Copyright
Contents
Preface
Chapter 1: Airline Crew Pairing Optimization
1.1. Introduction
1.2. Definition 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 finding 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 method1.4.4. Case of many resources: reduction of the resource space
1.4.4.1. Reduction principle
1.4.4.2. Approach based on the Lagrangian relaxation
1.4.4.3. Approach based on the surrogate relaxation
1.5. Conclusion
1.6. Bibliography
Chapter 2: The Task Allocation Problem
2.1. Presentation
2.2. Definitions and modeling
2.2.1. Definitions
2.2.2. The processors
2.2.3. Communications
2.2.4. Tasks
2.2.5. Allocation types
2.2.5.1. Static allocation
2.2.5.2. Dynamic allocation
2.2.5.3. With or without pre-emption. 2.2.5.4. Task duplication2.2.6. Allocation/scheduling
2.2.7. Modeling
2.2.7.1. Modeling costs
2.2.7.2. Constraints
2.2.7.3. Objectives of the allocation
2.2.7.3.1. Minimizing the execution duration
2.2.7.3.2. Minimizing the global execution and communication cost
2.2.7.3.3. Load balancing
2.3. Review of the main works
2.3.1. Polynomial cases
2.3.1.1. Two-processor cases
2.3.1.2. Tree case
2.3.1.3. Other structures
2.3.1.4. Restrictions on the processors or the tasks
2.3.1.5. Minmax objective
2.3.2. Approximability
2.3.3. Approximate solution
2.3.3.1. Heterogenous processors. 2.3.3.2. Homogenous processors2.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.4.2.1. Transformation of the problem
2.4.2.2. Modeling
2.4.2.3. Description of the heuristic
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.

✦ Subjects

Математика;Методы оптимизации;