Integer Programming and Combinatorial Optimization

Name: Integer Programming and Combinatorial Optimization | 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings

Oktay Günlük Gerhard J. Woeginger(Herausgeber*in)

Springer (Verlag)

Erschienen am 21. Juni 2011

XIII, 432 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-20807-2 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken