β Scribed by Michael JΓΌnger (editor), Denis Naddef (editor)
No coin nor oath required. For personal study only.
This tutorial contains written versions of seven lectures on Computational Combinatorial Optimization given by leading members of the optimization community. The lectures introduce modern combinatorial optimization techniques, with an emphasis on branch and cut algorithms and Lagrangian relaxation approaches. Polyhedral combinatorics as the mathematical backbone of successful algorithms are covered from many perspectives, in particular, polyhedral projection and lifting techniques and the importance of modeling are extensively discussed. Applications to prominent combinatorial optimization problems, e.g., in production and transport planning, are treated in many places; in particular, the book contains a state-of-the-art account of the most successful techniques for solving the traveling salesman problem to optimality.
Lecture Notes in Computer Science
Springer
Computational Combinatorial Optimization
Preface
Organization
Executive Committee
Program Committee
Steering Committee
Sponsoring Organizations
Referees
Contents
Security
Models and Architectures
Applications
Communication
Run-Time Support
Quantitative Evaluation and Benchmarking
General Mixed Integer Programming: Computational Issues for Branch-and-Cut Algorithms
Introduction
Branch-and-Cut Algorithms
Preprocessing
Branch-and-Bound Strategies
Node Selection
Variable Selection
Cutting Planes
Cutting Planes Independent of Any Problem Structure
Pure Integer Programs
Mixed Integer Programs
Cutting Planes Exploiting Structure
Knapsack Relaxations
Lifting
Conclusions
References
Projection and Lifting in Combinatorial Optimization
Basic Properties of Projection
Dimensional Aspects of Projection
Comparing Different Formulations
Proving the Integrality of Polyhedra
Disjunctive Programming
Projection and Polarity
Sequential Convexification
Disjunctive Rank
Another Derivation of the Basic Results
Generating Lift-and-Project Cuts
Deepest Cuts
Cut Lifting
Cut Strengthening
The Overall Cut Generating Procedure
Branch-and-Cut and Computational Experience
Computational Results in Branch-and-Cut Mode
Results in Cut-and-Branch Mode
References
Mathematical Programming Models and Formulations for Deterministic Production Planning Problems
Introduction
Production Planning
Manufacturing Planning and Control Systems
Production Planning Models
Optimization Methods
The CORE Subproblem: Single Item Uncapacitated Lot-Sizing
Basic Formulation and Motivation
Dynamic Programming Algorithm
Extended Reformulations
Complete Linear Description in the Initial Space
Single Item Variants of Uncapacitated Lot-Sizing
Formulations of Capacitated Models
Classes of Capacitated Models
Big Buckets Models: Capacitated Lot-Sizing
Small Buckets Models
Formulations of Multi-level Models
Multi-level Models and the Decomposition Approach
Optimization of Multi-level Models
The Echelon Stock Reformulation
New Directions
Setup Times, Capacity Utilization, and Productivity Models
Process Industry: Products and Operations Structure
Continuous Time Scheduling Models
Challenges
References
Lagrangian Relaxation
Introduction, Motivation
Scope of the Paper
The Basic Idea of Lagrangian Relaxation
Examples
Linear Programming
Quadratic Programming
Max-cut, Max-stable, and Quadratic Constraints
Conic Duality
A Large-Scale Problem: Unit-Commitment
Column Generation in Linear Programming
Entropy Maximization
Minimal Amount of Convex Analysis
Minimizing the Dual Function
Primal-Dual Relations
Dual Algorithms I: Subgradient, Cutting Plane, ACCPM
Subgradients and Ellipsoid Methods
The Cutting-Plane Method, or of Kelley, Cheney-Goldstein
Stability Problems: ACCPM
Dual Algorithms II: Bundle Methods
The Algorithmic Scheme
Primal-Dual Relations: Augmented Lagrangian
Quadratic Solvers and Poorman Bundle Methods
Numerical Illustrations
References
Branch-and-Cut Algorithms for Combinatorial Optimization and Their Implementation in ABACUS
Our Most Recent Story
Break Minimization
From Minimizing Breaks to Maximizing Cuts
Computational Results
A Bit of History
Linear Programming
Mixed Integer Programming
Combinatorial Optimization
Branch-and-Cut
Branch-and-Price
Components of Branch-and-Cut
Terminology
Enumerative Frame
Computation of Local Lower Bounds
Computation of Global Upper Bounds
Sparse Solution and Column Generation
Some More Advanced Topics
Reduction and Lifting for Separation
Branch-and-Cut-and-Price
Design and Usage of abacusbigfont ABACUS
Basic Design Ideas
Structure of the System
Essential Classes for an Applications
Exercise: Implementation of a Simple TSP Solver
References
Branch, Cut, and Price: Sequential and Parallel
Introduction
Related Work
Organization of the Manuscript
Introduction to Branch, Cut, and Price
Branch and Bound
Branch, Cut, and Price
Design of SYMPHONY
An Object-Oriented Approach
Data Structures and Storage
Modular Implementation
SYMPHONY Overview
Details of the Implementation
The Master Module
The Linear Programming Module
The Tree Manager Module
The Cut Generator Module
The Cut Pool Module
Parallelizing BCP
Scalability
Details of the Parallel Implementation
Applications
The Vehicle Routing Problem
Set Partitioning Problem
Computational Experience
Sequential Performance
Parallel Performance
Computational Results for Vehicle Routing
Computational Results for Set Partitioning
Future Development
Improving Parallel Scalability
Other Directions
Conclusion
References
TSP Cuts Which Do Not Conform to the Template Paradigm
The Cutting-Plane Method and Its Descendants
Ways of Finding Cuts
Cuts, Tours, and Shrinking
Processing xΒ―
Does xΒ― Lie Outside the Graphical Traveling Salesman Polytope?
Separating xΒ―* from the Graphical Traveling Salesman Polytope: the Three Phases
Phase 1: From Strongly Constrained to Moderately Constrained Tangled Tours
Phase 2: From Moderately Constrained to Weakly Constrained Tangled Tours
Phase 3: From Weakly Constrained to All Tangled Tours
Making Choices of V_0, V_1, . . . , V_k
Experimental Findings
The Easier TSPLIB Instances
Three of the Harder TSPLIB Instances
Generalizations
References
Author Index
π SIMILAR VOLUMES
<p>This tutorial contains written versions of seven lectures on Computational Combinatorial Optimization given by leading members of the optimization community. The lectures introduce modern combinatorial optimization techniques, with an emphasis on branch and cut algorithms and Lagrangian relaxatio
<p>This tutorial contains written versions of seven lectures on Computational Combinatorial Optimization given by leading members of the optimization community. The lectures introduce modern combinatorial optimization techniques, with an emphasis on branch and cut algorithms and Lagrangian relaxatio
<p>This tutorial contains written versions of seven lectures on Computational Combinatorial Optimization given by leading members of the optimization community. The lectures introduce modern combinatorial optimization techniques, with an emphasis on branch and cut algorithms and Lagrangian relaxatio