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

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