Integer Programming and Combinatorial Optimization

We describe new algorithms for solving linear programming relaxations of very large precedence constrained production scheduling problems. We present theory that motivates a new set of algorithmic ideas that can be employed on a wide range of problems; on data sets arising in the mining industry our algorithms prove effective on problems with many millions of variables and constraints, obtaining provably optimal solutions in a few minutes of computation.

Hypergraph

k

-cut problem is a problem of finding a minimum capacity set of hyperedges whose removal divides a given hypergraph into

k

connected components. We present an algorithm for this problem which runs in strongly polynomial-time if both

k

and the rank of the hypergraph are constants. Our algorithm extends the algorithm due to Thorup (2008) for computing minimum

k

-cuts of graphs from greedy packings of spanning trees.

A fundamental difficulty when dealing with a minimization problem given by a nonlinear, convex objective function over a nonconvex feasible region, is that even if we can efficiently optimize over the convex hull of the feasible region, the optimum will likely lie in the interior of a high dimensional face, “far away” from any feasible point, yielding weak bounds. We present theory and implementation for an approach that relies on (a) the S-lemma, a major tool in convex analysis, (b) efficient projection of quadratics to lower dimensional hyperplanes, and (c) efficient computation of combinatorial bounds for the minimum distance from a given point to the feasible set, in the case of several significant optimization problems. On very large examples, we obtain significant lower bound improvements at a small computational cost.

We present a min-max formula and a polynomial time algorithm for a slight generalization of the following problem: in a simple undirected graph in which the degree of each node is at most

t

 + 1, find a maximum

t

-matching containing no member of a list

$\mathcal{K}$

of forbidden

K

t

,

t

and

K

t

 + 1

subgraphs. An analogous problem for bipartite graphs without degree bounds was solved by Makai [15], while the special case of finding a maximum square-free 2-matching in a subcubic graph was solved in [1].

Many cuts used in practice to solve mixed integer programs are derived from a basis of the linear relaxation. Every such cut is of the form

α

T

x

 ≥ 1, where

x

 ≥ 0 is the vector of non-basic variables and

α

 ≥ 0. For a point

$\bar{x}$

of the linear relaxation, we call

α

T

x

 ≥ 1 a

zero-coefficient cut

wrt.

$\bar{x}$

if

$\alpha^T \bar{x} = 0$

, since this implies

α

j

 = 0 when

$\bar{x}_j > 0$

. We consider the following problem: Given a point

$\bar{x}$

of the linear relaxation, find a basis, and a zero-coefficient cut wrt.

$\bar{x}$

derived from this basis, or provide a certificate that shows no such cut exists. We show that this problem can be solved in polynomial time. We also test the performance of zero-coefficient cuts on a number of test problems. For several instances zero-coefficient cuts provide a substantial strengthening of the linear relaxation.

In the

Steiner Network

problem we are given a graph

G

with edge-costs and connectivity requirements

r

uv

between node pairs

u

,

v

. The goal is to find a minimum-cost subgraph

H

of

G

that contains

r

uv

edge-disjoint paths for all

u

,

v

 ∈ 

V

. In

Prize-Collecting Steiner Network

problems we do not need to satisfy all requirements, but are given a

penalty function

for violating the connectivity requirements, and the goal is to find a subgraph

H

that minimizes the cost plus the penalty. The case when

r

uv

 ∈ {0,1} is the classic

Prize-Collecting Steiner Forest

problem.

In this paper we present a novel linear programming relaxation for the

Prize-Collecting Steiner Network

problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone non-decreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed in [SSW07]. We further generalize our results for element-connectivity and node-connectivity.

This paper contributes to the theory of cutting planes for mixed integer linear programs (MILPs). Minimal valid inequalities are well understood for a relaxation of an MILP in tableau form where all the nonbasic variables are continuous. In this paper we study lifting functions for the nonbasic

integer

variables starting from such minimal valid inequalities. We characterize precisely when the lifted coefficient is equal to the coefficient of the corresponding continuous variable in every minimal lifting. The answer is a nonconvex region that can be obtained as the union of convex polyhedra.

In this paper we present new edge splitting-off results maintaining all-pairs edge-connectivities of a graph. We first give an alternate proof of Mader’s theorem, and use it to obtain a deterministic

$\tilde{O}({r_{\max}}^2 \cdot n^2)$

-time complete edge splitting-off algorithm for unweighted graphs, where

r

max

denotes the maximum edge-connectivity requirement. This improves upon the best known algorithm by Gabow by a factor of

$\tilde{\Omega}(n)$

. We then prove a new structural property, and use it to further speedup the algorithm to obtain a randomized

$\tilde{O}(m + {r_{\max}}^3 \cdot n)$

-time algorithm. These edge splitting-off algorithms can be used directly to speedup various graph algorithms.

Iterative rounding and relaxation have arguably become the method of choice in dealing with unconstrained and constrained network design problems. In this paper we extend the scope of the iterative relaxation method in two directions: (1) by handling more complex degree constraints in the minimum spanning tree problem (namely

laminar

crossing spanning tree), and (2) by incorporating ‘degree bounds’ in other combinatorial optimization problems such as

matroid intersection

and

lattice polyhedra

. We give new or improved approximation algorithms, hardness results, and integrality gaps for these problems.

General purpose cutting planes have played a central role in modern IP solvers. In practice, the Gomory mixed integer cut has proven to be among the most useful general purpose cuts. One may obtain this inequality from the group relaxation of an IP, which arises by relaxing non-negativity on the basic variables. We study the mixed integer cut as a facet of the master cyclic group polyhedron and characterize its extreme points and adjacent facets in this setting. Extensions are provided under automorphic and homomorphic mappings.

In 1991, Yannakakis [17] proved that no symmetric extended formulation for the matching polytope of the complete graph

K

n

with

n

nodes has a number of variables and constraints that is bounded subexponentially in

n

. Here, symmetric means that the formulation remains invariant under all permutations of the nodes of

K

n

. It was also conjectured in [17] that “asymmetry does not help much,” but no corresponding result for general extended formulations has been found so far. In this paper we show that for the polytopes associated with the matchings in

K

n

with

$\lfloor\log n\rfloor$

edges there are non-symmetric extended formulations of polynomial size, while nevertheless no symmetric extended formulation of polynomial size exists. We furthermore prove similar statements for the polytopes associated with cycles of length

$\lfloor\log n\rfloor$

. Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot.

We consider the facility location problem where each facility can serve at most

U

clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of

$3+2\sqrt{2}$

for the same algorithm. We also provide an example which shows that our analysis is tight.

In the classical secretary problem an employer would like to choose the best candidate among

n

competing candidates that arrive in a random order. This basic concept of

n

elements arriving in a random order and irrevocable decisions made by an algorithm have been explored extensively over the years, and used for modeling the behavior of many processes. Our main contribution is a new linear programming technique that we introduce as a tool for obtaining and analyzing mechanisms for the secretary problem and its variants. The linear program is formulated using judiciously chosen variables and constraints and we show a one-to-one correspondence between mechanisms for the secretary problem and feasible solutions to the linear program. Capturing the set of mechanisms as a linear polytope holds the following immediate advantages.

Computing the optimal mechanism reduces to solving a linear program.

Proving an upper bound on the performance of any mechanism reduces to finding a feasible solution to the dual program.

Exploring variants of the problem is as simple as adding new constraints, or manipulating the objective function of the linear program.

We demonstrate these ideas by exploring some natural variants of the secretary problem. In particular, using our approach, we design optimal secretary mechanisms in which the probability of selecting a candidate at any position is equal. We refer to such mechanisms as

incentive compatible

and these mechanisms are motivated by the recent applications of secretary problems to online auctions. We also show a family of linear programs which characterize all mechanisms that are allowed to choose

J

candidates and gain profit from the

K

best candidates. We believe that linear programming based approach may be very helpful in the context of other variants of the secretary problem.

We introduce the framework of branched polyhedral systems that can be used in order to construct extended formulations for polyhedra by combining extended formulations for other polyhedra. The framework, for instance, simultaneously generalizes extended formulations like the well-known ones (see Balas [1]) for the convex hulls of unions of polyhedra (disjunctive programming) and like those obtained from dynamic programming algorithms for combinatorial optimization problems (due to Martin, Rardin, and Campbell [11]). Using the framework, we construct extended formulations for full orbitopes (the convex hulls of all 0/1-matrices with lexicographically sorted columns), we show for two special matching problems, how branched polyhedral systems can be exploited in order to construct formulations for certain nested combinatorial problems, and we indicate how one can build extended formulations for stable set polytopes using the framework of branched polyhedral systems.

We consider the following NP-hard problem: in a weighted graph, find a minimum cost set of vertices whose removal leaves a graph in which no two cycles share an edge. We obtain a constant-factor approximation algorithm, based on the primal-dual method. Moreover, we show that the integrality gap of the natural LP relaxation of the problem is Θ(log

n

), where

n

denotes the number of vertices in the graph.

A path is said to be ℓ-bounded if it contains at most ℓ edges. We consider two types of ℓ-bounded disjoint paths problems. In the maximum edge- or node-disjoint path problems MEDP(ℓ) and MNDP(ℓ), the task is to find the maximum number of edge- or node-disjoint ℓ-bounded (

s

,

t

)-paths in a given graph

G

with source

s

and sink

t

, respectively. In the weighted edge- or node-disjoint path problems WEDP(ℓ) and WNDP(ℓ), we are also given an integer

k

 ∈ ℕ and non-negative edge weights

c

e

 ∈ ℕ,

e

 ∈ 

E

, and seek for a minimum weight subgraph of

G

that contains

k

edge- or node-disjoint ℓ-bounded (

s

,

t

)-paths. Both problems are of great practical relevance in the planning of fault-tolerant communication networks, for example.

Even though length-bounded cut and flow problems have been studied intensively in the last decades, the

$\mathcal{NP}$

-hardness of some 3- and 4-bounded disjoint paths problems was still open. In this paper, we settle the complexity status of all open cases showing that WNDP(3) can be solved in polynomial time, that MEDP(4) is

$\mathcal{AP\kern-1.5ptX}$

-complete and approximable within a factor of 2, and that WNDP(4) and WEDP(4) are

$\mathcal{AP\kern-1.5ptX}$

-hard and

$\mathcal{NPO}$

-complete, respectively.

In this paper we generalize

N

-fold integer programs and two-stage integer programs with

N

scenarios to

N

-fold 4-block decomposable integer programs. We show that for fixed blocks but variable

N

, these integer programs are polynomial-time solvable for any linear objective. Moreover, we present a polynomial-time computable optimality certificate for the case of fixed blocks, variable

N

and any convex separable objective function. We conclude with two sample applications, stochastic integer programs with second-order dominance constraints and stochastic integer multi-commodity flows, which (for fixed blocks) can be solved in polynomial time in the number of scenarios and commodities and in the binary encoding length of the input data. In the proof of our main theorem we combine several non-trivial constructions from the theory of Graver bases. We are confident that our approach paves the way for further extensions.

We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. We aim for a universal solution that performs well without adaptation for any possible machine behavior. For the objective of minimizing the total weighted completion time, we design a polynomial time deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the disruptions in advance. A randomized version of this algorithm attains in expectation a ratio of

e

. We also show that both results are best possible among all universal solutions. As a direct consequence of our results, we answer affirmatively the question of whether a constant approximation algorithm exists for the offline version of the problem when machine unavailability periods are known in advance.

When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of Ω(log

n

/ loglog

n

) worse than an optimal sequence. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a non-trivial algorithm with a small constant performance guarantee.

We give a new randomized LP-rounding 1.725-approximation algorithm for the metric Fault-Tolerant Uncapacitated Facility Location problem. This improves on the previously best known 2.076-approximation algorithm of Swamy & Shmoys. To the best of our knowledge, our work provides the first application of a dependent-rounding technique in the domain of facility location. The analysis of our algorithm benefits from, and extends, methods developed for Uncapacitated Facility Location; it also helps uncover new properties of the dependent-rounding approach.

An important concept that we develop is a novel, hierarchical clustering scheme. Typically, LP-rounding approximation algorithms for facility location problems are based on partitioning facilities into disjoint clusters and opening at least one facility in each cluster. We extend this approach and construct a laminar family of clusters, which then guides the rounding procedure: this allows us to exploit properties of dependent rounding, and provides a quite tight analysis resulting in the improved approximation ratio.

This paper introduces two fundamental families of ‘quasi-polyhedra’ — polyhedra with a countably infinite number of facets — that arise in the context of integer quadratic programming. It is shown that any integer quadratic program can be reduced to the minimisation of a linear function over a quasi-polyhedron in the first family. Some fundamental properties of the quasi-polyhedra are derived, along with connections to some other well-studied convex sets. Several classes of facet-inducing inequalities are also derived. Finally, extensions to the mixed-integer case are briefly examined.

We present a new approach for exactly solving general chance constrained mathematical programs having discrete distributions. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and currently available methods are only able to find provably good solutions in certain very special cases. Our approach uses both decomposition, to enable processing subproblems corresponding to one possible outcome at a time, and integer programming techniques, to combine the results of these subproblems to yield strong valid inequalities. Computational results on a chance-constrained two-stage problem arising in call center staffing indicate the approach works significantly better than both an existing mixed-integer programming formulation

and

a simple decomposition approach that does not use strong valid inequalities. Thus, the strength of this approach results from the successful merger of stochastic programming decomposition techniques with integer programming techniques for finding strong valid inequalities.

We present a branch-and-bound algorithm for minimizing a convex quadratic objective function over integer variables subject to convex constraints. In a given node of the enumeration tree, corresponding to the fixing of a subset of the variables, a lower bound is given by the continuous minimum of the restricted objective function. We improve this bound by exploiting the integrality of the variables using suitably-defined lattice-free ellipsoids. Experiments show that our approach is very fast on both unconstrained problems and problems with box constraints. The main reason is that all expensive calculations can be done in a preprocessing phase, while a single node in the enumeration tree can be processed in linear time in the problem dimension.

We show how under certain conditions one can extend constructions of integrality gaps for semidefinite relaxations into ones that hold for stronger systems: those SDP to which the so-called

k

-level constraints of the Sherali-Adams hierarchy are added. The value of

k

above depends on properties of the problem. We present two applications, to the

Quadratic Programming

problem and to the

MaxCutGain

problem.

Our technique is inspired by a paper of Raghavendra and Steurer [Raghavendra and Steurer, FOCS 09] and our result gives a doubly exponential improvement for

Quadratic Programming

on another result by the same authors [Raghavendra and Steurer, FOCS 09]. They provide tight integrality-gap for the system above which is valid up to

k

 = (loglog

n

)

Ω(1)

whereas we give such a gap for up to

k

 = 

n

Ω(1)

.

We study the quality of equilibrium in atomic splittable routing games. We show that in single-source single-sink games on series-parallel graphs, the

price of collusion

— the ratio of the total delay of atomic Nash equilibrium to the Wardrop equilibrium — is at most 1. This proves that the existing bounds on the price of anarchy for Wardrop equilibria carry over to atomic splittable routing games in this setting.

It is well-know that the Chvátal-Gomory (CG) closure of a rational polyhedron is a rational polyhedron. In this paper, we show that the CG closure of a bounded full-dimensional ellipsoid, described by rational data, is a rational polytope. To the best of our knowledge, this is the first extension of the polyhedrality of the CG closure to a non-polyhedral set. A key feature of the proof is to verify that all non-integral points on the boundary of ellipsoids can be separated by some CG cut. Given a point

u

on the boundary of an ellipsoid that cannot be trivially separated using the CG cut parallel to its supporting hyperplane, the proof constructs a sequence of CG cuts that eventually separates

u

. The polyhedrality of the CG closure is established using this separation result and a compactness argument. The proof also establishes some sufficient conditions for the polyhedrality result for general compact convex sets.

In this paper, we consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph

G

 = (

V

 = 

V

B

 ∪ 

V

W

 ∪ 

V

R

,

E

), with local rewards

$r: E \to {\mathbb R}$

, and three types of vertices: black

V

B

, white

V

W

, and random

V

R

. The game is played by two players, White and Black: When the play is at a white (black) vertex

v

, White (Black) selects an outgoing arc (

v

,

u

). When the play is at a random vertex

v

, a vertex

u

is picked with the given probability

p

(

v

,

u

). In all cases, Black pays White the value

r

(

v

,

u

). The play continues forever, and White aims to maximize (Black aims to minimize) the limiting mean (that is, average) payoff. It was recently shown in [7] that BWR-games are polynomially equivalent with the classical Gillette games, which include many well-known subclasses, such as cyclic games, simple stochastic games (SSG′s), stochastic parity games, and Markov decision processes. In this paper, we give a new algorithm for solving BWR-games in the

ergodic case

, that is when the optimal values do not depend on the initial position. Our algorithm solves a BWR-game by reducing it, using a potential transformation, to a canonical form in which the optimal strategies of both players and the value for every initial position are obvious, since a locally optimal move in it is optimal in the whole game. We show that this algorithm is pseudo-polynomial when the number of random nodes is constant. We also provide an almost matching lower bound on its running time, and show that this bound holds for a wider class of algorithms. Let us add that the general (non-ergodic) case is at least as hard as SSG′s, for which no pseudo-polynomial algorithm is known.

In a column-restricted covering integer program (CCIP), all the non-zero entries of any column of the constraint matrix are equal. Such programs capture capacitated versions of covering problems. In this paper, we study the approximability of CCIPs, in particular, their relation to the integrality gaps of the underlying 0,1-CIP.

If the underlying 0,1-CIP has an integrality gap

O

(

γ

), and assuming that the integrality gap of the

priority version

of the 0,1-CIP is

O

(

ω

), we give a factor

O

(

γ

 + 

ω

) approximation algorithm for the CCIP. Priority versions of 0,1-CIPs (PCIPs) naturally capture

quality of service

type constraints in a covering problem.

We investigate priority versions of the line (PLC) and the (rooted) tree cover (PTC) problems. Apart from being natural objects to study, these problems fall in a class of fundamental geometric covering problems. We bound the integrality of certain classes of this PCIP by a constant. Algorithmically, we give a polytime exact algorithm for PLC, show that the PTC problem is APX-hard, and give a factor 2-approximation algorithm for it.

We consider the class of packing integer programs (PIPs) that are

column sparse

, where there is a specified upper bound

k

on the number of constraints that each variable appears in. We give an improved (

ek

 + 

o

(

k

))-approximation algorithm for

k

-column sparse PIPs. Our algorithm is based on a linear programming relaxation, and involves randomized rounding combined with alteration. We also show that the integrality gap of our LP relaxation is at least 2

k

 − 1; it is known that even special cases of

k

-column sparse PIPs are

$\Omega(\frac{k}{\log k})$

-hard to approximate.

We generalize our result to the case of maximizing monotone submodular functions over

k

-column sparse packing constraints, and obtain an

$\smash{\left(\frac{e^2k}{e-1} + o(k) \right)}$

-approximation algorithm. In obtaining this result, we prove a new property of submodular functions that generalizes the fractionally subadditive property, which might be of independent interest.

We investigate hypergraphic LP relaxations for the Steiner tree problem, primarily the partition LP relaxation introduced by Könemann et al. [Math. Programming, 2009]. Specifically, we are interested in proving upper bounds on the integrality gap of this LP, and studying its relation to other linear relaxations. Our results are the following.

Structural results:

We extend the technique of uncrossing, usually applied to families of sets, to families of partitions. As a consequence we show that any basic feasible solution to the partition LP formulation has sparse support. Although the number of variables could be exponential, the number of positive variables is at most the number of terminals.

Relations with other relaxations:

We show the equivalence of the partition LP relaxation with other known hypergraphic relaxations. We also show that these hypergraphic relaxations are equivalent to the well studied bidirected cut relaxation, if the instance is quasibipartite.

Integrality gap upper bounds:

We show an upper bound of

$\sqrt{3} \doteq 1.729$

on the integrality gap of these hypergraph relaxations in general graphs. In the special case of uniformly quasibipartite instances, we show an improved upper bound of 73/60 ≐ 1.216. By our equivalence theorem, the latter result implies an improved upper bound for the bidirected cut relaxation as well.

We consider the problem of, given an undirected graph

G

with a nonnegative weight on each edge, finding a basis of the cycle space of

G

of minimum total weight, where the total weight of a basis is the sum of the weights of its cycles. Minimum cycle bases are of interest in a variety of fields. In [13] Horton proposed a first polynomial-time algorithm where a minimum cycle basis is extracted from a polynomial-size subset of candidate cycles in

O

(

m

3

n

) by using Gaussian elimination. In a different approach, due to de Pina [7] and refined in [15], the cycles of a minimum cycle basis are determined sequentially in

O

(

m

2

n

 + 

m

n

2

log

n

). A more sophisticated hybrid algorithm proposed in [18] has the best worst-case complexity of

O

(

m

2

n

/ log

n

 + 

m

n

2

).

In this work we revisit Horton’s and de Pina’s approaches and we propose a simple hybrid algorithm which improves the worst-case complexity to

O

(

m

2

n

/ log

n

). We also present a very efficient related algorithm that relies on an adaptive independence test

à la

de Pina. Computational results on a wide set of instances show that the latter algorithm outperforms the previous algorithms by one or two order of magnitude on medium-size instances and allows to solve instances with up to 3000 vertices in a reasonable time.

We analyze the competitive ratio of algorithms for minimizing (weighted) average completion time on identical parallel machines and prove that the well-known shortest remaining processing time algorithm (SRPT) is 5/4-competitive w.r.t. the average completion time objective. For weighted completion times we give a deterministic algorithm with competitive ratio 1.791 + 

o

(

m

). This ratio holds for preemptive and non-preemptive scheduling.

Following the flurry of recent theoretical work on cutting planes from two row mixed integer group relaxations of an LP tableau, we report on some computational tests to evaluate the effectiveness of two row cuts based on lattice-free (type 2) triangles having more than one integer point on one side. A heuristic procedure to generate such triangles is presented, and then the coefficients of the integer variables are tightened by lifting. As a first step in testing the effectiveness of the triangle cuts, we make comparisons between the gap closed using Gomory mixed integer cuts for one round and the gap closed in one round using all the triangles generated by our heuristic. Our tests are carried out on different classes of randomly generated instances designed to represent different models in the literature by varying the number of integer non-basic variables, bounds and non-negativity constraints.

In the

cutting stock problem

we are given a set

T

of object types, where objects of type

T

i

 ∈ 

T

have integer length

p

i

 > 0. Given a set

O

of

n

objects containing

n

i

objects of type

T

i

, for each

i

 = 1, ...,

d

, the problem is to pack

O

into the minimum number of bins of capacity

β

. In this paper we consider the version of the problem in which the number

d

of different object types is constant and we present an algorithm that computes a solution using at most

OPT

 + 1 bins, where

OPT

is the value of an optimum solution.

We introduce a natural abstraction of propositional proof systems that are based on cutting planes. This new class of proof systems includes well-known operators such as Gomory-Chvátal cuts, lift-and-project cuts, Sherali-Adams cuts (for a fixed hierarchy level

d

), and split cuts. The rank of such a proof system corresponds to the number of rounds needed to show the nonexistence of integral solutions. We exhibit a family of polytopes without integral points contained in the

n

-dimensional 0/1-cube that has rank Ω(

n

/log

n

) for any proof system in our class. In fact, we show that whenever a specific cutting-plane based proof system has (maximal) rank

n

on a particular family of instances, then any cutting-plane proof system in our class has rank Ω(

n

/log

n

) for this family. This shows that the rank complexity of worst-case instances is intrinsic to the problem, and does not depend on specific cutting-plane proof systems, except for log factors. We also construct a new cutting-plane proof system that has worst-case rank

O

(

n

/log

n

) for any polytope without integral points, implying that the universal lower bound is essentially tight.