Integer Programming and Combinatorial Optimization
15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings
Published on 21. June 2011
XIII, 432 pages
978-3-642-20807-2 (ISBN)
Description
This book constitutes the proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2011, held in New York, USA in June 2011.
The 33 papers presented were carefully reviewed and selected from 110 submissions. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization with the aim to present recent developments in theory, computation, and applications. The scope of IPCO is viewed in a broad sense, to include algorithmic and structural results in integer programming and combinatorial optimization as well as revealing computational studies and novel applications of discrete optimization to practical problems.
More details
Other editions
Additional editions
Oktay Günlük | Gerhard J. Woeginger
Integer Programming and Combinatorial Optimization
15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings
Book
05/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- An Excluded Minor Characterization of Seymour Graphs
- Introduction
- Results
- Proof of Theorem 2
- References
- Complexity Analyses of Bienstock-Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
- Introduction
- Preliminaries
- The $\SA$ and $\SA_+$ Operator
- The Lasserre Operator
- The Bienstock-Zuckerberg Operators
- Matching Polytope and the Notion of Rank
- Some Tools for Upper Bound Analyses
- The $\SA_+$-rank, the $\Las$-rank, and the Theta-rank of the Matching Polytope
- The $\BZ_+$-rank of the Matching Polytope
- The $\BZ$-rank of the Stable Set Polytope
- References
- A Probabilistic Analysis of the Strength of the Split and Triangle Closures
- Introduction
- Preliminaries
- Worst-Cost Measure in $\mathbb{R}^2$
- A Bad Ensemble for the Split Closure
- Probability of Bad Ensembles
- Proof of Theorem 1
- Average-Cost Measure
- $(\beta,k)$-Good Ensembles
- Probability of Obtaining a $(\beta, k)$-Good Ensemble
- Lower Bound for Simple Splits
- Proof of Theorem 2
- References
- Partial Convexification of General MIPsby Dantzig-Wolfe Reformulation
- Introduction
- Partial Convexification and Dantzig-Wolfe Reformulations
- Related Literature
- Almost Automatic Detection of an Arrowhead Form
- Computational Results
- Notes on the Implementation and Experimental Setup
- A Class of Structured MIPs without Block-Diagonal Form
- MIPLIB2003
- Discussion
- References
- Lift-and-Project Cuts for Mixed Integer Convex Programs
- Introduction
- Outline of the Approach
- Phase I: Testing If x Belongs to a Split Relaxation
- Phase II: Computing the Cut
- Cutting Plane Strategies and Practical Considerations
- Separation by Rounds
- Rank-1 Optimization
- Cut Validity and Stability
- Computational Testing
- Gap Closed
- Complete Resolutions
- References
- TSP on Cubic and Subcubic Graphs
- Introduction
- Preliminaries
- Cubic Graphs
- Subcubic Graphs
- Epilogue
- References
- Approximability of Capacitated Network Design
- Introduction
- Our Results
- The Cap-$R$-Connected Subgraph Problem
- The Standard LP Relaxation and Knapsack-Cover Inequalities
- The Rounding and Analysis
- The $k$-Way-$R$-Connected Subgraph Problem.
- Single-Pair Cap-SNDP in Directed Graphs
- Cap-SNDP with Multiple Copies Allowed
- Conclusions
- References
- Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems
- Introduction
- LP-Rounding Approximation Algorithms for \textsf{MLUFL}
- An \boldmath $O\bigl(\log n\cdot\max\{\log n,\log m\}\bigr)$-Approximation Algorithm
- \textsf{MLUFL} with Related Metrics
- \textsf{MLUFL} with a Uniform Time-Metric
- LP-Relaxations and Algorithms for \textsf{ML}
- Extensions
- References
- An Exact Rational Mixed-Integer Programming Solver
- Introduction
- Hybrid Rational/Safe Floating-Point Approach
- Safe Dual Bound Generation Techniques
- Exact LP Solutions
- Basis Verification
- Primal-Bound-Shift
- Project-and-Shift
- Combinations and Beyond
- Computational Study
- Root Node Performance
- Overall Performance
- Combinations
- Conclusion
- References
- Valid Inequalities for the Pooling Problem with Binary Variables
- Introduction
- The Pooling Problem
- Mathematical Formulation
- Example
- Valid Inequalities
- Quality Inequalities
- Pooling Flow Cover Inequalities
- Computational Results
- References
- On the Chv´atal-Gomory Closure of a Compact Convex Set
- Introduction
- Definitions, Main Result and Proof Idea
- $\CC(K,S) \cap H_v^= = \CC(F_v)$ and $\CC(K,S) \subseteq H_v$
- Lifting CG Cuts
- Separating All Points in $F_v \setminus \aff_I(H_v^=)$
- Lifting the CG Closure of an Exposed Face of $K$
- Approximation of the CG Closure
- Approximation 1 of the CG Closure
- Approximation 2 of the CG Closure
- Proof of Theorem
- Remarks
- References
- Design and Verify: A New Scheme for Generating Cutting-Planes
- Introduction
- General Properties of the $\mathbb V$-Closure
- Strength and Comparisons of $\mathbb V$-Closures
- Strength of $\outer{\M}$ for Arbitrary Admissible Cutting-Plane Procedures $\M$
- Comparing $\M$ and $\outer{\M}$ for $\M$ Being $\gco$, $\SC$, $\N_0$, $\N$, or $\N_{+}$
- Rank of Valid Inequalities with Respect to $\mathbb V$-Closures
- $\mathbb V$-Closures for Well-Known and Structured Problems
- Monotone Polytopes
- Stable Set Polytope
- The Traveling Salesman Problem
- General Polytopes in $\RR^2$
- Concluding Remarks
- References
- Contact Center Scheduling with Strict Resource Requirements
- Introduction
- Problem Definition and Notation
- Hardness Results
- Proof of Theorem 1
- Proof of Theorem 3
- The Bicriteria Approximation Algorithm
- The Special Case of Uniform Requirements
- Extending to General Requirements
- Discussion
- References
- Set Covering with Ordered Replacement: Additive and Multiplicative Gaps
- Introduction
- Bounding the Additive Gap
- The Upper Bound
- The Lower Bound
- Approximation and Intractability
- Ruling Out an APTAS
- Multiplicative Integrality Gaps
- Applications
- References
- Backdoor Branching
- Introduction
- A Basic Set Covering Model
- Backdoor Branching
- Preliminary Computational Results
- References
- A Subexponential Lower Bound for Zadeh's Pivoting Rule for Solving Linear Programs and Games
- Introduction
- Markov Decision Processes and Their Linear Programs
- Policy Iteration Algorithms and Simplex Algorithms
- Lower Bound for Least-Entered
- Full Construction
- Lower Bound Proof
- Concluding Remarks and Open Problems
- References
- An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming
- Introduction
- Polynomial Programming Problem
- Approximations Hierarchies for Polynomial Programs
- Dynamic Approximations for Polynomial Programs
- General Case
- Dynamic Inequality Generation Scheme (DIGS)
- Binary Case
- Specializing the Dynamic Inequality Generation Scheme
- Convergence Results
- Examples
- References
- A New Approach to the Stable Set Problem Based on Ellipsoids
- Introduction
- Literature Review
- Linear Programming Relaxations
- Semidefinite Programming Relaxations
- The Lovász Theta Body and Ellipsoids
- Relaxations of Non-convex Quadratic Problems
- The New Approach
- An `Optimal' Ellipsoid
- Cutting Planes from the Optimal Ellipsoid
- Cut Strengthening
- Computational Experiments
- The Cut-and-Branch Algorithm
- Preliminary Computational Results
- Concluding Remarks
- References
- Capacitated Vehicle Routing with Non-uniform Speeds
- Introduction
- Previous Techniques
- Results, Techniques and Outline
- Related Work
- Model and Preliminaries
- Algorithm for HetTSP
- Assignable Trees
- Level-Prim Spanning Tree
- Decomposition Procedure
- Open Problems
- References
- Approximation Algorithms for Single and Multi-Commodity Connected Facility Location
- Introduction
- Our Results and Techniques
- Related Work
- An Improved Approximation for CFL
- A Constant Approximation for MCFL
- On the Approximability of SROB
- References
- Safe Lower Bounds for Graph Coloring
- Introduction
- Column Generation
- Finding Maximum-Weight Stable Sets
- Numerically Safe Bounds
- Improved Computation of Lower Bounds
- Decreasing Dual Weights for Speed
- Experimental Results
- Results of Column Generation
- Results of Branch and Price
- Results on Dense Subgraphs
- Maximum-Weight Stable Set Results
- References
- Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation
- Introduction
- Preliminaries
- Rational Function Matrices
- Independent Matching Problem
- Mixed Matrices and Mixed Polynomial Matrices
- Rank of LM-Matrices
- Combinatorial Relaxation Algorithm
- Combinatorial Relaxation
- Test for Tightness
- Matrix Modification
- Dual Updates
- Complexity Analysis
- Application to Valuated Independent Assignment
- References
- Constructing Extended Formulations from Reflection Relations
- Introduction
- Polyhedral Relations
- Reflection Relations
- Applications
- Reflection Groups
- Huffman Polytopes
- Conclusions
- References
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- Introduction
- Related Work
- Preliminaries
- The Knapsack Problem
- The Sherali-Adams and Lasserre Hierarchies
- Proof Overview
- Lower Bound for the Sherali-Adams Hierarchy for Knapsack
- A Decomposition Theorem for the Lasserre Hierarchy
- Upper Bound for the Lasserre Hierarchy for Knapsack
- Conclusion
- References
- Degree Bounded Forest Covering
- Introduction
- Relation to Degree Bounded Matroids
- Proof of the Fractional Conjecture
- References
- A Primal-Dual Algorithm for Weighted Abstract Cut Packing
- Introduction
- Overview
- The WACP Model
- Preliminaries
- Accessing the Abstract Network via an Oracle
- Outer Framework of the Algorithm
- Detailed Algorithm
- The Choice of Step Length $\theta$
- Polynomial Algorithm via Scaling
- Solving the Restricted Problems
- Step 1: Finding an Initial RACP
- Step 2: Construction of the Auxiliary Digraph
- Step 3: Finding a Generalized Path on Tight Arcs
- Step 4: Update of the RACP
- Final Thoughts
- References
- Convexification Techniques for Linear Complementarity Constraints
- Introduction
- Reformulation-Linearization Technique
- A Class of Complementarity Problems
- Convex Hull of One-Complementarity Sets
- Explicit Inequalities via Convexification of Simple Sets
- Convex Hull of C^{1,1}
- Convex Hull of C^{1,2}
- Conclusion
- References
- Iterative Packing for Demand and Hypergraph Matching
- Introduction
- Iterative Packing: An Example
- Iterative Packing for $k$-Hypergraph Demand Matching
- Improvements for 2-CS-PIP and Demand Matching
- Establishing the Integrality Gap
- A Polynomial Time Implementation
- Concluding Remarks
- References
- Universal Packet Routing with Arbitrary Bandwidths and Transit Times
- Introduction
- The Model
- Our Contribution
- Related Work
- Tight Bound for Instances with Small Dilation
- High Level Ideas for General Bounds
- Technical Analysis
- Framework
- References
- A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems
- Introduction
- Transformation to the Steiner Arborescence Problem on Layered Digraphs
- ILP Model on the Layered Digraph
- Lower and Upper Bounds by Redirecting Arcs
- Adaptive Layers Framework (ALF)
- Computational Results
- Conclusions and Future Work
- References
- Jump Number of Two-Directional Orthogonal Ray Graphs
- Introduction
- Preliminaries
- A Linear Programming Approach
- A Combinatorial Algorithm
- Discussion
- The Maximum Weight Cross-Free Matching Problem
- Summary of Results
- References
- Optimal Matching Forests and Valuated Delta-Matroids
- Introduction
- Delta-Matroids and Matching Forests
- Matching Delta-Matroids and Branching Delta-Matroids
- Delta-Matroids and Matching Forests
- A Simpler Algorithm
- Linear Programming Formulation
- Algorithm Description
- A Faster Algorithm
- References
- Fixed-Charge Transportation on a Path: Linear Programming Formulations
- Introduction
- Compact Linear Programming Formulation and Projection
- Path-Modular Inequalities
- Conclusion
- References
- Author Index
