Integer Programming and Combinatorial Optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings (Lecture Notes in Computer Science, 4513)

✍ Scribed by Matteo Fischetti (editor), David P. Williamson (editor)

• Publisher: Springer
• Year: 2007
• Tongue: English
• Leaves: 509
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2007, held in Ithaca, NY, USA, in June 2007.

Among the topics addressed in the 36 revised full papers are approximation algorithms, algorithmic game theory, computational biology, integer programming, polyhedral combinatorics, scheduling theory and scheduling algorithms, as well as semidefinite programs.

✦ Table of Contents

Title
Preface
Organization
Table of Contents
Inequalities from Two Rows of a Simplex Tableau
Introduction
Basic Structure of $\conv(P_I)$
A Characterization of $\conv(X_{\alpha})$ and $\conv(P_I)$
Cuts for Conic Mixed-Integer Programming
Introduction
Outline
Conic Integer Programming
Relevant Literature
A New Approach
Conic Mixed-Integer Rounding
The Simple Case
The General Case
Preliminary Computational Results
Sequential-Merge Facets for Two-Dimensional Group Problems
Introduction
Group Problem and Lifting-Space
Sequential-Merge Inequalities for Two-Dimensional Group Problems
Facet-Defining Sequential-Merge Inequalities
Conclusion
Triangle-Free Simple 2-Matchings in Subcubic Graphs (Extended Abstract)
Introduction
Main Results
The 2-Factor Polytope for Subcubic Graphs
The Algorithm for Finding Max Weight 2-matchings in Subcubic Graphs
The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
Introduction
Previous Results
Our Results
Model and Notations
Upper Bound on the Expected Number of Pareto Optimal Solutions
Lower Bounds on the Expected Number of Pareto Optimal Solutions
Smoothed Complexity of Integer Programming
Finding a Polytope from Its Graph in Polynomial Time
Introduction
2-Systems and Pseudo-polytopes
Solving Via Linear Programming
Solution and Integrality of the Linear Program
Discussion
Orbitopal Fixing
Introduction
Orbitopes
The Geometry of Fixing Variables
Fixing Variables for Orbitopes
Intersection of Orbitopes with Cube Faces
Sequential Fixing for Orbitopes
An Algorithm for Orbitopal Fixing
Computational Experiments
Concluding Remarks
New Variants of Lift-and-Project Cut Generation from the LP Tableau: Open Source Implementation and Testing
Introduction
The Correspondence Between L&P Cuts and MIG Cuts
The Lift-and-Project Procedure in the Original LP Tableau
Computation of the Reduced Cost and of the Evaluation Functions
Most Violated Cut Selection Rule
Disjunctive Modularization
Computational Results
Orbital Branching
Introduction
Preliminaries
Orbital Branching
Orbital Fixing
Comparison to Isomorphism Pruning
Implementation
Computing $\cG(\cdot)$
Branching Rules
Computational Experiments
Conclusion
Distinct Triangle Areas in a Planar Point Set
Introduction
Proof of Theorem 1
Remarks
Scheduling with Precedence Constraints of Low Fractional Dimension
Introduction
Definitions and Preliminaries
Posets and Fractional Dimension
Scheduling, Vertex Cover, and Dimension Theory
Scheduling and Fractional Dimension
Precedence Constraints with Low Fractional Dimension
Interval Orders
Interval Dimension Two
Posets of Bounded Degree
Lexicographic Sums
NP-Completeness for Interval Orders
Omitted Proofs
Proof of Theorem 2
Proof of Claim 1
Proof of Claim 3
Approximation Algorithms for 2-Stage Stochastic Scheduling Problems
Introduction
IP and LP Formulations: 2-Stage Stochastic Models
An Algorithm for the Polynomial Scenario Model
An Algorithm for the Black Box Model
An $\mathcal{NP}$-Hardness of Approximation Result
On Integer Programming and the Branch-Width of the Constraint Matrix
Introduction
Branch-Width
Linear Algebra and Branch-Width
The Main Result
Hardness Results
Bounded Variables
Matching Problems in Polymatroids Without Double Circuits
Introduction
The Partition Formula
Circuits and Compatible Double Circuits in Polymatroids
First Proof of the Partition Formula
Preliminaries
Circuits and Double Circuits in Matroids
Polymatroid Operations
Second, Constructive Proof of the Partition Formula
Projections
Blossoms
A Semi-strongly Polynomial Time Algorithm
Applications
A Parity Constrained Orientation Theorem
A Planar Rigidity Problem
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
Introduction
Preliminaries
Pipage Rounding Framework
Extensions of Submodular Functions
Sums of Weighted Rank Functions
The Generalized Assignment Problem
Conclusions
On a Generalization of the Master Cyclic Group Polyhedron
Introduction
Polyhedral Analysis of $K(n,r) $
Facet Characterization
Facets of $K(n,0)$
Separating over $K(n,r)$
Lifting Facets of $P(n,r)$
The Restricted Coefficient Polyhedron $T^{\bar\pi}$
Mixed Integer Rounding Inequalities
Mixed-Integer Extension
General Mixed-Integer Sets
Conclusion
A Framework to Derive Multidimensional Superadditive Lifting Functions and Its Applications
Introduction
Constructing Multidimensional Superadditive Lifting Functions
Lifting and Superadditive Lifting Functions
Representation of High-Dimensional Lifting Function
A Framework to Build Multidimensional Superadditive Functions
Superadditive Lifting Functions for $\01$ PCKP
Superadditive Lifting Functions for SNFCC
Conclusion
On the Exact Separation of Mixed Integer Knapsack Cuts
Introduction
Identifying Violated Knapsack Cuts
Solving the Mixed Integer Knapsack Problem
Computational Experiments
The Optimization Oracle
Knapsack Cuts
Final Remarks
A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization
Introduction
The Base Polyhedron
Distance Functions and Optimality Conditions
Distance Functions and Extreme Vectors
A Strongly Polynomial Algorithm for SFM
The Auxiliary Matrix and How to Choose $\γ$
Proof of Correctness and Time Bound
References
On Convex Minimization over Base Polytopes
Introduction
Preliminaries
Examples of Problems
Related Problems
Examples of Objective Functions
The Decomposition Algorithm
The Decomposition Algorithm and the Rationality
Equivalence of Problems
An Efficient Implementation
Submodular Function Minimization
The Fleischer-Iwata Algorithm for Parametric SFM
An Efficient Implementation of the Decomposition Algorithm
Non-separable Convex Functions
Computational Geometric Approach to Submodular Function Minimization form Multiclass Queueing Systems
Introduction
Multiclass Queueing Systems
Preemptive M/M/1
Nonpreemptive M/G/1
Geometric Approach
Lower Extreme Points
Finding the Minimum Value
Duality Between Zonotope and Hyperplane Arrangement
Extension
Conclusion
Generating Multiple Solutions for Mixed Integer Programming Problems
Introduction
Motivation
Related Work
Outline of the Paper
Definitions
Problem Definition and Complexity
Solution Diversity
Algorithms
The One-Tree Algorithm
Heuristics
The Sequential Algorithm
Computational Results
Comparison of Performance
Comparison of Diversity
Exhaustive Enumeration of Optimal Solutions
Conclusion and Future Work
A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
Introduction
The Max-Cut Problem
Semidefinite Relaxations of (MC)
Branching Rules and Heuristics
Branching Strategies
Generating Feasible Solutions
Random Data for (MC) and (QP)
Max-Cut Instances
(QP) Instances
Numerical Results
Summarizing Existing Methods and Their Limits
Numerical Results of Max-Cut Instances
Numerical Results of (QP) Instances
Equipartition
Summary
DINS, a MIP Improvement Heuristic
Introduction
Related Previous Work
Methods
Local Branching
Relaxation Induced Neighbourhood Search
Distance Induced Neighbourhood Search
Computational Results
Experimental Setup and Instance Test Bed
Comparison Among Methods
Conclusions
Mixed-Integer Vertex Covers on Bipartite Graphs
Introduction
The Main Result
First Chvátal Closure
The Motivation
The Extended Formulation
The Formulation in the Original Space
Separation
On the MIR Closure of Polyhedra
Introduction
Mixed-Integer Rounding Inequalities
Basic Properties of MIR Inequalities
The Separation Problem
Relaxed MIR Inequalities
An Approximate Separation Model
A Simple Proof That the MIR Closure Is a Polyhedron
Computational Experiments
The Intersection of Continuous Mixing Polyhedra and the Continuous Mixing Polyhedron with Flows
Introduction
Two Extended Formulations for the Intersection Set
An Extended Formulation for conv$(X^{\mathrm I}_1)$
An Extended Formulation for conv$(X^{\mathrm I}_2)$
The Difference Set
Intersection Sets with an Exponential Number of Fractional Parts
An Extended Formulation for conv$(X^{\mathrm{CMF}})$
An Extended Formulation for the Two Stage Stochastic Lot-Sizing Problem with Constant Capacities and Backlogging
Simple Explicit Formula for Counting Lattice Points of Polyhedra
Introduction
Brion's Decomposition
Notation and Definitions
Brion's Decomposition
Computing $h(y;z)$: A Primal Approach
Simplifications Via Group Theory
Simplifications Via Finite Number of Generators
Generating Function
Characterizations of Total Dual Integrality
Introduction
TDI Systems
Set Packing
Computation
Sign-Solvable Linear Complementarity Problems
Introduction
Totally Sign-Nonsingular Matrices
Sign-Solvable LCPs with Nonzero Diagonals
The Residual Row-Mixed Matrix
Characterization
Algorithm for Sign-Solvable LCPs with Nonzero Diagonals
An Integer Programming Approach for Linear Programs with Probabilistic Constraints
Introduction
The MIP Formulation
Strengthening the Formulation
A Strong Extended Formulation
Computational Experience
Comparison of Formulations
Testing Inequalities (18)
The Effect of Increasing $\epsilon$
Concluding Remarks
Infrastructure Leasing Problems
Introduction
Our Results and Techniques
Models and Notation
Observations and Reductions
Algorithms for Leasing Problems
Reduction to Multistage Stochastic Optimization
Leasing Algorithms from Existing Stochastic Algorithms
New Stochastic/Leasing Approximations
Multiple-Sink Buy-at-Bulk
Single-Sink Buy-at-Bulk Problems
Conclusions
Cost Shares and Stochastic Algorithms
Robust Combinatorial Optimization with Exponential Scenarios
Introduction
The Model
Our Contribution
An LP-Rounding Approach for Robust Set Cover
The Max-Min Problems
Improved Algorithms for Unweighted Problems
Robust Unweighted Set Cover
Robust Unweighted Vertex Cover
Robust Unweighted Edge Cover
Hardness of Max-Min Problems
Approximation Algorithms for the Multi-item Capacitated Lot-Sizing Problem Via Flow-Cover Inequalities
Introduction
A Flow-Cover-Inequality-Based LP Relaxation
Flow-Cover Inequalities
The Random-Shift Algorithm with Median Demand Assignment
Phase I: The Random-Shift Procedure
The Median Assignment
On-The-Fly Algorithm
Optimal Efficiency Guarantees for Network Design Mechanisms
Introduction
Preliminaries
An Optimal Facility Location Cost-Sharing Mechanism
Optimal Rent-or-Buy Cost-Sharing Mechanisms
An $\Omega(\log^2 k)$ Lower Bound for Steiner Tree Problems
The Set Connector Problem in Graphs
Introduction
Preliminaries
Notations
Induction Techniques
Proof of the Fractional Set Connector Packing Theorem
Approximation Algorithm
Applications
NA-Connectivity
Steiner Forest Problem
Group Steiner Tree Problem
Concluding Remarks
Author Index