Concepts of Combinatorial Optimization

Cover

Concepts of Combinatorial Optimization

ISBN 9781848211476

Table of Contents

Preface

PART I Complexity of Combinatorial Optimization Problems

Chapter 1 Basic Concepts in Algorithms and Complexity Theory
1.1. Algorithmic complexity
1.2. Problem complexity
1.3. The classes P, NP and NPO
1.4. Karp and Turing reductions
1.5. NP-completeness
1.6. Two examples of NP-complete problems
o 1.6.1. MIN VERTEX COVER
o 1.6.2. MAX STABLE
1.7. A few words on strong and weak NP-completeness
1.8. A few other well-known complexity classes
1.9. Bibliography
Chapter 2 Randomized Complexity
2.1. Deterministic and probabilistic algorithms
o 2.1.1. Complexity of a Las Vegas algorithm
o 2.1.2. Probabilistic complexity of a problem
2.2. Lower bound technique
o 2.2.1. Defnitions and notations
o 2.2.2. Minimax theorem
o 2.2.3. The Loomis lemma and the Yao principle
2.3. Elementary intersection problem
o 2.3.1. Upper bound
o 2.3.2. Lower bound
o 2.3.3. Probabilistic complexity
2.4. Conclusion
2.5. Bibliography

PART II Classical Solution Methods

Chapter 3 Branch-and-Bound Methods
3.1. Introduction
3.2. Branch-and-bound method principles
o 3.2.1. Principle of separation
o 3.2.2. Pruning principles
o 3.2.3. Developing the tree
3.3. A detailed example: the binary knapsack problem
o 3.3.1. Calculating the initial bound
o 3.3.2. First principle of separation
o 3.3.3. Pruning without evaluation
o 3.3.4. Evaluation
o 3.3.5. Complete execution of the branch-and-bound method for fnding only one
o 3.3.6. First variant: fnding all the optimal solutions
o 3.3.7. Second variant: best frst search strategy
o 3.3.8. Third variant: second principle of separation
3.4. Conclusion
3.5. Bibliography
Chapter 4 Dynamic Programming
4.1. Introduction
4.2. A frst example: crossing the bridge
4.3. Formalization
o 4.3.1. State space, decision set, transition function
o 4.3.2. Feasible policies, comparison relationships and objectives
4.4. Some other examples
o 4.4.1. Stock management
o 4.4.2. Shortest path bottleneck in a graph
o 4.4.3. Knapsack problem
4.5. Solution
o 4.5.1. Forward procedure
o 4.5.2. Backward procedure
o 4.5.3. Principles of optimality and monotonicity
4.6. Solution of the examples
o 4.6.1. Stock management
o 4.6.2. Shortest path bottleneck
o 4.6.3. Knapsack
4.7. A few extensions
o 4.7.1. Partial order and multicriteria optimization
o 4.7.2. Dynamic programming with variables
o 4.7.3. Generalized dynamic programming
4.8. Conclusion
4.9. Bibliography

PART III Elements from Mathematical Programming

Chapter 5 Mixed Integer Linear Programming Models for Combinatorial Optimization Problems
5.1. Introduction
o 5.1.1. Preliminaries
o 5.1.2. The knapsack problem
o 5.1.3. The bin-packing problem
o 5.1.4. The set covering/set partitioning problem
o 5.1.5. The minimum cost fow problem
o 5.1.6. The maximum fow problem
o 5.1.7. The transportation problem
o 5.1.8. The assignment problem
o 5.1.9. The shortest path problem
5.2. General modeling techniques
o 5.2.1. Min-max, max-min, min-abs models
o 5.2.2. Handling logic conditions
5.3. More advanced MILP models
o 5.3.1. Location models
o 5.3.2. Graphs and network models
o 5.3.3. Machine scheduling models
5.4. Conclusions
5.5. Bibliography
Chapter 6 Simplex Algorithms for Linear Programming
6.1. Introduction
6.2. Primal and dual programs
o 6.2.1. Optimality conditions and strong duality
o 6.2.2. Symmetry of the duality relation
o 6.2.3. Weak duality
o 6.2.4. Economic interpretation of duality
6.3. The primal simplex method
o 6.3.1. Basic solutions
o 6.3.2. Canonical form and reduced costs
6.4. Bland's rule
o 6.4.1. Searching for a feasible solution
6.5. Simplex methods for the dual problem
o 6.5.1. The dual simplex method
o 6.5.2. The primal-dual simplex algorithm
6.6. Using reduced costs and pseudo-costs for integer programming
o 6.6.1. Using reduced costs for tightening variable bounds
o 6.6.2. Pseudo-costs for integer programming
6.7. Bibliography
Chapter 7 A Survey of some Linear Programming Methods
7.1. Introduction
7.2. Dantzig's simplex method
o 7.2.1. Standard linear programming and the main results
o 7.2.2. Principle of the simplex method
o 7.2.3. Putting the problem into canonical form
o 7.2.4. Stopping criterion, heuristics and pivoting
7.3. Duality
7.4. Khachiyan's algorithm
7.5. Interior methods
o 7.5.1. Karmarkar's projective algorithm
o 7.5.2. Primal-dual methods and corrective predictive methods
o 7.5.3. Mehrotra predictor-corrector method
7.6. Conclusion
7.7. Bibliography
Chapter 8 Quadratic Optimization in 0-1 Variables
8.1. Introduction
8.2. Pseudo-Boolean functions and set functions
8.3. Formalization using pseudo-Boolean functions
8.4. Quadratic pseudo-Boolean functions (qpBf)
8.5. Integer optimum and continuous optimum of qpBfs
8.6. Derandomization
8.7. Posiforms and quadratic posiforms
o 8.7.1. Posiform maximization and stability in a graph
o 8.7.2. Implication graph associated with a quadratic posiform
8.8. Optimizing a qpBf: special cases and polynomial cases
o 8.8.1. Maximizing negative-positive functions
o 8.8.2. Maximizing functions associated with k-trees
o 8.8.3. Maximizing a quadratic posiform whose terms are associated with two con-
o 8.8.4. Quadratic pseudo-Boolean functions equal to the product of two linear func-
8.9. Reductions, relaxations, linearizations, bound calculation and persistence
o 8.9.1. Complementation
o 8.9.2. Linearization
o 8.9.3. Lagrangian duality
o 8.9.4. Another linearization
o 8.9.5. Convex quadratic relaxation
o 8.9.6. Positive semi-defnite relaxation
o 8.9.7. Persistence
8.10. Local optimum
8.11. Exact algorithms and heuristic methods for optimizing qpBfs
o 8.11.1. Different approaches
o 8.11.2. An algorithm based on Lagrangian decomposition
o 8.11.3. An algorithm based on convex quadratic programming
8.12. Approximation algorithms
o 8.12.1. A 2-approximation algorithm for maximizing a quadratic posiform
o 8.12.2. MAX-SAT approximation
8.13. Optimizing a quadratic pseudo-Boolean function with linear constraints
o 8.13.1. Examples of formulations
o 8.13.2. Some polynomial and pseudo-polynomial cases
o 8.13.3. Complementation
8.14. Linearization, convexifcation and Lagrangian relaxation for optimizing a
o 8.14.1. Linearization
o 8.14.2. Convexifcation
o 8.14.3. Lagrangian duality
8.15. e-Approximation algorithms for optimizing a qpBf with linear constraints
8.16. Bibliography
Chapter 9 Column Generation in Integer Linear Programming
9.1. Introduction
9.2. A column generation method for a bounded variable linear programming
9.3. An inequality to eliminate the generation of a 0-1 column
9.4. Formulations for an integer linear program
9.5. Solving an integer linear program using column generation
o 9.5.1. Auxiliary problem (pricing problem)
o 9.5.2. Branching
9.6. Applications
o 9.6.1. The p-medians problem
o 9.6.2. Vehicle routing
9.7. Bibliography
Chapter 10 Polyhedral Approaches
10.1. Introduction
10.2. Polyhedra, faces and facets
o 10.2.1. Polyhedra, polytopes and dimension
o 10.2.2. Faces and facets
10.3. Combinatorial optimization and linear programming
o 10.3.1. Associated polytope
o 10.3.2. Extreme points and extreme rays
10.4. Proof techniques
o 10.4.1. Facet proof techniques
o 10.4.2. Integrality techniques
10.5. Integer polyhedra and min-max relations
o 10.5.1. Duality and combinatorial optimization
o 10.5.2. Totally unimodular matrices
o 10.5.3. Totally dual integral systems
o 10.5.4. Blocking and antiblocking polyhedra
10.6. Cutting-plane method
o 10.6.1. The Chvtal-Gomory method
o 10.6.2. Cutting-plane algorithm
o 10.6.3. Branch-and-cut algorithms
o 10.6.4. Separation and optimization
10.7. The maximum cut problem
o 10.7.1. Spin glass models and the maximum cut problem
o 10.7.2. The cut polytope
10.8. The survivable network design problem
o 10.8.1. Formulation and associated polyhedron
o 10.8.2. Valid inequalities and separation
o 10.8.3. A branch-and-cut algorithm
10.9. Conclusion
10.10. Bibliography
Chapter 11 Constraint Programming
11.1. Introduction
11.2. Problem defnition
11.3. Decision operators
11.4. Propagation
11.5. Heuristics
o 11.5.1. Branching
o 11.5.2. Exploration strategies
11.6. Conclusion
11.7. Bibliography

List of Authors

Index

Summary of Volume 2 Paradigms of Combinatorial Optimization

Summary of Volume 3 Applications of Combinatorial Optimization