Integer Programming and Combinatorial Optimization: 21st International Conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings (Lecture Notes in Computer Science, 12125)

✍ Scribed by Daniel Bienstock (editor), Giacomo Zambelli (editor)

• Publisher: Springer
• Year: 2020
• Tongue: English
• Leaves: 459
• Edition: 1st ed. 2020
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 21st International Conference on Integer Programming and Combinatorial Optimization, IPCO 2020, held in London, UK, in June 2020. The 33 full versions of extended abstracts presented were carefully reviewed and selected from 126 submissions. The conference is a forum for researchers and practitioners working on various aspects of integer programming and combinatorial optimization. The aim is to present recent developments in theory, computation, and applications in these areas.

✦ Table of Contents

Preface
Organization
Contents
Idealness of k-wise Intersecting Families
1 Introduction
1.1 Paper Outline
2 Cuboids
3 Proof of Theorem 2
3.1 The 8-flow Theorem
3.2 Sums of Circuits Property
3.3 Proof of Theorem 2
4 Applications and Two More Conjectures
4.1 Embedding Projective Geometries
4.2 Dyadic Fractional Packings
A Binary Matroids
B Proof of Proposition 20
References
Flexible Graph Connectivity
1 Introduction
1.1 Importance of Non-uniform Models for Network Reliability
1.2 Complexity of FGC and Its Relationship to 2-ECSS and WTAP
1.3 Main Techniques and an Overview of the Algorithm
1.4 Notation and Organization
2 The Algorithm
A Proof Sketch of Theorem 1
References
Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts
1 Introduction
1.1 Related Works
1.2 Our Results
2 Problem PNB(M)
2.1 A Deterministic Contraction Algorithm
2.2 A Randomized Contraction Algorithm
3 Problem Pmax(M)
4 Conclusion
5 Appendix
5.1 Geometric tools
References
Optimizing Sparsity over Lattices and Semigroups
1 Introduction
1.1 Lattices: Sparse Solutions of Linear Diophantine Systems
1.2 Semigroups: Sparse Solutions in Integer Programming
2 Proofs of Theorem 1 and its consequences
3 Proof of Theorem 6
A Appendix
References
A Technique for Obtaining True Approximations for k-Center with Covering Constraints
1 Introduction
1.1 Our Results
1.2 Outline of Main Technical Contributions and Paper Organization
2 A 4-approximation for C k C for =O(1)
3 The Lottery Model of Harris et al. ch5HarrisPST19
A Appendix
References
Tight Approximation Bounds for Maximum Multi-coverage
1 Introduction
1.1 Our Results and Techniques
1.2 Related Covering Problems and Submodular Function Maximization
1.3 Applications
2 Approximation Algorithm for the -Multi-coverage Problem
2.1 Proof Sketch of Theorem3
3 Concluding Remarks
References
Implementing Automatic Benders Decomposition in a Modern MIP Solver
1 Introduction
2 Benders Decomposition
3 The Master Problem
4 CGLP Improvements
4.1 Generalized Bound Constraints
4.2 CGLP Normalization
5 Computational Results
A Appendix
A.1 Proof of Lemma 1
A.2 Proof of Lemma 2
References
Improved Approximation Algorithms for Inventory Problems
1 Introduction
2 Preliminaries, Model and Technical Overview
3 Reducing to Structured Covering Problems
3.1 Bounding the Time Horizon, and Further Simplifications
4 Steiner Tree over Time
5 Submodular Cover over Time
A Some Omitted Proofs
References
Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles
1 Introduction
2 The Structure of Graphs Without Two Disjoint Odd Cycles
3 Constructing a Compact Extended Formulation
4 Dealing with Small Separations
4.1 Reducing to Edge-Induced Weights
4.2 Correctness of the Extended Formulation
A Review of the Projective Planar Case
References
On a Generalization of the Chvátal-Gomory Closure
1 Introduction
1.1 Preliminaries
2 Integer Points in a General Cylinder
3 Integer Points in a Pointed Polyhedron
3.1 Covering Polyhedra
3.2 Packing Polyhedra and General Pointed Polyhedra
4 The General Case
A Proof of Lemma5
References
Algorithms for Flows over Time with Scheduling Costs
1 Introduction
2 Model and Preliminaries
3 A Combinatorial Algorithm
4 Optimality
5 Optimal Tolls
A Some Omitted Proofs
References
Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation
1 Introduction
2 Preliminaries
3 Multicuts Versus Multiflows via 2-Connectors
4 From Fractional to Half-Integer
5 From Half-Integer to Integer
6 Lower Bounds on the Flow-Cut Gap
7 Conclusions
References
Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract)
1 Introduction
1.1 Results and Techniques
1.2 Related Work
2 Problem Definition and Preliminaries
2.1 Structure of Set Systems: The Two Assumptions
2.2 Effective Size and Random Variables
3 The General Framework
4 Applications
5 Integrality Gap Lower Bounds
A Analysis Outline
References
Continuous Facility Location on Graphs
1 Introduction
2 Notation and Technical Preliminaries
3 Parametrized Hardness Results
4 NP-Hardness Results
5 The Polynomial Time Result for 1-Covering
6 The Fixed Parameter Tractable Cases
References
Recognizing Even-Cycle and Even-Cut Matroids
1 Introduction
2 A Simple Algorithm for Recognizing Graphic Matroids
2.1 Reduction to the 3-Connected Case
2.2 Graph Representations
2.3 The Algorithm
3 A First Attempt at Generalization
3.1 Signed Graph Representations
3.2 A Bad Example
4 Pinch-Graphic Matroids
4.1 The Definition
4.2 Even-Cycle Matroids that Are Not Pinch-Graphic
4.3 Recognition: From Pinch-Graphic to Even-Cycle Matroids
5 Internally 4-Connected Pinch-Graphic Matroids
5.1 Connectivity Helps, up to a Point
5.2 Preserving Connectivity
5.3 Recognition: Is an Internally 4-Connected Matroid pinch-Graphic?
6 Taming 1-, 2-, and 3-Separations
6.1 Reduction to the 3-Connected Case
6.2 Structure of 3-Separations
A Appendix: Outline of the Proof of Theorem 7
A.1 Pinch Cographic Matroids
A.2 Sizes of Equivalence Classes
A.3 Counting Representations
References
A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 22 Submatrices
1 Introduction
2 Matching
3 Algorithm
3.1 Augmenting Trail
3.2 Finding an Augmenting Trail
3.3 Augmentation
A Bit Complexity
B Constructing an Augmenting Space-Walk and Computing the Wong Sequence
C Blow-Up Free Algorithm for Edmonds' Problem
References
Fair Colorful k-Center Clustering
1 Introduction
2 A 3-Approximation Algorithm
2.1 The Pseudo-Approximation Algorithm
2.2 Phase I
2.3 Phase II
3 Sum-of-Squares Integrality Gap
A Dynamic Programming for Dense Points
B Flow Constraints
References
Popular Branchings and Their Dual Certificates
1 Introduction
1.1 Our Problem and Results
1.2 Background and Related Work
2 Dual Certificates
3 Popular Branching Algorithm
3.1 A Simple Extension of Our Algorithm: Algorithm MinMargin
4 The Popular Arborescence Polytope of D
References
Sparse Graphs and an Augmentation Problem
1 Introduction
2 Preliminaries
2.1 Algorithmic Preliminaries
3 Preprocessing
4 The Min-Max Theorem for the Reduced Problem
5 The Algorithm for the Reduced Problem
6 The General Augmentation Problem
7 Concluding Remarks
References
About the Complexity of Two-Stage Stochastic IPs
1 Introduction
1.1 Two-Stage Stochastic Integer Programming
1.2 The Augmentation Framework
1.3 Our Results
2 The Complexity of Two-Stage Stochastic IPs
3 About the Intersection of Integer Cones
4 Proof of Lemma 2
References
Packing Under Convex Quadratic Constraints
1 Introduction
2 Preliminaries
3 A Golden Ratio Approximation Algorithm
4 The Greedy Algorithm
5 Monotone Algorithms
6 Constantly Many Packing Constraints
7 Approximation Hardness
References
Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles
1 Introduction
1.1 2-Matchings Without Short Cycles
1.2 Our Results
1.3 Key Ingredient: Extended Formulation
1.4 Organization of the Paper
2 Extended Formulation of the T-free b-factor Polytope
3 Outline of the Proof of Proposition 1
4 Algorithm
5 Concluding Remarks
A Proof of Lemma 2
B Proof of Lemma 3
References
Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds
1 Introduction
2 A Short Proof of the Dinitz-Garg-Goemans Theorem
3 Unsplittable Flows with Arc-Wise Lower Bounds
4 Combining Lower and Upper Bounds
5 Conclusion
A Illustration of UBP and LBP Augmentation Steps
B Counterexample
C Proof of Lemma 4
References
Maximal Quadratic-Free Sets
1 Introduction
1.1 Literature Review
1.2 Notation
2 Preliminaries
3 Homogeneous Quadratics
4 Including a Single Homogeneous Linear Constraint
4.1 Case 1: "026B30D a"026B30D "026B30D d"026B30D M > 1
4.2 Case 2: "026B30D a"026B30D "026B30D d"026B30D
5 Non-homogeneous Quadratics
5.1 Case 1: "026B30D a"026B30D "026B30D d"026B30D M > 1
5.2 Case 2: "026B30D a"026B30D > "026B30D d"026B30D
6 Conclusions
References
On Generalized Surrogate Duality in Mixed-Integer Nonlinear Programming
1 Introduction
2 Background
3 Generalized Surrogate Duality
4 An Algorithm for the K-surrogate Dual
4.1 A Benders' Approach
4.2 Convergence
5 Computational Enhancements
6 Computational Experiments
6.1 Experimental Setup
6.2 Computational Results
7 Conclusion
A Appendix
A.1 The Effect of Stabilization
A.2 Detailed Results for the DUALBOUND Experiment
References
The Integrality Number of an Integer Program
1 Introduction
2 The Proof of Theorem1
3 The Proof of Theorem2
References
Persistency of Linear Programming Relaxations for the Stable Set Problem
1 Introduction
2 LP Formulations for Stable Set
3 Results
4 Proof of the Main Result
4.1 The Graph G-out
4.2 The Graph G-in
4.3 The Graph G*
4.4 The Objective Vector
A Deferred proofs
References
Constructing Lattice-Free Gradient Polyhedra in Dimension Two
1 Introduction
2 An Update Procedure for n = 2 and d = 0
2.1 Convergence Towards an Optimal Solution Of ([eqMainProb]CM): Theorem1
2.2 Convergence Towards a Lattice-Free Set: Theorem2
References
Sequence Independent Lifting for the Set of Submodular Maximization Problem
1 Introduction
2 A New Class of Subadditive Function
3 Lifting for conv(P0)
3.1 Lifted Inequalities from Uplifting
3.2 Lifted Inequalities from Downlifting
4 Lifting for conv(P) with a Partition Matroid X
4.1 Multidimensional Lifting and Lifted Inequalities
4.2 Computing the Exact Lifting Function
5 Computational Experiments
A Proof of Theorem 1
B Proof Sketch of Theorem 4
References
A Fast (2 + 2/7)-Approximation Algorithm for Capacitated Cycle Covering
1 Introduction
1.1 Our Results and Techniques
2 Tree Splitting
3 The Tree Cover LP
4 Randomized Rounding
5 A Fast and Deterministic Algorithm
6 Lower Bounds
A Sketch of the Proof of Lemma1
B Sketch of the Proof of Lemma4
C Sketch of the Proof of Lemma8
D Proof of Theorem3
References
Graph Coloring Lower Bounds from Decision Diagrams
1 Introduction
2 Graph Coloring by Independent Sets
3 Decision Diagrams
4 Network Flow Model
5 Iterative Refinement Procedure
6 Implementation and Experimental Results
7 Conclusion
References
On Convex Hulls of Epigraphs of QCQPs
1 Introduction
2 A General Framework
2.1 Rewriting the SDP in Terms of a Dual Object
2.2 The Eigenvalue Structure of
2.3 The Framework
3 Symmetries in QCQPs
4 Convex Hull Results
A Proof Sketch of Lemma4
References
On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables
1 Introduction
2 Convex Hull Results
2.1 Separable Quadratic Function
2.2 Rank-One Quadratic Function
3 Computations
References
Author Index