Integer Programming and Combinatorial Optimization

Inhaltsverzeichnis

1. Frontmatter

2. Idealness of k-wise Intersecting Families

   Ahmad Abdi, Gérard Cornuéjols, Tony Huynh, Dabeen Lee

   Abstract

   A clutter is k-wise intersecting if every k members have a common element, yet no element belongs to all members. We conjecture that every 4-wise intersecting clutter is non-ideal. As evidence for our conjecture, we prove it in the binary case. Two key ingredients for our proof are Jaeger’s 8-flow theorem for graphs, and Seymour’s characterization of the binary matroids with the sums of circuits property. As further evidence for our conjecture, we also note that it follows from an unpublished conjecture of Seymour from 1975.

3. Flexible Graph Connectivity

   Approximating Network Design Problems Between 1- and 2-Connectivity David Adjiashvili, Felix Hommelsheim, Moritz Mühlenthaler

   Abstract

   Graph connectivity and network design problems are among the most fundamental problems in combinatorial optimization. The minimum spanning tree problem, the two edge-connected spanning subgraph problem (\(2\) -ECSS) and the tree augmentation problem (WTAP) are all examples of fundamental well-studied network design tasks that postulate different initial states of the network and different assumptions on the reliability of network components. In this paper we motivate and study Flexible Graph Connectivity (FGC), a problem that mixes together both the modeling power and the complexities of all aforementioned problems and more. In a nutshell, FGC asks to design a connected network, while allowing to specify different reliability levels for individual edges.

   In this paper we develop a general algorithmic approach for approximating FGC that yields approximation algorithms with ratios that are close to the known best bounds for many special cases, such as \(2\) -ECSS and WTAP. Our algorithm and analysis combine various techniques including a weight-scaling algorithm, a charging argument that uses a variant of exchange bijections between spanning trees and a factor revealing min-max-min optimization problem.

4. Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts

   Hassene Aissi, S. Thomas McCormick, Maurice Queyranne

   Abstract

   The parametric global minimum cut problem concerns a graph \(G = (V, E)\) where the cost of each edge is an affine function of a parameter \(\mu \in \mathbb {R}^d\) for some fixed dimension d. We consider the problems of finding the next breakpoint in a given direction, and finding a parameter value with maximum minimum cut value. We develop strongly polynomial algorithms for these problems that are faster than a naive application of Megiddo’s parametric search technique. Our results indicate that the next breakpoint problem is easier than the max value problem.

5. Optimizing Sparsity over Lattices and Semigroups

   Iskander Aliev, Gennadiy Averkov, Jesús A. De Loera, Timm Oertel

   Abstract

   Motivated by problems in optimization we study the sparsity of the solutions to systems of linear Diophantine equations and linear integer programs, i.e., the number of non-zero entries of a solution, which is often referred to as the \(\ell _0\)-norm. Our main results are improved bounds on the \(\ell _0\)-norm of sparse solutions to systems \(A\varvec{x}=\varvec{b}\), where \(A\in \mathbb {Z}^{m\times n}\), \({\varvec{b}}\in \mathbb {Z}^m\) and \(\varvec{x}\) is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In the lattice case and certain scenarios of the semigroup case, we give polynomial time algorithms for computing solutions with \(\ell _0\)-norm satisfying the obtained bounds.

6. A Technique for Obtaining True Approximations for k-Center with Covering Constraints

   Georg Anegg, Haris Angelidakis, Adam Kurpisz, Rico Zenklusen

   Abstract

   There has been a recent surge of interest in incorporating fairness aspects into classical clustering problems. Two recently introduced variants of the k-Center problem in this spirit are Colorful k-Center, introduced by Bandyapadhyay, Inamdar, Pai, and Varadarajan, and lottery models, such as the Fair Robust k-Center problem introduced by Harris, Pensyl, Srinivasan, and Trinh. To address fairness aspects, these models, compared to traditional k-Center, include additional covering constraints. Prior approximation results for these models require to relax some of the normally hard constraints, like the number of centers to be opened or the involved covering constraints, and therefore, only obtain constant-factor pseudo-approximations. In this paper, we introduce a new approach to deal with such covering constraints that leads to (true) approximations, including a 4-approximation for Colorful k-Center with constantly many colors—settling an open question raised by Bandyapadhyay, Inamdar, Pai, and Varadarajan—and a 4-approximation for Fair Robust k-Center, for which the existence of a (true) constant-factor approximation was also open.

   We complement our results by showing that if one allows an unbounded number of colors, then Colorful k-Center admits no approximation algorithm with finite approximation guarantee, assuming that \(\mathtt {P}\ne \mathtt {NP}\). Moreover, under the Exponential Time Hypothesis, the problem is inapproximable if the number of colors grows faster than logarithmic in the size of the ground set.

7. Tight Approximation Bounds for Maximum Multi-coverage

   Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, Emirhan Gürpınar

   Abstract

   In the classic maximum coverage problem, we are given subsets \(T_1, \dots , T_m\) of a universe [n] along with an integer k and the objective is to find a subset \(S \subseteq [m]\) of size k that maximizes \(C(S) := |\cup _{i \in S} T_i|\). It is well-known that the greedy algorithm for this problem achieves an approximation ratio of \((1-e^{-1})\) and there is a matching inapproximability result. We note that in the maximum coverage problem if an element \(e \in [n]\) is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element e as many times as it is covered, then we obtain a linear objective function, \(C^{(\infty )}(S) = \sum _{i \in S} |T_i|\), which can be easily maximized under a cardinality constraint.

   We study the maximum \(\ell \)-multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to \(\ell \) times but no more; hence, we consider maximizing the function \(C^{(\ell )}(S) = \sum _{e \in [n]} \min \{\ell , |\{i \in S : e \in T_i\}| \}\), subject to the constraint \(|S| \le k\). Note that the case of \(\ell = 1\) corresponds to the standard maximum coverage setting and \(\ell = \infty \) gives us a linear objective.

   We develop an efficient approximation algorithm that achieves an approximation ratio of \(1 - \frac{\ell ^{\ell }e^{-\ell }}{\ell !}\) for the \(\ell \)-multi-coverage problem. In particular, when \(\ell = 2\), this factor is \(1-2e^{-2} \approx 0.73\) and as \(\ell \) grows the approximation ratio behaves as \(1 - \frac{1}{\sqrt{2\pi \ell }}\). We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture.

   This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as combinatorial auctions.

8. Implementing Automatic Benders Decomposition in a Modern MIP Solver

   Pierre Bonami, Domenico Salvagnin, Andrea Tramontani

   Abstract

   We describe the automatic Benders decomposition implemented in the commercial solver IBM CPLEX. We propose several improvements to the state-of-the-art along two lines: making a numerically robust method able to deal with the general case and improving the efficiency of the method on models amenable to decomposition. For the former, we deal with: unboundedness, failures in generating cuts and scaling of the artificial variable representing the objective. For the latter, we propose a new technique to handle so-called generalized bound constraints and we use different types of normalization conditions in the Cut Generating LPs. We present computational experiments aimed at assessing the importance of the various enhancements. In particular, on our test bed of models amenable to a decomposition, our implementation is approximately 5 times faster than CPLEX default branch-and-cut. A remarkable result is that, on the same test bed, default branch-and-cut is faster than a Benders decomposition that doesn’t implement our improvements.

9. Improved Approximation Algorithms for Inventory Problems

   Thomas Bosman, Neil Olver

   Abstract

   We give new approximation algorithms for the submodular joint replenishment problem and the inventory routing problem, using an iterative rounding approach. In both problems, we are given a set of N items and a discrete time horizon of T days in which given demands for the items must be satisfied. Ordering a set of items incurs a cost according to a set function, with properties depending on the problem under consideration. Demand for an item at time t can be satisfied by an order on any day prior to t, but a holding cost is charged for storing the items during the intermediate period; the goal is to minimize the sum of the ordering and holding cost.

   Our approximation factor for both problems is \(O(\log \log \min (N,T))\); this improves exponentially on the previous best results.

10. Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles

    Michele Conforti, Samuel Fiorini, Tony Huynh, Stefan Weltge

    Abstract

    Let G be an n-node graph without two disjoint odd cycles. The algorithm of Artmann, Weismantel and Zenklusen (STOC’17) for bimodular integer programs can be used to find a maximum weight stable set in G in strongly polynomial time. Building on structural results characterizing sufficiently connected graphs without two disjoint odd cycles, we construct a size-\(O(n^2)\) extended formulation for the stable set polytope of G.

11. On a Generalization of the Chvátal-Gomory Closure

    Sanjeeb Dash, Oktay Günlük, Dabeen Lee

    Abstract

    Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (2012) considered a strengthened version of Chvátal-Gomory (CG) inequalities that use 0–1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result by considering strengthened CG inequalities that use all variable bounds. In this paper, we generalize further by considering not just variable bounds, but general linear constraints on variables. We show that all points in a rational polyhedron that satisfy such strengthened CG inequalities form a rational polyhedron.

12. Algorithms for Flows over Time with Scheduling Costs

    Dario Frascaria, Neil Olver

    Abstract

    Flows over time have received substantial attention from both an optimization and (more recently) a game-theoretic perspective. In this model, each arc has an associated delay for traversing the arc, and a bound on the rate of flow entering the arc; flows are time-varying. We consider a setting which is very standard within the transportation economic literature, but has received little attention from an algorithmic perspective. The flow consists of users who are able to choose their route but also their departure time, and who desire to arrive at their destination at a particular time, incurring a scheduling cost if they arrive earlier or later. The total cost of a user is then a combination of the time they spend commuting, and the scheduling cost they incur. We present a combinatorial algorithm for the natural optimization problem, that of minimizing the average total cost of all users (i.e., maximizing the social welfare). Based on this, we also show how to set tolls so that this optimal flow is induced as an equilibrium of the underlying game.

13. Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation

    Naveen Garg, Nikhil Kumar, András Sebő

    Abstract

    In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a 1/4-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of 8.

14. Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract)

    Anupam Gupta, Amit Kumar, Viswanath Nagarajan, Xiangkun Shen

    Abstract

    We study stochastic combinatorial optimization problems where the objective is to minimize the expected maximum load (a.k.a. the makespan). In this framework, we have a set of n tasks and m resources, where each task j uses some subset of the resources. Tasks have random sizes \(X_j\), and our goal is to non-adaptively select t tasks to minimize the expected maximum load over all resources, where the load on any resource i is the total size of all selected tasks that use i. For example, given a set of intervals in time, with each interval j having random load \(X_j\), how do we choose t intervals to minimize the expected maximum load at any time? Our technique is also applicable to other problems with some geometric structure in the relation between tasks and resources; e.g., packing paths, rectangles, and “fat” objects. Specifically, we give an \(O(\log \log m)\)-approximation algorithm for all these problems.

    Our approach uses a strong LP relaxation using the cumulant generating functions of the random variables. We also show an LP integrality gap of \(\varOmega (\log ^* m)\) even for the problem of selecting intervals on a line.

15. Continuous Facility Location on Graphs

    Tim A. Hartmann, Stefan Lendl, Gerhard J. Woeginger

    Abstract

    We study a continuous facility location problem on undirected graphs where all edges have unit length and where the facilities may be positioned at the vertices as well as at interior points of the edges. The goal is to cover the entire graph with a minimum number of facilities with covering range \(\delta >0\). In other words, we want to position as few facilities as possible subject to the condition that every point on every edge is at distance at most \(\delta \) from one of these facilities.

    We investigate this covering problem in terms of the rational parameter \(\delta \). We prove that the problem is polynomially solvable whenever \(\delta \) is a unit fraction, and that the problem is NP-hard for all non unit fractions \(\delta \). We also analyze the parametrized complexity with the solution size as parameter: The resulting problem is fixed parameter tractable for all \(\delta <3/2\), and it is W[2]-hard for all \(\delta \ge 3/2\).

16. Recognizing Even-Cycle and Even-Cut Matroids

    Cheolwon Heo, Bertrand Guenin

    Abstract

    Even-cycle matroids are elementary lifts of graphic matroids. Even-cut matroids are elementary lifts of cographic matroids. We give a polynomial time algorithm to check if a binary matroid is an even-cycle matroid. We also give a polynomial time algorithm to check if a binary matroid is an even-cut matroid. These algorithms rely on structural properties of the class of pinch-graphic matroids.

17. A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2  2 Submatrices

    Hiroshi Hirai, Yuni Iwamasa

    Abstract

    In this paper, we consider the problem of computing the rank of a block-structured symbolic matrix (a generic partitioned matrix) \(A = (A_{\alpha \beta }x_{\alpha \beta })\), where \(A_{\alpha \beta }\) is a \(2 \times 2\) matrix over a field \(\mathbf {F}\) and \(x_{\alpha \beta }\) is an indeterminate for \(\alpha = 1,2,\dots , \mu \) and \(\beta = 1,2, \dots , \nu \). This problem can be viewed as an algebraic generalization of the bipartite matching problem, and was considered by Iwata and Murota (1995). One of recent interests on this problem lies in the connection with non-commutative Edmonds’ problem by Ivanyos, Qiao and Subrahamanyam (2018), and Garg, Gurvits, Oliveiva and Wigderson (2019), where a result by Iwata and Murota implicitly says that the rank and the non-commutative rank (nc-rank) are the same for this class of symbolic matrices.

    The main result of this paper is a combinatorial \(O((\mu \nu ){^2} \min \{ \mu , \nu \})\)-time algorithm for computing the symbolic rank of a \((2 \times 2)\)-type generic partitioned matrix of size \(2\mu \times 2\nu \). Our algorithm is based on the Wong sequence algorithm by Ivanyos, Qiao, and Subrahamanyam for the nc-rank of a general symbolic matrix, but is simpler. Our proposed algorithm requires no blow-up operation, no field extension, and no additional care for bounding the bit-size. Moreover it naturally provides a maximum rank completion of A for an arbitrary field \(\mathbf {F}\).

18. Fair Colorful k-Center Clustering

    Xinrui Jia, Kshiteej Sheth, Ola Svensson

    Abstract

    An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius \(\rho \) such that there exist balls of radius \(\rho \) around k of the points that meet the coverage requirements.

    The motivation behind this problem is twofold. First, from fairness considerations: each color/group should receive a similar service guarantee, and second, from the algorithmic challenges it poses: this problem combines the difficulties of clustering along with the subset-sum problem. In particular, we show that this combination results in strong integrality gap lower bounds for several natural linear programming relaxations.

    Our main result is an efficient approximation algorithm that overcomes these difficulties to achieve an approximation guarantee of 3, nearly matching the tight approximation guarantee of 2 for the classical k-center problem which this problem generalizes.