Concepts of Combinatorial Optimization, Volume 1

Name: Concepts of Combinatorial Optimization, Volume 1
Brand: Wiley-ISTE
Price: 160.99 EUR
Availability: OnlineOnly

Vangelis Th. Paschos(Editor)

Wiley-ISTE (Publisher)

Published on 27. December 2012

368 pages

E-Book

ePUB with Adobe-DRM

System requirements

978-1-118-60023-8 (ISBN)

€160.99incl. 7% vat

System requirements

for ePUB with Adobe-DRM

E-Book Single Licence

Available for download

Description

More details

Other editions

Person

Content

Cover
Concepts of Combinatorial Optimization
Title Page
Copyright Page
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
1.6.1. MIN VERTEX COVER
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
2.1.1. Complexity of a Las Vegas algorithm
2.1.2. Probabilistic complexity of a problem
2.2. Lower bound technique
2.2.1. Definitions and notations
2.2.2. Minimax theorem
2.2.3. The Loomis lemma and the Yao principle
2.3. Elementary intersection problem
2.3.1. Upper bound
2.3.2. Lower bound
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
3.2.1. Principle of separation
3.2.2. Pruning principles
3.2.3. Developing the tree
3.3. A detailed example: the binary knapsack problem
3.3.1. Calculating the initial bound
3.3.2. First principle of separation
3.3.3. Pruning without evaluation
3.3.4. Evaluation
3.3.5. Complete execution of the branch-and-bound method for finding only one optimal solution
3.3.6. First variant: finding all the optimal solutions
3.3.7. Second variant: best first search strategy
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 first example: crossing the bridge
4.3. Formalization
4.3.1. State space, decision set, transition function
4.3.2. Feasible policies, comparison relationships and objectives
4.4. Some other examples
4.4.1. Stock management
4.4.2. Shortest path bottleneck in a graph
4.4.3. Knapsack problem
4.5. Solution
4.5.1. Forward procedure
4.5.2. Backward procedure
4.5.3. Principles of optimality and monotonicity
4.6. Solution of the examples
4.6.1. Stock management
4.6.2. Shortest path bottleneck
4.6.3. Knapsack
4.7. A few extensions
4.7.1. Partial order and multicriteria optimization
4.7.2. Dynamic programming with variables
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
5.1.1. Preliminaries
5.1.2. The knapsack problem
5.1.3. The bin-packing problem
5.1.4. The set covering/set partitioning problem
5.1.5. The minimum cost flow problem
5.1.6. The maximum flow problem
5.1.7. The transportation problem
5.1.8. The assignment problem
5.1.9. The shortest path problem
5.2. General modeling techniques
5.2.1. Min-max, max-min, min-abs models
5.2.2. Handling logic conditions
5.3. More advanced MILP models
5.3.1. Location models
5.3.2. Graphs and network models
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
6.2.1. Optimality conditions and strong duality
6.2.2. Symmetry of the duality relation
6.2.3. Weak duality
6.2.4. Economic interpretation of duality
6.3. The primal simplex method
6.3.1. Basic solutions
6.3.2. Canonical form and reduced costs
6.4. Bland's rule
6.4.1. Searching for a feasible solution
6.5. Simplex methods for the dual problem
6.5.1. The dual simplex method
6.5.2. The primal-dual simplex algorithm
6.6. Using reduced costs and pseudo-costs for integer programming
6.6.1. Using reduced costs for tightening variable bounds
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
7.2.1. Standard linear programming and the main results
7.2.2. Principle of the simplex method
7.2.3. Putting the problem into canonical form
7.2.4. Stopping criterion, heuristics and pivoting
7.3. Duality
7.4. Khachiyan's algorithm
7.5. Interior methods
7.5.1. Karmarkar's projective algorithm
7.5.2. Primal-dual methods and corrective predictive methods
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
8.7.1. Posiform maximization and stability in a graph
8.7.2. Implication graph associated with a quadratic posiform
8.8. Optimizing a qpBf: special cases and polynomial cases
8.8.1. Maximizing negative-positive functions
8.8.2. Maximizing functions associated with k-trees
8.8.3. Maximizing a quadratic posiform whose terms are associated with two consecutive arcs of a directed multigraph
8.8.4. Quadratic pseudo-Boolean functions equal to the product of two linear functions
8.9. Reductions, relaxations, linearizations, bound calculation and persistence
8.9.1. Complementation
8.9.2. Linearization
8.9.3. Lagrangian duality
8.9.4. Another linearization
8.9.5. Convex quadratic relaxation
8.9.6. Positive semi-definite relaxation
8.9.7. Persistence
8.10. Local optimum
8.11. Exact algorithms and heuristic methods for optimizing qpBfs
8.11.1. Different approaches
8.11.2. An algorithm based on Lagrangian decomposition
8.11.3. An algorithm based on convex quadratic programming
8.12. Approximation algorithms
8.12.1. A 2-approximation algorithm for maximizing a quadratic posiform
8.12.2. MAX-SAT approximation
8.13. Optimizing a quadratic pseudo-Boolean function with linear constraints
8.13.1. Examples of formulations
8.13.2. Some polynomial and pseudo-polynomial cases
8.13.3. Complementation
8.14. Linearization, convexification and Lagrangian relaxation for optimizing a qpBf with linear constraints
8.14.1. Linearization
8.14.2. Convexification
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 problem
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
9.5.1. Auxiliary problem (pricing problem)
9.5.2. Branching
9.6. Applications
9.6.1. The p-medians problem
9.6.2. Vehicle routing
9.7. Bibliography
Chapter 10. Polyhedral Approaches
10.1. Introduction
10.2. Polyhedra, faces and facets
10.2.1. Polyhedra, polytopes and dimension
10.2.2. Faces and facets
10.3. Combinatorial optimization and linear programming
10.3.1. Associated polytope
10.3.2. Extreme points and extreme rays
10.4. Proof techniques
10.4.1. Facet proof techniques
10.4.2. Integrality techniques
10.5. Integer polyhedra and min-max relations
10.5.1. Duality and combinatorial optimization
10.5.2. Totally unimodular matrices
10.5.3. Totally dual integral systems
10.5.4. Blocking and antiblocking polyhedral
10.6. Cutting-plane method
10.6.1. The Chvátal-Gomory method
10.6.2. Cutting-plane algorithm
10.6.3. Branch-and-cut algorithms
10.6.4. Separation and optimization
10.7. The maximum cut problem
10.7.1. Spin glass models and the maximum cut problem
10.7.2. The cut polytope
10.8. The survivable network design problem
10.8.1. Formulation and associated polyhedron
10.8.2. Valid inequalities and separation
10.8.3. A branch-and-cut algorithm
10.9. Conclusion
10.10. Bibliography
Chapter 11. Constraint Programming
11.1. Introduction
11.2. Problem definition
11.3. Decision operators
11.4. Propagation
11.5. Heuristics
11.5.1. Branching
11.5.2. Exploration strategies
11.6. Conclusion
11.7. Bibliography
List of Authors
Index
Summary of Other Volumes in the Series

Content (EPUB)

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Concepts of Combinatorial Optimization, Volume 1

Description

More details

Other editions

Additional editions

Person

Content

System requirements