2010 Book IntegerProgrammingAndCombinato
2010 Book IntegerProgrammingAndCombinato
Editorial Board
David Hutchison
Lancaster University, UK
Takeo Kanade
Carnegie Mellon University, Pittsburgh, PA, USA
Josef Kittler
University of Surrey, Guildford, UK
Jon M. Kleinberg
Cornell University, Ithaca, NY, USA
Alfred Kobsa
University of California, Irvine, CA, USA
Friedemann Mattern
ETH Zurich, Switzerland
John C. Mitchell
Stanford University, CA, USA
Moni Naor
Weizmann Institute of Science, Rehovot, Israel
Oscar Nierstrasz
University of Bern, Switzerland
C. Pandu Rangan
Indian Institute of Technology, Madras, India
Bernhard Steffen
TU Dortmund University, Germany
Madhu Sudan
Microsoft Research, Cambridge, MA, USA
Demetri Terzopoulos
University of California, Los Angeles, CA, USA
Doug Tygar
University of California, Berkeley, CA, USA
Gerhard Weikum
Max-Planck Institute of Computer Science, Saarbruecken, Germany
Friedrich Eisenbrand F. Bruce Shepherd (Eds.)
Integer Programming
and Combinatorial
Optimization
13
Volume Editors
Friedrich Eisenbrand
École Polytechnique Féderale de Lausanne
Institute of Mathematics
1015 Lausanne, Switzerland
E-mail: [email protected]
F. Bruce Shepherd
McGill University
Department of Mathematics and Statistics
805 Sherbrooke West, Montreal, Quebec, H3A 2K6, Canada
E-mail: [email protected]
ISSN 0302-9743
ISBN-10 3-642-13035-6 Springer Berlin Heidelberg New York
ISBN-13 978-3-642-13035-9 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
in its current version, and permission for use must always be obtained from Springer. Violations are liable
to prosecution under the German Copyright Law.
springer.com
© Springer-Verlag Berlin Heidelberg 2010
Printed in Germany
Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India
Printed on acid-free paper 06/3180
Preface
Programme Committee
Alper Atamtürk UC Berkeley
David Avis McGill
Friedrich Eisenbrand EPFL
Marcos Goycoolea Adolfo Ibañez
Oktay Günlük IBM
Satoru Iwata Kyoto
Tamás Király Eötvös Budapest
François Margot CMU
Bruce Shepherd (Chair) McGill
Levent Tunçel Waterloo
Santosh Vempala Georgia Tech
Peter Winkler Dartmouth
Neal E. Young UC Riverside
Local Organization
Michel Bierlaire
Jocelyne Blanc
Friedrich Eisenbrand (Chair)
Thomas Liebling
Martin Niemeier
Thomas Rothvoß
Laura Sanità
External Reviewers
Tobias Achterberg John Birge
Ernst Althaus Jaroslaw Byrka
Reid Andersen Alberto Caprara
Matthew Andrews Deeparnab Chakrabarty
Elliot Anshelevich Chandra Chekuri
Gary Au Kevin Cheung
Mourad Baiou Marek Chrobak
Nina Balcan Jose Coelho de Pina
Nikhil Bansal Michelangelo Conforti
Andre Berger Miguel Constantino
Attila Bernáth Jose Correa
Dan Bienstock Sanjeeb Dash
VIII Organization
Zero-Coefficient Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
Kent Andersen and Robert Weismantel
1 Introduction
We consider problems involving the scheduling of jobs over several periods sub-
ject to precedence constraints among the jobs as well as side-constraints. We
must choose the subset of jobs to be performed, and, for each of these jobs,
how to perform it, choosing from among a given set of options (representing
facilities or modes of operation). Finally, there are side-constraints to be satis-
fied, including period-wise, per-facility processing capacity constraints, among
others. There are standard representations of these problems as (mixed) integer
programs.
Our data sets originate in the mining industry, where problems typically have
a small number of side constraints - often well under one hundred – but may
contain millions of jobs and tens of millions of precedences, as well as spanning
multiple planning periods. Appropriate formulations often achieve small inte-
grality gap in practice; unfortunately, the linear programming relaxations are
far beyond the practical reach of commercial software.
We present a new iterative algorithm for solving the LP relaxation of this prob-
lem. The algorithm incorporates, at a low level, ideas from Lagrangian relaxation
and column generation, but is however based on fundamental observations on
the underlying combinatorial structure of precedence constrained, capacitated
optimization problems. Rather than updating dual information, the algorithm
uses primal structure gleaned from the solution of subproblems in order to ac-
celerate convergence. The general version of our ideas should be applicable to
a wide class of problems. The algorithm can be proved to converge to optimal-
ity; in practice we have found that even for problems with millions of variables
1
The first author was partially funded by a gift from BHP Billiton Ltd., and ONR
Award N000140910327.
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 1–14, 2010.
c Springer-Verlag Berlin Heidelberg 2010
2 D. Bienstock and M. Zuckerberg
t
t
Subject to: yi,τ ≤ yj,τ , ∀(i, j) ∈ A, 1 ≤ t ≤ T (2)
τ =1 τ =1
Dx ≤ d (3)
F
yj,t = xj,t,f , ∀j ∈ N , 1 ≤ t ≤ T (4)
f =1
T
yj,t ≤ 1, ∀j ∈ N (5)
t=1
x ≥ 0. (6)
2.2 Background
The Open Pit Mine Scheduling Problem. The practical motivating prob-
lem behind our study is the open pit mine scheduling problem. We are given a
three-dimensional region representing a mine to be exploited; this region is di-
vided into “blocks” (jobs, from a scheduling perspective) corresponding to units
of earth (“cubes”) that can be extracted in one step. In order for a block to be
extracted, the set of blocks located (broadly speaking) in a cone above it must
be extracted first. This gives rise to a set of precedences, i.e. to a directed graph
whose vertices are the blocks, and whose arcs represent the precedences. Finally,
the extraction of a block entails a certain (net) profit or cost.
The problem of selecting which blocks to extract so as to maximize profit can
be stated as follows:
max cT x : xi ≤ xj ∀ (i, j) ∈ A, xj ∈ {0, 1} ∀j ,
where as before A indicates the set of precedences. This is the so-called maximum
weight closure problem – in a directed graph, a closure is a set S of vertices such
that there exist no arcs (i, j) with i ∈ S and j ∈
/ S. It can be solved as a minimum
s − t cut problem in a related graph of roughly the same size. See [P76], and also
[J68], [Bal70] and [R70]. Further discussion can be found in [HC00], where the
authors note (at the end of Section 3.4) that it can be shown by reduction from
max clique that adding a single cardinality constraint to a max closure problem
is enough to make it NP-hard. For additional related material see [F06], [LG65],
[CH03], and references therein.
The problem we are concerned with here, by contrast, also incorporates pro-
duction scheduling. When a block is extracted it will be processed at one of
several facilities with different operating capabilities. The processing of a given
block i at a given facility f consumes a certain amount of processing capacity
vif and generates a certain net profit pif . This overall planning problem spans
several time periods; in each period we will have one or more knapsack (capac-
ity) constraints for each facility. We usually will also have additional, ad-hoc,
non-knapsack constraints. In this version the precedence constraints apply across
periods as per (2): if (i, j) ∈ A then j can only be extracted in the same or in a
later period than i.
Typically, we need to produce schedules spanning 10 to 20 periods. Addi-
tionally, we may have tens of thousands (or many more) blocks; this can easily
make for an optimization problem with millions of variables and tens of millions
of precedence constraints, but with (say) on the order of one hundred or fewer
processing capacity constraints (since the total number of processing facilities is
typically small).
Previous work. A great deal of research has been directed toward algorithms
for the maximum weight closure problems, starting with [LG65] and culminat-
ing in the very efficient method described in [H08] (also see [CH09]). A “nested
shells” heuristic for the capacitated, multiperiod problem, based on the work in
[LG65], is applicable to problems with a single capacity constraint, among other
4 D. Bienstock and M. Zuckerberg
3 Our Results
Empirically, it can be observed that formulation (1-6) frequently has small in-
tegrality gap. We present a new algorithm for solving the continuous relaxation
of this formulation and generalizations. Our algorithm is applicable to problems
with an arbitrary number of process options and arbitrary side constraints, and
it requires no aggregation. On very large, real-world instances our algorithm
proves very efficient.
2
We interacted with [BDFG09] as part of an industrial partnership, but our work was
performed independently.
Solving LP Relaxations of Large-Scale Precedence Constrained Problems 5
t−1
F
f
zj,t,f = xj,τ,f + xj,t,f ,
τ =1 f =1 f =1
and conversely. Thus, for an appropriate system D̄z ≤ d¯ (with the same number
of rows as Dx ≤ d) and objective c̄T z, PCPSP is equivalent to the linear program:
¯ and constraints (11)-(15)}.
min{c̄T z : D̄z ≤ d,
Let Ā be the submatrix of A containing the binding constraints at x̂. Then the
vectors θr are linearly independent and belong to the null space of Ā. As a con-
sequence, k ≤ q.
Proof: First we prove that Āθr = 0. Given a precedence constraint xi − xj ≤ 0,
if the constraint is binding then x̂i = x̂j . Thus if x̂i = αr , so that θir = 1, then
Solving LP Relaxations of Large-Scale Precedence Constrained Problems 7
x̂j = αr also, and so θjr = 1 as well, and so θir − θjr = 0. By the same token if
x̂i = αr then x̂j = αr and again θir − θjr = 0. If a constraint xi ≥ 0 or xi ≤ 1 is
binding at x̂ then naturally θir = 0 for all r as x̂i is not fractional. The supports
of the θr vectors are disjoint, yielding linear independence. Finally, k ≤ q follows
from Lemma 2.
where μ ≥ 0, and, for each q, v q ∈ {0, 1}n is the incidence vector of a closure
S q ⊂ N . [In fact, the S q can be assumed to be nested]. So for any i, j ∈ N ,
x∗j = x∗i if i and j belong to precisely the same family of sets S q . Also, Lemma 3
states that the number of distinct values that x∗j can take is small, if the number
of side constraints is small. Therefore it can be shown that when the number
of side constraints is small the number of closures (terms) in (19) must also be
small. In the full paper we show that a rich relationship exists between the max
closures produced by Lagrangian problems and the optimal dual and primal
solutions to GP CP . Next, we will develop an algorithm that solves GP CP by
attempting to “guess” the correct representation (19).
First, we present a result that partially generalizes Lemma 3.
Comment: Note that rank(Ā) can be high and thus condition (d) is not quite
as strong as Lemma 3; nevertheless q is small in any case and so we obtain
a decomposition of x̂ into “few” terms when the number of side-constraints is
“small”. Theorem 2 can be strengthened for specific families of totally unimodu-
lar matrices. For example, when A is the node-arc incidence matrix of a digraph,
the θ vectors are incidence vectors of cycles, which yields the following corollary.
Corollary 1. Let P be the feasible set for a minimum cost network flow problem
with integer data and side constraints. Let x̂ be an extreme point of P , and let
q be the number of linearly independent side constraints that are binding at x̂.
Let ζ = {j : x̂j integral}. Then x̂ can be decomposed into the sum of an integer
vector v satisfying all network flow (but not necessarily side) constraints, and
with vj = x̂j ∀j ∈ ζ, and a sum of no more than q fractional cycle flows, over a
set of cycles disjoint from ζ.
(P1 ) : max cT x
s.t. Ax ≤ b
Dx ≤ d. (21)
Denote by L(P1 , μ) the Lagrangian relaxation in which constraints (21) are du-
alized with penalties μ, i.e. the problem max{cT x + μT (d − Dx) : Ax ≤ b}.
One can approach problem P1 by means of Lagrangian relaxation, i.e. an algo-
rithm that iterates by solving multiple problems L(P1 , μ) for different choices of
μ; the multipliers μ are updated according to some procedure. A starting point
for our work concerns the fact that traditional Lagrangian relaxation schemes
(such as subgradient optimization) can prove frustratingly slow to achieve con-
vergence, often requiring seemingly instance-dependent choices of algorithmic
parameters. They also do not typically yield optimal feasible primal solutions;
in fact frequently failing to deliver a sufficiently accurate solutions (primal or
dual). However, as observed in [B02] (and also see [BA00]) Lagrangian relaxation
schemes can discover useful “structure.”
Solving LP Relaxations of Large-Scale Precedence Constrained Problems 9
The restricted linear program includes all constraints, and thus could (poten-
tially) still be very hard – the idea is that the structure we have imposed renders
the LP much easier. Further, the LP includes all constraints, and thus the solu-
tion we obtain is fully feasible for P1 , thus proving a lower bound. Moreover, if
our guess as to “structure” is correct, we also obtain a high-quality dual feasible
vector, and our use of this vector so as to restart the Lagrangian scheme should
result in accelerated convergence (as well as proving an upper bound on P1 ). In
[B02] these observations were experimentally verified in the context of several
problem classes.
(P2k ) : max cT x
s.t. Ax ≤ b, Dx ≤ d, H k x = hk .
where the first equality follows by duality and the second by definition of wk in
Step 2 since H k−1 wk = hk−1 . Also, clearly z k−1 ≤ z ∗ , and so in summary
note later that this partition never needs more than a small number of elements
for the algorithm to converge.
At iteration k, we denote by C k = {C1k , . . . , Crkk } the constructed partition of
N . Our basic application of the template is as follows:
GPCP Algorithm
1. Set μ0 = 0. Set r0 = 1, = N , C 0 = {C10 }, z 0 = −∞, and k = 1.
C10
k
2. Let y be an optimal solution to L(P1 , μk−1 ), and define
I k = {j ∈ N : yjk = 1} (23)
and define
Ok = {j ∈ N : yjk = 0}. (24)
If k > 1, and, for 1 ≤ h ≤ rk−1 , either Chk−1 ∩ I k = ∅ or Chk−1 ∩ Ok = ∅,
then STOP.
3. Let C k = {C1k , . . . , Crkk } consist of all nonempty sets in the collection
k
I ∩ Chk−1 : 1 ≤ h ≤ rk−1 ∪ Ok ∩ Chk−1 : 1 ≤ h ≤ rk−1 .
Let H k x = hk consist of the constraints:
xi = xj , for 1 ≤ h ≤ rk , and each pair i, j ∈ Chk .
4. Let P2k consist of P1 , plus the additional constraints H k x = hk .
5. Solve P2k , with optimal solution xk , and let μk denote the optimal duals
corresponding to the side-constraints Dx ≤ d. If μk = μk−1 , STOP.
6. Set k = k + 1 and goto Step 2.
We have:
Lemma 4. (a) For each k, problem P2k is an instance of GPCP with rk variables
and the same number of side-constraints as in Dx ≤ d. (b) If P21 is feasible, the
above algorithm terminates finitely with an optimal solution.
Proof: full paper.
Comments: Since each problem P2k is a GPCP, its extreme point solution xk
never attains more than m + 2 distinct values (where m is the number of linearly
independent rows in D), and thus the partition C k can be coarsened while main-
taining the feasibility of xk by merging the sets Cjk with common xk values. Note
also that in choosing C k+1 to be a refinement of C k the LP solution xk remains
available to the problem P2k+1 . The above algorithm is a basic application of
the template. Finer partitions than {I k , Ok } may also be used. The feasibility
assumption in (b) of Lemma 4 can be bypassed. Details will be provided in the
full paper.
In the full paper an analysis is presented that explains why the structure
exposed by the Lagrangian solutions can be expected to point the algorithm in
the right direction. In particular, the solution to the Lagrangian obtained by
using optimal duals for the side constraints can be shown to exhibit significant
structure.
12 D. Bienstock and M. Zuckerberg
Algorithm Performance
Iterations to 10−5
optimality 8 8 9 13 30
Time to 10−5
optimality (sec) 10 60 344 1 1076
Iterations to
comb. optimality 11 12 16 15 39
Time to comb.
optimality (sec) 15 96 649 1 1583
5 Computational Experiments
In this section we present results from some of our experiments. A more complete
set of results will be presented in the full paper. All these tests were conducted
using a single core of a dual quad-core 3.2 GHz Xeon machine with 64 GB of
memory. The LP solver we used was Cplex, version 12 and the min cut solver
we used was our implementation of Hochbaum’s pseudoflow algorithm ([H08]).
The tests reported on in Tables 1 and 2 are based on three real-world ex-
amples provided by BHP Billiton3 , to which we refer as ’Mine1’, ’Mine2’ and
’Mine3’ and a synthetic but realistic model called ’Marvin’ which is included
with Gemcom’s Whittle [W] mine planning software. ’Mine1B’ is a modifica-
tion of Mine1 with a denser precedence graph. Mine3 comes in two versions to
which we refer as ’big’ and ’small’. Using Mine1, we also obtained smaller and
larger problems by modifying the data in a number of realistic ways. Some of
the row entries in these tables are self-explanatory; the others have the following
meaning:
3
Data was masked.
Solving LP Relaxations of Large-Scale Precedence Constrained Problems 13
– Problem arcs. The number of arcs in the graph that the algorithm creates to
represent the scheduling problem (i.e., the size of the min cut problems we solve).
– Iterations, time to 10−5 optimality. The number of iterations (resp.,
the CPU time) taken by the algorithm until it obtained a solution it could
certify as having ≤ 10−5 relative optimality error.
– Iterations, time to combinatorial optimality. The number of iterations
(resp., the CPU time) taken by the algorithm to obtain a solution it could cer-
tify as optimal as per the stopping criteria in Steps 2 or 5. Notice that this
implies that the solution is optimal as per the numerical tolerances of Cplex.
Finally, an entry of ”—” indicates that Cplex was unable to terminate after 100000
seconds of CPU time. More detailed analyses will appear in the full paper.
Algorithm Performance
Iterations to 10−5
optimality 6 6 8 7 10
Time to 10−5
optimality (sec) 0 1 7 45 2875
Iterations to
comb. optimality 7 7 11 9 20
Time to comb.
optimality (sec) 0 2 10 61 6633
References
[Bal70] Balinsky, M.L.: On a selection problem. Management Science 17, 230–
231 (1970)
[BA00] Barahona, F., Anbil, R.: The Volume Algorithm: producing primal solu-
tions with a subgradient method. Math. Programming 87, 385–399 (2000)
14 D. Bienstock and M. Zuckerberg
Takuro Fukunaga
1 Introduction
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 15–28, 2010.
c Springer-Verlag Berlin Heidelberg 2010
16 T. Fukunaga
k ≥ 5. They also showed that, for the hypergraph 4-cut problem, their algorithm
achieves approximation factor 4/3.
The rest of this paper is organized as follows. Section 2 introduces basic facts
and notations. Section 3 explains outline of our result and presents our algo-
rithm. Sections 4 shows that a maximum hypertree packing contains a hyper-
tree sharing at most a constant number of hyperedges with a minimum k-cut.
Section 5 discusses a property of a set of hypertrees constructed greedily.
Section 6 concludes this paper and mentions the future works.
2 Preliminaries
The first step of our result is to prove the following theorem originally proven for
graphs by Thorup [18]. A recursively maximum hypertree packing is a maximum
hypertree packing that satisfies some condition, which will be defined formally
in Section 4.
components of V, |δE (V)| ≥ U∈V e ∈δE (U) (1/|e |). Since each e ∈ E has |e|
copies in E , e ∈δE (U) (1/|e |) = e∈δE (U) 1 = |δE (U )|. Moreover, |δE (U )| ≥ 1
because H is connected. Thus |δE (V)| ≥ U∈V 1 = |V|, which implies that H
is partition-connected. Hence by Theorem 1, H contains a hypertree.
Let us discuss the running time of this algorithm. For each hypertree, there
are O(nh ) ways to choose h hyperedges. By Corollary 1, shrinking n − 1 − h hy-
peredges in a hypertree results in a hypergraph with at most h+1 vertices. Hence
Step 3-2 can be done in O(k h+1 ) time. It means that Step 3 of the algorithm
runs in O(k h+1 nh ) time per one hypertree in T ∗ .
To bound the running time of all the steps, we must consider how to compute
a recursively maximum hypertree packing and how large its size is. A recursively
maximum hypertree packing can be computed in polynomial time. However we
know no algorithm to compute small recursively maximum hypertree packings.
Hence this paper follows the approach taken by Thorup [18] for the graph k-cut
problem. We show that a set of hypertrees constructed as below approximates a
recursively maximum hypertree packing well. It enables us to avoid computing
a recursively maximum hypertree packing.
4 Proof of Theorem 2
Let V be an arbitrary partition of V , and (T , α) be an arbitrary hypertree
packing of H. Since every hypertree T ∈ T satisfies |T | = |V | − 1 and has at
most |U | − 1 hyperedges contained by U for each U ∈ V, we have
|δT (V)| = |T | − |T [U ]| ≥ |V | − 1 − (|U | − 1) = |V| − 1. (1)
U∈V U∈V
Moreover,
c(e) ≥ α(Te ) for each e ∈ δ(V) (2)
by the definition of hypertree packings. Thus it follows that
c(δ(V)) e∈δ(V) α(Te ) α(T )|δT (V)|
≥ = T ∈T ≥ α(T ). (3)
|V| − 1 |V| − 1 |V| − 1
From now on, we let (T ∗ , α∗ ) stand for a recursively maximum hypertree pack-
ing. For U ∈ V ∗ , let T = {T [U ] | T ∈ T ∗ } and α (T [U ]) = α∗ (T )H[U] /α∗ (T ∗ )
where H[U] is the partition-connectivity of H[U ]. The definition of (T ∗ , α∗ ) im-
plies that (T , α ) is a recursively maximum hypertree packing of H[U ] for any
U ∈ V ∗.
From T ∗ and given k, define Vk as the k-partition of V constructed by the
following algorithm.
Algorithm 4: Computing Vk
Input: A connected hypergraph H = (V, E) with capacity c : E → Q+ , and an
integer k ≥ 2.
Output: A k-partition of V .
Step 1: Define Vk := {V }.
Step 2: Let U ∈ Vk be a set attaining min{H[U] | U ∈ Vk , |U | ≥ 2}. Compute
aweakest partition U = {U1 , U 2 , . . . , U|U | } of H[U ], where we assume that
∗ ∗
T ∈T ∗ α (T )|δ(Ui ) ∩ T [U ]| ≤ T ∈T ∗ α (T )|δ(Uj ) ∩ T [U ]| for 1 ≤ i < j ≤
|U|.
Step 3: If |Vk | − 1 + |U| < k, then Vk := (Vk \ {U }) ∪ U and return to Step 2.
Step 4: If |Vk | − 1 + |U| ≥ k, then Vk := (Vk \ {U }) ∪ {U1 , U2 , . . . , Uk−|Vk | , U \
k−|Vk |
∪i=1 Ui }, and output Vk .
Lemma 2
α∗ (Te∗ ) < (γk − 2)α∗ (T ∗ ).
e∈δ(Vk )
Computing Minimum Multiway Cuts in Hypergraphs 23
Proof. In this proof, Vk stands for Vk immediately before executing Step 4 of
Algorithm 4, and Vk stands for it outputted by Algorithm 4.
By the definition of recursively maximum hypertree packings, T [U ] is a hy-
∗
pertree of H[U ] for every pairof U ∈ Vk and T ∈ T . Thus |δ(Vk ) ∩ T | =
|T |− U∈V |T [U ]| = |V |−1− U∈V (|U |−1) = |Vk |−1 holds for each T ∈ T ∗ ,
k
∗ ∗
k ∗ ∗ ∗
and hence e∈δ(Vk ) α (Te ) = T ∈T ∗ α (T )|δ(Vk ) ∩ T | = (|Vk | − 1)α (T )
holds.
Let U be the element of Vk and U = {U1 , U2 , . . . , U|U | } be the weakest par-
tition of U computed in Step 2 immediately before executing Step 4. Note that
|U| > k − |Vk | holds by the condition of Step 4. By the same reason with above,
|δ(U) ∩ T [U ]| = |U| − 1 holds for each T ∈ T ∗ . Hence T ∈T ∗ α∗ (T )|δ(U) ∩
T [U ]| = (|U| − 1)α∗ (T ∗ ).
k−|V |
Let VU = {U1 , U2 , . . . , Uk−|Vk | , U \ ∪j=1 k Uj }. Then
k−|Vk |
∗
α (T )|δ(VU ) ∩ T [U ]| ≤ α∗ (T )|δ(Uj ) ∩ T [U ]|.
T ∈T ∗ j=1 T ∈T ∗
The
elements in U are ordered so that they satisfy T ∈T ∗ α∗ (T )|δ(Ui )∩T [U ]| ≤
∗
T ∈T ∗ α (T )|δ(Uj ) ∩ T [U ]| for 1 ≤ i < j ≤ |U|. Hence it holds that
k−|Vk | |U |
k − |Vk | ∗
∗
α (T )|δ(Uj ) ∩ T [U ]| ≤ α (T )|δ(Uj ) ∩ T [U ]|.
∗
|U| j=1 ∗
j=1 T ∈T T ∈T
Lemma 3. For each e ∈ δ(Vk ) and f ∈ E \ δ(Vk ), α∗ (Te∗ )/c(e) ≥ α∗ (Tf∗ )/c(f )
holds.
24 T. Fukunaga
Proof. Let U ∈ Vk denote the set containing f (i.e., f ∈ E[U ]). Let Vk denote
Vk immediately before e enters δ(Vk ) in Algorithm 4. Assume that e is contained
by U ∈ Vk (i.e., e ∈ E[U ]). Moreover, let U (resp., U ) denote the packing
value of H[U ] (resp., H[U ]).
From (T ∗ , α∗ ), define T = {T [U ] | T ∈ T ∗ }. Moreover, define α (T [U ]) =
α (T )U /α∗ (T ∗ ) for T ∈ T ∗ . By the definition of recursively maximum hyper-
∗
∗
Proof. Let η = mine∈δ(Vk ) α (Te∗ )/c(e).
By Lemma 3, each hyperedge e ∈
δ(V opt ) \ δ(Vk ) satisfies α∗ (Te∗ )/c(e) ≤ η. Hence it holds that
α∗ (Te∗ )
α∗ (Te∗ ) = c(e) ≤ ηc(δ(V opt ) \ δ(Vk )).
c(e)
e∈δ(V opt )\δ(Vk ) e∈δ(V opt )\δ(Vk )
The definition of V opt implies that c(δ(V opt )) ≤ c(δ(Vk )), and hence c(δ(V opt ) \
δ(Vk )) ≤ c(δ(Vk ) \ δ(V opt )). Thus
α∗ (T )|δ(V opt ) ∩ T | = α∗ (Te∗ ) + α∗ (Te∗ )
T ∈T ∗ e∈δ(V opt )∩δ(Vk ) e∈δ(V opt )\δ(Vk )
≤ α∗ (Te∗ ) + ηc(δ(V opt ) \ δ(Vk ))
e∈δ(V opt )∩δ(V k)
≤ α∗ (Te∗ ) + ηc(δ(Vk ) \ δ(V opt ))
e∈δ(V opt )∩δ(Vk )
≤ α∗ (Te∗ ).
e∈δ(Vk )
Computing Minimum Multiway Cuts in Hypergraphs 25
5 Proof of Theorem 5
In this section, we present a proof of Theorem 5. Although it is almost same
with that for γ = 2 presented by Thorup [18], we sketch it for self-containment.
Throughout this section, we let H = (VH , EH ) be a hypergraph such that
each e ∈ EH has at least |e| − 1 copies in EH \ {e} of the same capacity. We
denote |EH | by γm, and the capacity of hyperedges in H by cH in order to avoid
confusion. Moreover, we assume that a recursively maximum hypertree packing
(T ∗ , α∗ ) of H satisfies α∗ (Te∗ ) = α∗ (Te∗ ) for e ∈ EH and a copy e ∈ EH of e.
For a set T of hypertrees of H and e ∈ EH , define uT H (e) = |Te |/(cH (e)|T |).
For each e ∈ EH , we also define u∗H (e) as α∗ (Te∗ )/(cH (e)α∗ (T ∗ )) from a recur-
sively maximum hypertree packing (T ∗ , α∗ ) of H. Since cH (e) ≥ α∗ (Te∗ ) for all
e ∈ EH , 1/u∗H (e) is at least the packing value of H, i.e., 1/u∗H (e) ≥ α∗ (T ∗ ).
Moreover, since cH (e) = α∗ (Te∗ ) holds for some e ∈ EH by the maximality of
(T ∗ , α∗ ), mine∈EH 1/u∗H (e) = α∗ (T ∗ ) holds.
Recall that Algorithm 3 updates V ∗ by partitioning non-singleton sets in
∗
V repeatedly until no such sets exist. For e ∈ EH , define Ue as the last
set in V ∗ such that e ∈ EH [Ue ] during the execution of the algorithm. Then
maxe ∈EH [Ue ] u∗H[Ue ] (e ) = u∗H[Ue ] (e). The definition of recursively maximum hy-
pertree packings implies that u∗H[Ue ] (e ) = u∗H (e ) for each e ∈ EH [Ue ] because
α∗ (Te∗ )/α∗ (T ∗ ) = β(Se )/β(S ) holds with a maximum hypertree packing
(S , β) of H[Ue ]. Therefore, the partition-connectivity of H[Ue ] is 1/u∗H (e).
Lemma 5. Let I be a subgraph of H and assume that each hyperedge e in I
has capacity cI (e) such that cmin ≤ cI (e) ≤ cH (e). Let C = e∈EI cI (e), and
uI = maxe∈EI u∗I (e). Moreover, let be an arbitrary real such that 0 < <
1/2, and T g be a set of hypertrees in H constructed by Algorithm 2 with t ≥
3 ln(C/cmin )/(cmin uI 2 ). Then
uT
g
H (e) < (1 + )uI (4)
holds for each e ∈ EI .
Proof. Scaling hyperedge capacity makes no effect on the claim. Hence we assume
without loss of generality that cmin = 1.
Let T denote a set of hypertrees kept by Algorithm 2 at some moment during
it is running for computing T g . The key is the following quantity:
(1 + )|Te |/cH (e) (1 + uI )t−|T |
cI (e) . (5)
e∈EI
(1 + )(1+)uI t
26 T. Fukunaga
6 Concluding Remarks
References
1. Chekuri, C., Korula, N.: Personal Communication (2010)
2. Frank, A., Király, T., Kriesell, M.: On decomposing a hypergraph into k connected
sub-hypergraphs. Discrete Applied Mathematics 131(2), 373–383 (2003)
3. Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs.
Journal of Algorithms 50, 49–61 (2004)
4. Gasieniec, L., Jansson, J., Lingas, A., Óstlin, A.: On the complexity of constructing
evolutionary trees. Journal of Combinatorial Optimization 3, 183–197 (1999)
5. Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem.
Journal of the ACM 35, 921–940 (1988)
6. Goldschmidt, O., Hochbaum, D.: A polynomial algorithm for the k-cut problem
for fixed k. Mathematics of Operations Research 19, 24–37 (1994)
7. Kamidoi, Y., Yoshida, N., Nagamochi, H.: A deterministic algorithm for finding
all minimum k-way cuts. SIAM Journal on Computing 36, 1329–1341 (2006)
8. Karger, D.R., Stein, C.: A new approach to the minimum cut problem. Journal of
the ACM 43, 601–640 (1996)
9. Klimmek, R., Wagner, F.: A simple hypergraph min cut algorithm. Internal Report
B 96-02, Bericht FU Berlin Fachbereich Mathematik und Informatik (1995)
10. Lawler, E.L.: Cutsets and partitions of hypergraphs. Networks 3, 275–285 (1973)
11. Lorea, M.: Hypergraphes et matroides. Cahiers Centre Etudes Rech. Oper. 17,
289–291 (1975)
12. Lovász, L.: A generalization of König’s theorem. Acta. Math. Acad. Sci. Hungar. 21,
443–446 (1970)
13. Mak, W.-K., Wong, D.F.: A fast hypergraph min-cut algorithm for circuit parti-
tioning. Integ. VLSI J. 30, 1–11 (2000)
14. Nagamochi, H.: Algorithms for the minimum partitioning problems in graphs. IE-
ICE Transactions on Information and Systems J86-D-1, 53–68 (2003)
15. Okumoto, K., Fukunaga, T., Nagamochi, H.: Divide-and-conquer algorithms for
partitioning hypergraphs and submodular systems. In: Dong, Y., Du, D.-Z., Ibarra,
O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 55–64. Springer, Heidelberg (2009)
16. Stoer, M., Wagner, F.: A simple min-cut algorithm. J. the ACM 44, 585–591 (1997)
17. Thorup, M.: Fully-dynamic min-cut. Combinatorica 27, 91–127 (2007)
18. Thorup, M.: Minimum k-way cuts via deterministic greedy tree packing. In: Pro-
ceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 159–
166 (2008)
19. Xiao, M.: Finding minimum 3-way cuts in hypergraphs. In: Agrawal, M., Du, D.-
Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978, pp. 270–281. Springer,
Heidelberg (2008)
20. Xiao, M.: An improved divide-and-conquer algorithm for finding all minimum k-
way cuts. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS,
vol. 5369, pp. 208–219. Springer, Heidelberg (2008)
21. Zhao, L., Nagamochi, H., Ibaraki, T.: A unified framework for approximating mul-
tiway partition problems. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS,
vol. 2223, pp. 682–694. Springer, Heidelberg (2001)
Eigenvalue Techniques for Convex Objective,
Nonconvex Optimization Problems
Daniel Bienstock
1 Introduction
We consider problems with the general form
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 29–42, 2010.
c Springer-Verlag Berlin Heidelberg 2010
30 D. Bienstock
After obtaining the solution x∗ to the given relaxation for problem F , our meth-
ods will use techniques of convex analysis, of eigenvalue optimization, and com-
binatorial estimations, in order to quickly obtain a valid lower bound on F̄ which
is strictly larger than F (x∗ ). Our methods apply if F is not quadratic but there
is a convex quadratic G such that F (x) − F (x∗ ) ≥ G(x − x∗ ) for all feasible x.
We will describe an important class of problems where our method, applied
to a “cheap” but weak formulation, produces bounds comparable to or better
than those obtained by much more sophisticated formulations, and at a small
fraction of the computational cost.
Cardinality constrained optimization problems. Here, for some integer
0 < K ≤ n, K = { x ∈ Rn : x0 ≤ K }, where the zero-norm v0 of a vector
v is used to denote the number of nonzeros in v. This constraint arises in portfo-
lio optimization (see e.g. [2]) but modern applications involving this constraint
arise in statistics, machine learning [13], and, especially, in engineering and bi-
ology [19]. Problems related to compressive sensing have an explicit cardinality
constraint (see www.dsp.ece.rice.edu/cs for material). Also see [7].
The simplest canonical example of problem F is as follows:
This problem is strongly NP-hard, and it does arise in practice, exactly as stated.
In spite of its difficulty, this example already incorporates the fundamental
difficulty alluded to above: clearly, conv x ∈ Rn+ : j xj = 1, x0 ≤ K =
1.1 Techniques
Our methods embody two primary techniques:
(a) The S-lemma (see [20], also [1], [5], [15]). Let f, g : Rn → R be quadratic
functions and suppose there exists x̄ ∈ RN such that g(x̄) > 0. Then
Simple Template
S.1 Compute an optimal solution x∗ to the given relaxation to problem F .
S.2 Obtain the quantity D(x∗ ).
S.3 Apply the S-lemma as in (7), using F (x) for p(x), and (the exterior of)
the ball centered at x∗ with radius D(x∗ ) for q(x) − β.
x*
y xF
x*
In Section 1.4 we will address how to produce the quadratic q(x) and the value
D2 (y, q) when K is defined by a cardinality constraint.
Let c = ∇F (x∗ ) (other choices for c discussed in full paper). Note that for
any x ∈ P ∩ K, cT (x − x∗ ) ≥ 0. For α ≥ 0, let pα = x∗ + αc, and let H α be the
hyperplane through pα orthogonal to c. Finally, define
and let y α attain the minimum. Note: computing V (α) entails an application of
the S-lemma, “restricted” to H α . See Figure 3. Clearly, V (α) ≤ F̄ . Then
Thus, F (x∗ ) ≤ inf α≥0 V (α) ≤ F̄ ; the first inequality being strict in the positive-
definite case. [It can be shown that the “inf” is a “min”]. Each value V (α)
incorporates combinatorial information (through the quantity D2 (pα , q)) and
thus the computation of minα≥0 V (α) cannot be obtained through direct convex
optimization techniques. As a counterpoint to Theorem 1 one can prove (using
the notation in eq. (8):
Theorem 2. In (9), if C has one row and q(x) = j x2j , V ≤ inf α≥0 V (α).
c
α
H
yα
pα
x*
Updated Template
The idea here is that if (for all i) α(i+1) −α(i) is small then V (α(i) ) ≈ V (α(i+1) ).
Thus the quantity output in (2) will closely approximate minα≥0 V (α).
34 D. Bienstock
and therefore
P M P wi = P M wi = λ̂i P wi = λ̂i wi ,
as desired.
Altogether, Lemma 1 produces q − 1 eigenvalue/eigenvector pairs of P M P . The
vector in (e.2) should not be explicitly computed; rather the factorized form in
(e.2) will suffice. The root to the equation in (e.1) can be quickly obtained using
numerical methods (such as golden section search) since the expression in (e.1)
is monotonely increasing in (αi , αi+1 ) (it may also be possible to adapt the basic
trust-region algorithm [14], which addresses a similar but not identical problem).
Lemma 2. Let α be an eigenvalue of M , V α the set of columns of Q with
eigenvalue α, and A = A(α) denote the acute members of V α . If |A| > 0, then
we can construct |A| − 1 eigenvectors of P M P corresponding to eigenvalue α,
each of which is a linear combination of elements of A and is orthogonal to c.
Proof: Write m = |A|, and let H be the m × m Householder matrix [9] corre-
sponding to dA , i.e. H is a symmetric matrix with H 2 = Im such that
HdA = (dA 2 , 0, ..., 0)T ∈ Rm .
Let QA be the n × m submatrix of Q consisting of the columns corresponding
to A, and define
W = QA H. (12)
Then cT W = dTA H = (dA 2 , 0, ..., 0). In other words, the columns of the
submatrix Ŵ consisting of the last m − 1 columns of W are orthogonal to c.
Denoting by Ĥ the submatrix of H consisting of the last m − 1 columns of H,
we therefore have
Ŵ = QA Ĥ, and
P M P Ŵ = P QΛQT Ŵ = P QΛQT QA Ĥ = αP QA Ĥ = αŴ .
Finally, Ŵ T Ŵ = Ĥ T Ĥ = Im , as desired.
Now suppose that
α1 < α2 < . . . < αq
denote the distinct acute eigenvalues of M (possibly q = 0). Let p denote the
number of columns of Q which are perpendicular eigenvectors. Writing mi =
|A(αi )| > 0 for 1 ≤ i ≤ q, we have that
q
n= mi + p.
i=1
Here we take up the problem of computing strong lower bounds on the Euclidean
distance from a point to the set P ∩ K. In this abstract we will focus on the
cardinality constrained problem, but results of a similar flavor hold for the case
of disjunctive sets.
Let a ∈ Rn , b ∈ R, K < n be a positive integer, and ω ∈ Rn . Consider the
problem
⎧ ⎫
⎨n ⎬
2
Dmin (ω, a) := min (xj − ωj )2 , : aT x = b and x0 ≤ K . (13)
⎩ ⎭
j=1
Clearly, the sum of smallest n − K values ωj2 constitutes a (“naive”) lower bound
for problem (13). But it is straightforward to show that an exact solution to (13)
is obtained by choosing S ⊆ {1, . . . , n} with |S| ≤ K, so as to minimize
(b − j∈S aj ωj )2
2 + ωj2 . (14)
j∈S aj j ∈S
/
[We use the convention that 0/0 = 0.] Empirically, the naive bound mentioned
above is very weak since the first term in (14) is typically at least an order of
magnitude larger than the second; and it is the bound, rather than the set S
itself, that matters.
Suppose aj = 1 for all j. It can be shown, using (14), that the optimal set S
has the following structure: S = P ∪ N , where |P | + |N | ≤ K, and P consists of
the indices of the |P | smallest nonnegative ωj (resp., N consists of the indices
of the |N | smallest |ωj | with ωj < 0). The optimal S can be computed in O(K)
Eigenvalue Techniques for Convex Objective Problems 37
n
(x̂j − ωj )2 ≤ (1 + )Dmin
2
(ω, a),
j=1
Writing
ω̄j = aj ω j (for all
j), this becomes
n
j=1 (xj − ω̄j ) j xj = b and x0 ≤ K , which as noted above
2
min :
can be efficiently solved.
This is a simple task, since in [0, λ̃1 ) the objective in (19) is concave in μ.
Remarks:
(1) Our updated template in Section 1.2 requires the solution of multiple prob-
lems of the form (19) but just one computation of Q̃ and Λ̃.
(2) Consider any integer 1 ≤ p < n − 1. When μ < λ̃1 , the expression max-
p ṽi2
n−1 2
i=p+1 ṽi
imized in (19) is lower bounded by μβ − i=1 λ̃i −μ − λp+1 −μ . This, and
related facts, yield an approximate version of our approach which only asks for
the first p elements of the eigenspace of P M P (and M ).
Capturing the second eigenvalue. We see that Γ < λ̃1 β (and frequently this
bound is close). In experiments, the solution y ∗ to (16) often “cheats” in that y1∗
is close to zero. We can then improve on our procedure if the second projected
eigenvalue, λ̃2 , is significantly larger than λ̃1 . Assuming that is the case, pick a
value θ with y1∗2 /β < θ < 1.
n that y1 ≥ θβ
2
(a) If we assert then we may be able to strengthen the constraint
in (15) to i=1 δi (xi − x̂i )2 ≥ γ, where γ = γ(θ) > β. See Lemma 3 below. So
the assertion amounts to applying
the2 S-lemma, but using γ in place of β.
(b) Otherwise, we have that n−1 i=2 yi ≥ (1 − θ)β. In this case, instead of the
right-hand side of (19), we will have
ṽ 2
n−1
max μ(1 − θ)β − i
: 0 ≤ μ ≤ λ̃2 . (20)
λ̃ − μ
i=2 i
The minimum of the quantities obtained in (a) and (b) yields a valid lower
bound on Γ ; we can evaluate several candidates for θ and choose the strongest
bound. When λ̃2 is significantly larger than λ̃1 we often obtain an improvement
over the basic approach as in Section 1.5.
Note: the approach in this section constitutes a form of branching and in our
testing has proved very useful when λ2 > λ1 . It is, intrinsically, a combinatorial
approach, and thus not easily reproducible using convexity arguments alone.
To complete this section, we point out that the construction of the quantities
γ(β) above is based on the following observation:
Eigenvalue Techniques for Convex Objective Problems 39
2 Computational Experiments
We consider problems min{ xT M x + v T x : j xj = 1, x ≥ 0, x0 ≤ K }. The
matrix M 0 is given in its eigenvector/eigenvalue factorization QΛQT . To
stress-test our linear algebra routines, we construct Q as the product of random
rotations: as the number of rotations increases, so does the number of nonzeroes
in Q, and the overall “complexity” of M . We ran our procedure after computing
the solution to the (diagonalized) “weak” formulation
min{ y T Λy + v T x : QT x = y, xj = 1, x ≥ 0}.
j
We also ran the (again, diagonalized) perspective formulation [10], [12], a strong
conic formulation (here, λmin is the minimum λi ):
min λmin wj + (λj − λmin )yj2
j j
T
s.t. Q x = y, xj = 1
j
x2j − wj zj ≤ 0, 0 ≤ zj ≤ 1 ∀ j, (21)
zj ≤ K, xj ≤ zj ∀ j, x, w ∈ Rn+ .
j
We used the Updated Template given above, with c = ∇(x∗ ) and with the
α(i) quantities set according to the following method: (a) J = 100, and (b)
α(J) = argmax{α ≥ 0 : H α ∩ S n−1 = ∅} (S n−1 is the unit simplex). The
improvement technique involving the second eigenvalue was applied in all cases.
For the experiments in Tables 1 and 2, we used Cplex 12.1 on a single core
of a 2.66 GHz quad-core Xeon machine with 16 GB of RAM, which was never
exceeded. In the tests in Table 1, n = 2443 and the eigenvalues are from a
finance application. Q is the product of 5000 random rotations, resulting in
142712 nonzeros in Q.
Here, rQMIP refers to the weak formulation, PRSP to the perspective for-
mulation, and SLE to the approach in this paper. “LB” is the lower bound
produced by a given approach, and “sec” is the CPU time in seconds. The second
eigenvalue technique proved quite effective in all these tests.
In Table 2 we consider examples with n = 10000 and random Λ. In the table,
Nonz indicates the number of nonzeroes in Q; as this number increases the
quadratic becomes less diagonal dominant.
40 D. Bienstock
QPMIP
mip emph 3 4 10000 41685 0.0314 0.241
(16.67 sec/node)
PRSP-MIP
mip emph 2 16 14000 39550 0 0.8265
(90.4 sec/node)
mip emph 3 16 7000 19817 0 0.8099
(45.30 sec/node)
LPRSP-MIP
References
1. Ben-Tal, A., Nemirovsky, A.: Lectures on Modern Convex Optimization: Analysis,
Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization.
SIAM, Philadelphia (2001)
2. Bienstock, D.: Computational study of a family of mixed-integer quadratic pro-
gramming problems. Math. Programming 74, 121–140 (1996)
3. Bienstock, D., Zuckerberg, M.: Subset algebra lift algorithms for 0-1 integer pro-
gramming. SIAM J. Optimization 105, 9–27 (2006)
4. Bienstock, D., McClosky, B.:Tightening simple mixed-integer sets with guaranteed
bounds (submitted 2008)
5. Boyd, S., El Ghaoui, L., Feron, E., Balakrishnan, V.: Linear matrix inequalities in
system and control theory. SIAM, Philadelphia (1994)
6. Cook, W., Kannan, R., Schrijver, A.: Chv’atal closures for mixed integer programs.
Math. Programming 47, 155–174 (1990)
7. De Farias, I., Johnson, E., Nemhauser, G.: A polyhedral study of the cardinality
constrained knapsack problem. Math. Programming 95, 71–90 (2003)
8. Golub, G.H.: Some modified matrix eigenvalue problems. SIAM Review 15, 318–
334 (1973)
9. Golub, G.H., van Loan, C.: Matrix Computations. Johns Hopkins University Press,
Baltimore (1996)
10. Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0-1 mixed integer
programs. Mathematical Programming 106, 225–236 (2006)
11. Frangioni, A., Gentile, C.: SDP Diagonalizations and Perspective Cuts for a Class
of Nonseparable MIQP. Oper. Research Letters 35, 181–185 (2007)
12. Günlük, O., Linderoth, J.: Perspective Relaxation of Mixed Integer Nonlinear Pro-
grams with Indicator Variables. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.)
IPCO 2008. LNCS, vol. 5035, pp. 1–16. Springer, Heidelberg (2008)
13. Moghaddam, B., Weiss, Y., Avidan, S.: Generalized spectral bounds for sparse
LDA. In: Proc. 23rd Int. Conf. on Machine Learning, pp. 641–648 (2006)
14. Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat.
Comput. 4, 553–572 (1983)
15. Pólik, I., Terlaky, T.: A survey of the S-lemma. SIAM Review 49, 371–418 (2007)
16. Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems
with applications to large scale minimization. Math. Program 77, 273–299 (1997)
17. Stern, R.J., Wolkowicz, H.: Indefinite trust region subproblems and nonsymmetric
eigenvalue perturbations. SIAM J. Optim. 5, 286–313 (1995)
18. Sturm, J., Zhang, S.: On cones of nonnegative quadratic functions. Mathematics
of Operations Research 28, 246–267 (2003)
19. Miller, W., Wright, S., Zhang, Y., Schuster, S., Hayes, V.: Optimization methods for
selecting founder individuals for captive breeding or reintroduction of endangered
species (2009) (manuscript)
20. Yakubovich, V.A.: S-procedure in nonlinear control theory, vol. 1, pp. 62–77. Vest-
nik Leningrad University (1971)
21. Ye, Y., Zhang, S.: New results on quadratic minimization. SIAM J. Optim. 14,
245–267 (2003)
Restricted b-Matchings
in Degree-Bounded Graphs
1 Introduction
Let G = (V, E) be an undirected graph and let b : V → Z+ be an upper bound
on the nodes. An edge set F ⊆ E is called a b-matching if dF (v), the number of
edges in F incident to v, is at most b(v) for each node v. (This is often called
simple b-matching in the literature.) For some integer t ≥ 2, by a t-matching
we mean a b-matching with b(v) = t for every v ∈ V . Let K be a set consisting
of Kt,t ’s, complete bipartite subgraphs of G on two colour classes of size t, and
Kt+1 ’s, complete subgraphs of G on t + 1 nodes. The node-set and the edge-set
of a subgraph K ∈ K are denoted by VK and EK , respectively. By a K-free b-
matching we mean a b-matching not containing any member of K. In this paper,
we give a min-max formula on the size of K-free b-matchings and a polynomial
time algorithm for finding one with maximum size (that is, a K-free b-matching
F ⊆ E with maximum cardinality) under the assumptions that for any K ∈ K
and any node v of K,
VK spans no parallel edges (1)
b(v) = t (2)
dG (v) ≤ t + 1. (3)
Note that this is a generalization of the problem mentioned in the abstract. The
most important special case of K-free b-matching is to find a maximum C3 -free
Supported by the Hungarian National Foundation for Scientific Research (OTKA)
grant K60802.
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 43–56, 2010.
c Springer-Verlag Berlin Heidelberg 2010
44 K. Bérczi and L.A. Végh
the graph is subcubic was solved by the first author and Kobayashi [1]. In terms
of connectivity augmentation, the equivalent problem is augmenting an (n − 4)-
connected graph to (n − 3) connected. Our theorem is a generalization of this
result.
It is worth mentioning that the polynomial solvability of the above problems
seems to show a strong connection with jump systems. In [18], Szabó proved that
for a list K of forbidden Kt,t and Kt+1 subgraphs the degree sequences of K-free t-
matchings form a jump system in any graph. Concerning bipartite graphs,
Kobayashi and Takazawa showed [14] that the degree sequences of C≤k -free 2-
matchings do not always form a jump system for k ≥ 6. These results are con-
sistent with the polynomial solvability of the C≤k -free 2-matching problem, even
when restricting it to bipartite graphs. Similar results are known about even fac-
tors due to [13]. Although Szabó’s result suggests that finding a maximum K-free
t-matching should be solvable in polynomial time, the problem is still open.
Among our assumptions, (1) and (2) may be considered as natural ones as
they hold for the maximum Kt,t -free t-matching problem in a simple graph.
We exclude parallel edges on the node sets of members of K in order to avoid
having two different Kt,t ’s on the same two colour classes or two Kt+1 ’s on the
same ground set. However, the degree bound (3) is a restrictive assumption and
dissipates essential difficulties. Our proof strongly relies on this and the theorem
cannot be straightforwardly generalized, as it can be shown by using the example
in Chapter 6 of [20].
The proof and algorithm use the contraction technique of [11], [16] and [1].
Our contribution on the one hand is the extension of this technique for t ≥ 2 and
forbidding Kt+1 ’s as well, while on the other hand the argument is significantly
simpler than the argument in [1].
Throughout the paper we use the following notation. For an undirected graph
G = (V, E), the set of edges induced by X ⊆ V is denoted by E[X]. For disjoint
subsets X, Y of V , E[X, Y ] denotes the set of edges between X and Y . The set of
nodes in V − X adjacent to X by some edge from F ⊆ E is denoted by ΓF (X).
We let dF (v) denote the number of edges in F ⊆ E incident to v, where loops
in G are counted twice, while dF (X, Y ) stands for the number of edges going
between disjoint subsets X and Y . For a node v ∈ V , we sometimes abbreviate
the set {v} by v, e.g. dF (v,
X) is the number of edges between v and X. For a
set X ⊆ V , let hF (X) = v∈X dF (v), the sum of the number of edges incident
to X and twice the number of edges spanned by X. We use b(U ) = v∈U b(v)
for a function b : V → Z+ and a set U ⊆ V .
Let K be the list of forbidden Kt,t and Kt+1 subgraphs. For disjoint subsets
X, Y of V we denote by K[X] and K[X, Y ] the members of K contained in X
and having edges only between X and Y , respectively. That is, K[X, Y ] stands
for forbidden Kt,t ’s whose colour classes are subsets of X and Y . Recall that
VK and EK denote the node-set and edge-set of the forbidden graph K ∈ K,
respectively.
The rest of the paper is organized as follows. In Section 2 we formalize the
theorem and prove the trivial max ≤ min direction. Two shrinking operations
46 K. Bérczi and L.A. Végh
are introduced in Section 3, and Section 4 contains the proof of the max ≥ min
direction. Finally, the algorithm is presented in Section 5.
2 Main Theorem
Before stating our theorem, let us recall the well-known min-max formula on the
maximum size of a b-matching (see e.g. [17, Vol A, p. 562.]).
where U and W are disjoint subsets of V , and T ranges over the connected
components of G − U − W .
Let us now formulate our theorem. There are minor technical difficulties when
t = 2 that do not occur for larger t. In order to make both the formulation and
the proof simpler it is worth introducing the following definitions. We refer to
forbidden K2,2 and K3 subgraphs as squares and triangles, respectively.
For fixed U, W, P and K̇ the value of (5) is denoted by τ (U, W, P, K̇). It is easy
to see that the contribution of a square-full component to (5) is always 3 and
a maximum K-free b-matching contains exactly 3 of its edges. Hence we may
count these components of G separately, so the following theorem immediately
implies the general one.
Proof (of max ≤ min in Theorem 5). Let M be a K-free b-matching. Then clearly
|M ∩(E[U ]∪E[U, V −U ])| ≤ b(U ) and |M ∩E[W ]| ≤ |E[W ]|−|K̇[W ]|. Moreover,
for each T ∈ P we have
3 Shrinking
In the proof of max ≥ min we use two shrinking operations to get rid of the Kt,t
and Kt+1 subgraphs in K.
When identifying the nodes in KA and KB , the edges (and also loops) spanned
by KA and KB are replaced by loops on ka and kb , respectively. Each edge
48 K. Bérczi and L.A. Végh
KA ka
t − 1 edges
KB kb
VK
t+1
2
− 1 loops
Proof (of Lemma 8). First we show that if M is a K-free b-matching in G then
there is a K◦ -free b◦ -matching M ◦ in G◦ with |M ◦ | ≥ |M | − (t2 − t). Let M =
M −EK . Clearly, |M ∩EK | ≤ t2 −max{1, hM (KA ), hM (KB )}. In G◦ , let M ◦ be
the union of M and t− max{1, dM (ka ), dM (kb )} parallel edges from the shrunk
bundle between ka and kb . Is is easy to see that M ◦ is a K◦ -free b◦ -matching in
G◦ with |M ◦ | ≥ |M | − (t2 − t).
The proof is completed by showing that for an arbitrary K◦ -free b◦ -matching
M in G◦ there exists a K-free b-matching M in G with |M | ≥ |M ◦ | + (t2 − t).
◦
Let H denote the set of parallel edges in the shrunk bundle between ka and kb ,
and let M = M ◦ − H. Now |M ◦ ∩ H| ≤ t − max{1, dM (ka ), dM (kb )} and, by
Claim 10, M may be extended to a K-free b-matching in G with |M ∩ EK | =
t2 − max{1, hM (KA ), hM (KB )}, that is
v3 v3
v4 v1 v4 v1
v2 v2
: edges in M : edges in M
: edges in P : edges in P
v1 v2 x v1 v2 x
KA KA
K K
KB KB
v3 v4 y v3 v4 y
: edges in M
: edges in P
: edges in E \ (P ∪ M )
v4 v3 v4 v3
v1 v1
v5 v2 v5 v2
: edges in M : edges in M
: edges in P : edges in P
Fig. 5. Choice of P for t = 2 in the proof of Claim 11
52 K. Bérczi and L.A. Végh
Proof (of Lemma 9). First we show that if M is a K-free b-matching 2 in G then
there is a K◦ -free b◦ -matching M ◦ in G◦ with |M ◦ | ≥ |M | − t2 . Let M =
max{1,hM (VK )}
M − EK . Clearly, |M ∩ EK | ≤ t+1 − . In G◦ , let M ◦ be the
2 2
union of M and t−max{1,d 2
M (k)}
or t+1−max{1,d
2
M (k)}
loops on k depending
on whether t is even or not, respectively. Is
2 is easy to see that M ◦ is a K◦ -free
◦ ◦ ◦
b -matching in G with |M | ≥ |M | − 2 . t
Let H denote the set of loops on k obtained when shrinking K, and let M =
M ◦ − H. Now |M ◦ ∩ H| ≤ t−max{1,d M (k)}
if t is even and |M ◦ ∩ H| ≤
2
t+1−max{1,dM (k)}
if t is odd. By Claim 10, M can be extended modified as to
max{1,h (VK )}
2
max{1,hM (VK )} ◦
2
+ t+1 2 − 2 ≥ |M | + t
2
if t is even and
|M | = |M ◦ | − |M ◦ ∩ H| + |M ∩ EK | ≥ |M ◦ | − t+1−max{1,dM (k)}
2
max{1,hM (VK )} 2
+ t+1
2 − 2 ≥ |M ◦ | + t2
if t is odd.
4 Proof of Theorem 5
We prove max ≥ min by induction on |K|. For K = ∅, this is simply a consequence
of Theorem 1.
Assume now that K = ∅ and let K be a forbidden subgraph such that K is
uncovered if t = 2. Let G◦ = (V ◦ , E ◦ ) denote the graph obtained by shrinking
K, let b◦ be defined as in Lemma 8 or 9 depending on whether K is a Kt,t or a
Kt+1 . We denote by K◦ the list of forbidden subgraphs disjoint from K.
By induction, the maximum size of a K◦ -free b◦ -matching in G◦ is equal to the
minimum value of τ (U ◦ , W ◦ , P ◦ , K̇◦ ). Let us choose an optimal U ◦ , W ◦ , P ◦ , K˙◦
so that |U ◦ | is minimal. The following claim gives a useful property of U ◦ .
Claim 12. Assume that v ∈ U is such that d(v, W )+|Γ (v)∩(V −W )| ≤ b(v)+1.
Then τ (U −v, W, P , K̇) ≤ τ (U, W, P, K̇) where P is obtained from P by replacing
its members incident to v by their union plus v.
Proof. By removing v from U , b(U ) decreases by b(v). |E[W ]| − |K̇[W ]| remains
unchanged, while the bound on d(v, W ) + |Γ (v) ∩ (V − W )| implies that the
increment in the sum over the components of G − U − W is at most b(v).
Restricted b-Matchings in Degree-Bounded Graphs 53
1 1 3 3 3 T2 1 1 3 3 3 T1
2 3 3 3 U 2 3 3 3 W
Forbidden K3,3 τ (U, W, P, K̇) = 5 + 32 − 3 = 11
Shrinking
1 1 3 T2◦ 1 1
◦
3 T1
2 3 U◦ 2 3 W◦
τ (U ◦ , W ◦ , P ◦ , K˙◦ ) = 5
Fig. 6. Extending M ◦
Case 2: K is a Kt+1 .
By Lemma 9, the difference between the maximum size of a K-free
2 b-matching in
G and the maximum size of a K◦ -free b◦ -matching in G◦ is t2 . We show that
for the pre-images U, W and P of U ◦ , W ◦ and P ◦ with K̇ = K̇◦ ∪ {K} satisfy
54 K. Bérczi and L.A. Végh
2
τ (U, W, P, K̇) = τ (U ◦ , W ◦ , P ◦ , K˙◦ ) + t
2 . (8)
t+1
After shrinking K = (VK , EK ) we get a new node k with 2 − 1 loops on
it. (3) implies that there are at most t + 1 non-loop edges incident to k. Since
b◦ (k) ≥ t, Claim 12 implies k ∈ U . Hence we have the following two cases (T ◦
denotes a member of P ◦ ).
t+1
• k ∈ W ◦ : |E[W ]| = |E ◦ [W ◦ ]| + t+1
2 − 2 + 1 and |K̇[W ]| = |K˙◦ [W ◦ ]| + 1.
• k ∈ T ◦ : b(T ) = b◦ (T ◦ ) + t2 if t is even and b(T ) = b◦ (T ◦ ) + t2 − 1 for an
odd t.
(8) is satisfied in both cases, hence we are done. We may also leave out K from
K̇ in the second case as it is not counted in any term.
5 Algorithm
In this section we show how the proof of Theorem 5 immediately yields an
algorithm for finding a maximum K-free b-matching in strongly polynomial time.
In such problems, an important question from an algorithmic point of view is how
K is represented. For example, in the K-free b-matching problem for bipartite
graphs solved by Pap in [16], the set of excluded subgraphs may be exponentially
large. Therefore Pap assumes that K is given by a membership oracle, that is,
a subroutine is given for determining whether a given subgraph is a member
of K. However, with such an oracle there is no general method for determining
whether K = ∅. Fortunately, we do not have to tackle such problems: by the next
claim, we may assume that K is given explicitly, as its size is linear in n. We use
n = |V |, m = |E| for the number of nodes and edges of the graph, respectively.
Claim 13. If the graph G = (V, E) satisfies (1) and (3), then the total number
of Kt,t and Kt+1 subgraphs is bounded by (t+3)n
2 .
can be done in O(t3 n) time as follows. Maintain an array of size m that encodes
for each edge whether it is used in one of the selected forbidden subgraphs or
not. When increasing H, one only has to check whether any of the edges of the
examined forbidden subgraph is already used, which takes O(t2 ) time. This and
Claim 13 together give an O(t3 n) bound.
Let us shrink the members of H simultaneously (this can be easily done since
they are disjoint), resulting in a graph G = (V , E ) with a bound b : V → Z+
and no forbidden subgraphs since H was maximal. One can find a maximal b -
matching M in G in O(|V ||E | log |V |) = O(nm log m) time as in [5]. Using the
constructions described in Lemmas 8 and 9 for Hk , ..., H1 , this can be modified
into a maximal K-free b-matching M . Note that, for t = 2, Hi is always uncovered
in the actual graph by the selection rule. A dual optimal solution U, W, P, K̇ can
be constructed simultaneously as in the proof of Theorem 5. The best time bound
of the shrinking and extension steps may depend on the data structure used and
the representation of the graph. In any case, one such step may be performed in
O(m) time and |H| = O(n), hence the total running time is O(t3 n + nm log m).
References
1. Bérczi, K., Kobayashi, Y.: An Algorithm for (n − 3)–Connectivity Augmentation
Problem: Jump System Approach. Technical report, Department of Mathematical
Engineering, University of Tokyo, METR 2009-12
2. Cornuéjols, G., Pulleyblank, W.: A Matching Problem With Side Conditions. Dis-
crete Math. 29, 135–139 (1980)
3. Frank, A.: Restricted t-matchings in Bipartite Graphs. Discrete Appl. Math. 131,
337–346 (2003)
4. Frank, A., Jordán, T.: Minimal Edge-Coverings of Pairs of Sets. J. Comb. Theory
Ser. B 65, 73–110 (1995)
5. Gabow, H.N.: An Efficient Reduction Technique for Degree-Constrained Subgraph
and Bidirected Network Flow Problems. In: STOC ’83: Proceedings of the fifteenth
annual ACM symposium on Theory of computing, pp. 448–456. ACM, New York
(1983)
6. Hartvigsen, D.: Extensions of Matching Theory. PhD Thesis, Carnegie-Mellon Uni-
versity (1984)
7. Hartvigsen, D.: The Square-Free 2-factor Problem in Bipartite Graphs. In:
Cornuéjols, G., Burkard, R.E., Woeginger, G.J. (eds.) IPCO 1999. LNCS, vol. 1610,
pp. 234–241. Springer, Heidelberg (1999)
8. Hartvigsen, D.: Finding maximum square-free 2-matchings in bipartite graphs. J.
Comb. Theory Ser. B 96, 693–705 (2006)
9. Hartvigsen, D., Li, Y.: Triangle-Free Simple 2-matchings in Subcubic Graphs (Ex-
tended Abstract). In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS,
vol. 4513, pp. 43–52. Springer, Heidelberg (2007)
10. Király, Z.: C4 -free 2-factors in Bipartite Graphs. Technical report, Egerváry Re-
search Group, Department of Operations Research, Eötvös Loránd University, Bu-
dapest, TR-2001-13 (2001)
11. Király, Z.: Restricted t-matchings in Bipartite Graphs. Technical report, Egerváry
Research Group, Department of Operations Research, Eötvös Loránd University,
Budapest, TR-2009-04 (2009)
56 K. Bérczi and L.A. Végh
Otto-von-Guericke-University of Magdeburg,
Department of Mathematics/IMO, Universitätsplatz 2,
39106 Magdeburg, Germany
{andersen,weismant}@mail.math.uni-magdeburg.de
1 Introduction
This paper concerns mixed integer linear sets of the form:
Observe that P (B) can be obtained from P by deleting the non-negativity con-
straints on the basic variables xi for i ∈ B. Also observe that P (B) can be
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 57–70, 2010.
c Springer-Verlag Berlin Heidelberg 2010
58 K. Andersen and R. Weismantel
where x̄B ∈ Rn is the basic solution associated with B, and the vectors rj,B ∈ Rn
for j ∈ N \B are the extreme rays of P (B).Finally observe that every non-trivial
valid inequality for PI (B) is of the form j∈N \B αj xj ≥ 1 with αj ≥ 0 for all
j ∈ N \ B. We say that a valid inequality j∈N \B αj xj ≥ 1 for PI (B) is a valid
cut for PI that can be derived from the basis B.
Several classes of cuts can be derived from a basis. Some of these cuts are
derived from a single equation. This equation may be one of the equalities
x = x̄B + j∈N \B xj rj,B , or an integer combination of these equalities. The
integrality constraints on the variables are then used to obtain a valid cut. Single-
row cuts are named either Mixed Integer Gomory (MIG) cuts [10], Mixed Integer
Rounding (MIR) cuts [11] or Split Cuts [8].
Recent research has attempted to use several equations simultaneously to
generate valid cuts from a basis. In [3,9], two equations were considered, and
cuts named disection cuts and lifted two-variable cuts were derived. All these
cuts are intersection cuts [4], and their validity is based on lattice-free polyhedra.
This paper is motivated by the following question: Which properties should
cuts derived from bases of the linear relaxation have in order to be effective
cutting planes for mixed integer programs ? Such properties could be useful for
identifying classes of cuts that are effective in practice.
A first realization is that such cuts must be sparse, i.e., the cuts must have
many zero coefficients. Dense cuts are hard for linear programming solvers to
handle, and they have not been shown to be effective in closing the integrality
gap of mixed integer programs.
Secondly, deciding exactly which variables should have a zero coefficient in a
cut seems hard. It therefore seems natural to consider a specific point x̄ ∈ P and
aim at cuts that form solutions to the following variant of a separation problem:
min{ αj x̄j : αj xj ≥ 1 is valid for PI (B) for some basis B} (5)
j∈N \B j∈N \B
valid inequality j∈N \B αj xj ≥ 1 for PI (B) which satisfies j∈N \B αj x̄j = 0 if
such an inequality exists. The cuts we identify are split cuts, and we show that, if
there exists a zero-coefficient cut wrt. x̄, then there also exists a zero-coefficient
cut wrt. x̄ which is a split cut. The cut is computed by first pivoting to an
appropriate basis, and then computing a lattice basis of a well chosen lattice.
It has been shown that, in general, the separation problem for split cuts is
NP-hard [7]. Our result demonstrates that, if one insists on a maximally violated
split cut, then the separation problem can be solved in polynomial time. Zero-
coefficient cuts therefore seem to provide a reasonably efficient alternative to
optimizing over the split closure of a mixed integer set. The quality of the split
closure as an approximation of a mixed integer set was demonstrated in [5].
The performance of zero-coefficient cuts is tested computationally on instances
from miplib 3.0 [6] and miplib 2003 [1]. We restrict our experiments to the corner
polyhedron PI (B ∗ ) obtained from an optimal basis B ∗ of the LP relaxation. In
other words we do not examine the effect of pivoting in our experiments. On
several test problems, zero-coefficient close substantially more integrality gap
than the MIG cuts obtained from the equations defining the optimal simplex
tableau.
The remainder of the paper is organized as follows. In Sect. 2 we derive an
infeasibility certificate for the set PI (B) for a given basis B. This certificate
is key for deriving zero-coefficient cuts. Zero-coefficient cuts are motivated and
presented in Sect. 3. Our main theorem is proved in Sect. 4. Finally our compu-
tational results are presented in Sect. 5.
xj = xj , for j ∈ N \ B,
xj ≥ 0 for j ∈ N \ B }. (6)
Defining the following vectors r ∈ R for j ∈ N \ B:
j n
⎧
⎨ −āk,j if k ∈ B,
rkj := 1 if k = j, (7)
⎩
0 otherwise,
the representation (6) of P (B) can be re-written in the form
P (B) = {x ∈ Rn : x = x̄ + sj rj and sj ≥ 0 for j ∈ N \ B}. (8)
j∈N \B
60 K. Andersen and R. Weismantel
Hence PI (B) is empty if and only if the translated cone x̄ + cone({rj }j∈N \B )
does not contain mixed integer points. Our certificate for proving PI (B) is empty
is a split disjunction. A split disjunction is of the form π T x ≤ π0 ∨ π T x ≥ π0 + 1,
where (π, π0 ) ∈ Zn+1 and πj = 0 for all j ∈ N \ NI . All mixed integer points
x ∈ PI (B) satisfy all split disjunctions.
Our point of departure is a result characterizing when an affine set contains
integer points (see [2]). Specifically, consider the affine set:
T a := f + span({q j }j∈J ), (9)
Since PI (B) is the set of mixed integer points in a translate of a polyhedral cone,
we now have the following certificate for when PI (B) is empty.
Corollary 1. We have PI (B) = ∅ if and only there exists π ∈ Zn such that
π T x̄ ∈
/ Z, π T rj = 0 for all j ∈ N \ B and πj = 0 for all j ∈ N \ NI .
We now use the certificate obtained in Sect. 2 to derive zero-coefficient cuts for
a corner polyhedron PI (B) for a fixed basis B. As in Sect. 2, we let x̄ := x̄B and
rj := rj,B for j ∈ N \ B. We consider an optimization problem (MIP):
min{ cj xj : x ∈ PI (B)},
j∈N \B
where c ∈ R|N \B| denotes the objective coefficients. The linear programming
relaxation of (MIP) is denoted (LP). The set of feasible solutions to (LP) is the
set P (B). We assume cj ≥ 0 for all j ∈ N \B since otherwise (LP) is unbounded.
To motivate zero-coefficient cuts, we first consider a generic cutting plane
|N \B|
algorithm for strengthening the LP relaxation (LP) of (MIP). Let V ⊂ Q+
be a family of valid inequalities for PI (B), i.e., we have that j∈N \B αj xj ≥ 1 is
valid for PI (B) for all α ∈ V . Let x ∈ P (B) be arbitrary. A separation problem
(SEP) wrt. x can be formulated as:
min{ αj xj : α ∈ V }.
j∈N \B
In (CPalg) above, only one cut is added in every iteration. It is also possible
to add several optimal and sub-optimal solutions to (SEP). Furthermore, for
many classes V of valid cutting planes for PI (B), (SEP) can not necessarily be
62 K. Andersen and R. Weismantel
is a zero-coefficient
cut wrt. xk :
j∈N \B αj xj ≥ 1 to (LP) and re-optimize.
k
(a) Add
Let xk+1 be an optimal solution.
(b) Set k := k + 1.
End.
We next prove that, for a given point x ∈ P (B), if there exists any valid
inequality for PI (B) which is maximally violated wrt. x , then there also exists
a split cut which is maximally violated wrt. x .
Theorem 1. Let x ∈ P (B) be arbitrary. If there exists a valid inequality for
PI (B) which is a zero-coefficient cut wrt. x , then there also exists a split cut for
PI (B) which is a zero-coefficient cut wrt. x .
Proof. Let x ∈ P (B), and let j∈N \B αj xj ≥ 1 be a valid inequality for PI (B)
which is a zero-coefficient cut wrt. x . Since j∈N \B αj xj = 0 and αj , sj ≥ 0
for all j ∈ N \ B, we must have αj = 0 for all j ∈ N \ B satisfying xj > 0. Let
X := {j ∈ N \ B : xj > 0}. It follows that 0 ≥ 1 is valid for:
Observe that L(x ) is a lattice, i.e., for any π 1 , π 2 ∈ L(x ) and k ∈ Z, we have
kπ 1 ∈ L(x ) and π 1 + π 2 ∈ L(x ). For any lattice it is possible to compute a basis
for the lattice in polynomial time. Hence we can find vectors π 1 , . . . , π p ∈ L(x )
in polynomial time such that:
p
L(x ) = {π ∈ Zn : π = λi π i and λi ∈ Z for i = 1, 2, . . . , p}.
i=1
64 K. Andersen and R. Weismantel
Now, if there exists a lattice basis vector π ī ∈ L(x ) with ī ∈ {1, 2, . . . , p} such
that (π ī )T x̄ ∈
/ Z, then the split cut derived from π ī is maximally violated wrt.
x . Conversely, if we have (π i )T x̄ ∈ Z for all i ∈ {1, 2, . . . , p}, then π T x̄ ∈ Z for
all π ∈ L(x ). We therefore have the following.
Corollary 2. Let x ∈ P (B) be arbitrary. If there exists a valid inequality for
PI (B) that is maximally violated wrt. x , then it is possible to find such an
inequality in polynomial time.
Based on the above results, we have the following implementation of the cutting
plane algorithm (InitCPalg) presented earlier:
Implementation of (InitCPalg):
(1) Set k := 0. Let xk := x̄ be an optimal solution to (LP).
(2) Find a lattice basis π 1 , . . . , π pk for L(xk ).
Let I(xk ) := {i ∈ {1, . . . , pk } : (π i )T x̄ ∈
/ Z}.
(3) While I(xk ) = ∅:
(a) Add all split cuts generated from vectors π i
with i ∈ I(xk ) to (LP) and re-optimize.
Let xk+1 be an optimal solution.
(b) Find a lattice basis π 1 , . . . , π pk+1 for L(xk+1 ).
Let I(xk+1 ) := {i ∈ {1, . . . , pk+1 } : (π i )T x̄ ∈
/ Z}.
(c) Set k := k + 1.
End.
We next argue that mixed integer Gomory cuts play a natural role in the above
implementation of (InitCPalg). Consider the computation of the lattice basis for
L(x0 ) in step (2) of (InitCPalg). Observe that, since x0 = x̄, we have L(x0 ) = Zn ,
and therefore π 1 := e1 , . . . , π n := en is a lattice basis for L(x0 ), where e1 , . . . , en
denote the unit vectors in Rn . Since a split cut (10) obtained from a unit vector
is a mixed integer Gomory cut, the first cuts added in step (3).(a) of the above
implementation of (InitCPalg) are the mixed integer Gomory cuts. A natural
computational question therefore seems to be how much more integrality gap
can be closed by continuing (InitCPalg) and generating the remaining zero-
coefficient cuts.
Proof. For simplicity let x̄ := x̄B and x̄ := x̄B . Also let ā.j := (AB )−1 a.j for all
j ∈ N \ B and ā.j := (AB )−1 a.j for all j ∈ N \ B , where AB and AB denote
the basis matrices associated with the bases B and B respectively.
Suppose z ∈ PI (B). We have zi = x̄i + j∈N \B āi,j zj for all i ∈ B , zj ≥ 0 for
all j ∈ N \ (B ∪ {ī}) and zj ∈ Z for all j ∈ NI . If zī ≥ 0, we are done, so suppose
zī < 0. Choose an integer k > 0 such that kā.ī ∈ Zm and zī + k ≥ 0. Defining
zi := zi + kāi,ī for all i ∈ B , zī := zī + k and zj := zj for all j ∈ N \ (B ∪{ī}), we
have z ∈ PI (B ). Hence PI (B) = ∅ implies PI (B ) = ∅. The opposite direction
is symmetric.
From Lemma 3 it follows that either all corner polyhedra PI (B) associated with
bases B for P are empty, or they are all non-empty. We next present a pivot
operation from a basis B to an adjacent basis B with the property that, if a zero-
coefficient cut wrt. a point x ∈ P can be derived from B, then a zero-coefficient
cut wrt. x can also be derived from B .
Lemma 4. Let B be a basis for P , let x ∈ P and define X := {j ∈ N : xj > 0}.
Also let B := (B \ {ī}) ∪ {j̄} be an adjacent basis to B, where ī ∈ B \ X and
j̄ ∈ X \ B. If a zero-coefficient cut wrt. x can be derived from B, then a zero-
coefficient cut wrt. x can also be derived from B .
Proof. Given a set S ⊆ N , we will use sets obtained from P , PI , P (B) and
PI (B) by setting xj = 0 for all j ∈ N \ S. For S ⊆ N , define Q(S) := {x ∈ P :
xj = 0 for j ∈ N \ S} and QI (S) := {x ∈ PI : xj = 0 for j ∈ N \ S}. Also,
given a basis B ⊆ S, define Q(B, S) := {x ∈ P (B) : xj = 0 for j ∈ N \ S} and
QI (B, S) := {x ∈ PI (B) : xj = 0 for j ∈ N \ S}.
Assume a zero-coefficient cut wrt. x can be derived from B. Observe that this
implies PI (B, B ∪X ) = ∅. Now, PI (B, B ∪X ) is a corner polyhedron associated
with PI (B ∪ X ), and PI (B , B ∪ X ) is also a corner polyhedron associated with
PI (B ∪ X ). Since any two bases of P (B ∪ X ) can be obtained from each other
by pivoting, it follows from Lemma 3 that also PI (B , B ∪ X ) = ∅. Corollary 1
now gives a split cut which is a zero-coefficient cut wrt. x derived from B .
Lemma 4 shows that, for the purpose of identifying zero-coefficient cuts wrt. x ,
the interesting bases to consider are those bases for which it is not possible to
pivot a variable xj with j ∈ X into the basis.
Definition 1. Let x ∈ P , and define X := {j ∈ N : xj > 0}. A basis B for P
is called maximal wrt. x if (B \ {ī}) ∪ {j̄} is not a basis for P for all ī ∈ B \ X
and j̄ ∈ X \ B.
From the above results it is not clear whether it is necessary to investigate all
maximal bases wrt. x in order to identify a zero-coefficient cut wrt. x . However,
the following lemma shows that it is sufficient to examine just a single arbitrarily
chosen maximal basis wrt. x . In other words, if there exists a basis from which
a zero-coefficient cut wrt. x can be derived, then a zero-coefficient cut wrt. x
can be derived from every maximal basis wrt. x .
66 K. Andersen and R. Weismantel
Lemma 5. If there exists a basis B for P from which a zero-coefficient cut wrt.
x can be derived, then a zero-coefficient cut can be derived from every basis for
P which is maximal wrt. x .
Proof. Suppose B is a basis from which a zero-coefficient cut wrt. x can be
derived. Let J := N \ B, Bx := B ∩ X and Jx := J ∩ X . Also let x̄ := x̄B and
ā.j := (AB )−1 a.j for j ∈ J, where AB denotes the basis matrix associated with
B. Lemma 4 shows that we may assume B is maximal, i.e., we may assume that
the simplex tableau associated with B is of the form:
xi = 0 + āi,j xj for all i ∈ B \ Bx , (15)
j∈J\Jx
xi = x̄i + āi,j xj + āi,j xj for all i ∈ Bx . (16)
j∈Jx j∈J\Jx
Furthermore, from any basis B for P which is maximal wrt. x , a basic poly-
hedron T (B ) of T can be associated of the above form, and a zero-coefficient
cut wrt. x can be derived from B if and only if T (B ) does not contain mixed
integer points. Since T (B) does not contain mixed integer points, it follows from
Lemma 3 that every basic polyhedron T (B ) for T does not contain mixed in-
teger points. Hence a zero-coefficient cut can be derived from every basis B for
P which is maximal wrt. x .
Since a maximal basis wrt. x ∈ P can be obtained in polynomial time, we
immediately have our main theorem.
Theorem 2. Let x ∈ P be arbitrary. If there exists basis B, and a valid inequal-
ity for PI (B) which is a zero-coefficient cut wrt. x , then such a zero-coefficient
cut can be obtained in polynomial time.
5 Computational Results
We now test the performance of the cutting plane algorithm (InitCPalg) de-
scribed in Sect. 3. In our implementation, we use CPLEX 9.1 for solving linear
Zero-Coefficient Cuts 67
programs, and the open source software NTL for the lattice computations. We
use instances from miplib 3.0 [6] and miplib 2003 [1] in our experiments. All in-
stances are minimization problems, and we use the preprocessed version of each
instance, i.e., when we refer to an instance, we refer to the instance obtained
after applying the preprocessor of CPLEX 9.1.
For each instance, we formulate the optimization problem over the corner
polyhedron associated with an optimal basis of the LP relaxation. To distin-
guish the optimization problem over the corner polyhedron from the original
mixed integer program, we use the following notation: The original mixed inte-
ger program is denoted (MIP), and the mixed integer program over the corner
polyhedron is denoted (MIPc ). The optimal objective of (MIP) is denoted z MIP ,
c
and the optimal objective value of (MIPc ) is denoted z MIP . The LP relaxation
of (MIP) is denoted (LP), and the optimal objective value of (LP) is denoted
z LP .
We assume the (original) mixed integer program (MIP) has n variables, and
includes slack, surplus and artificial variables in the formulation:
min cT x
such that
aTi. x = bi , for all i ∈ M, (18)
lj ≤ xj ≤ uj , for all j ∈ N, (19)
xj ∈ Z, for all j ∈ NI . (20)
where M is an index set for the constraints, c ∈ Qn+|M| denotes the objective
coefficients, N := {1, 2, . . . , (n + |M |)} is an index set for the variables, NI ⊆ N
denotes those variables that are integer constrained, l and u are the lower and
upper bounds on the variables respectively and (ai. , bi ) ∈ Q|N |+1 for i ∈ M
denotes the coefficients in the ith constraint. The variables xn+i for i ∈ M are
either slack, surplus or artificial variables.
The problem (MIPc ) is formulated as follows. An optimal basis for (LP) is an
|M |-subset B ∗ ⊆ N of basic variables. Let J ∗ := N \ B ∗ denote the non-basic
variables. The problem (MIPc ) can be constructed from (MIP) by eliminating
∗
certain bounds on the variables. Let JA denote the non-basic artificial variables,
∗ ∗ ∗
let JL ⊆ J \ JA denote the non-basic structural variables on lower bound, and
let JU∗ ⊆ J ∗ \ JA
∗
denote the non-basic structural variables on upper bound. By
re-defining the bounds on the variables xj for j ∈ N to:
⎧ ∗
⎧ ∗
⎨0 if j ∈ JA , ⎨0 if j ∈ JA ,
∗ ∗
lj (B ) := lj if j ∈ JL , and uj (B ):= uj if j ∈ JU∗ ,
∗
(21)
⎩ ⎩
−∞ otherwise, +∞ otherwise,
then the problem (MIPc ) associated with B ∗ is given by:
min cT x
such that
aTi. x = bi , for all i ∈ M, (22)
68 K. Andersen and R. Weismantel
Table 2. Instances where the increase in objective with all ZC cuts was substantially
larger than the increase in objective with only MIG cuts
ΔObj. MIG cuts
Problem # Constr. # Var. # MIG # Additional ΔObj. All cuts × 100%
cuts ZC cuts
l152lav 97 1988 53 6 0.00%
mkc∗ 1286 3230 119 29 0.00%
p0201 107 183 42 27 0.00%
p2756 702 2642 201 7 6.02%
rout 290 555 52 36 6.24%
swath 482 6260 80 26 7.58%
vpm1 114 188 15 40 22.38%
vpm2 128 188 29 29 22.73%
flugpl 13 14 13 5 23.36%
fixnet6 477 877 12 19 27.06%
timtab2∗ 287 648 237 653 29.85%
timtab1∗ 166 378 133 342 30.93%
egout 35 47 8 5 41.47%
qnet1 363 1417 55 47 45.05%
p0282 160 200 34 53 49.60%
air04 614 7564 290 30 50.53%
modglob 286 384 60 28 56.77%
mas76 12 148 11 11 65.77%
pp08a 133 234 51 34 66.16%
10teams 210 1600 179 76 66.67%
mod008 6 319 5 10 69.77%
nsrand-ipx 590 4162 226 91 73.17%
Table 2 contains those instances where MIG cuts closed less than 80% of the
total integrality gap that can be closed with zero-coefficient cuts. We observe
that for the first 16 instances in Table 2, continuing (InitCPalg) beyond MIG
cuts closed at least twice as much integrality gap as would have been achieved
70 K. Andersen and R. Weismantel
by using only MIG cuts. For the remaining instances in Table 2, it was not at
least a factor of two which was achieved, but still a substantial improvement.
The instances marked with an asterisk in Table 2 are instances where we were
unable to solve (MIPc ). For those instances, the results are based on the best
possible solution we were able to find.
The remaining class of instances are those instances where MIG cuts closed
more than 80% of the total integrality gap that can be closed with zero-coefficient
cuts. There were 28 of these instances. For these instances, continuing (InitC-
Palg) beyond MIG cuts was therefore not beneficial. However, we observe that
for all except two of these instances (markshare1 and markshare2), this was
because very few zero-coefficient cuts were generated that are not MIG cuts.
Detecting that it is not beneficial to continue (InitCPalg) beyond the generation
of MIG cuts was therefore done after only very few lattice basis computations.
References
1. Achterberg, T., Koch, T.: MIPLIB 2003. Operations Research Letters 34, 361–372
(2006)
2. Andersen, K., Louveaux, Q., Weismantel, R.: Certificates of linear mixed integer
infeasibility. Operations Research Letters 36, 734–738 (2008)
3. Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.A.: Inequalities from Two
Rows of a Simplex Tableau. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007.
LNCS, vol. 4513, pp. 1–15. Springer, Heidelberg (2007)
4. Balas, E.: Intersection Cuts - a new type of cutting planes for integer programming.
Operations Research 19, 19–39 (1971)
5. Balas, E., Saxena, A.: Optimizing over the split closure. Mathematical Program-
ming, Ser. A 113, 219–240 (2008)
6. Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P.: An updated mixed
integer programming library: MIPLIB 3. 0. Optima 58, 12–15 (1998)
7. Caprara, A., Letchford, A.: On the separation of split cuts and related inequalities.
Mathematical Programming, Ser. A 94, 279–294 (2003)
8. Cook, W.J., Kannan, R., Schrijver, A.: Chvátal closures for mixed integer pro-
gramming problems. Mathematical Programming 47, 155–174 (1990)
9. Cornuéjols, G., Margot, F.: On the Facets of Mixed Integer Programs with Two
Integer Variables and Two Constraints. Mathematical Programming, Ser. A 120,
429–456 (2009)
10. Gomory, R.E.: An algorithm for the mixed integer problem. Technical Report RM-
2597, The Rand Corporation (1960a)
11. Nemhauser, G., Wolsey, L.A.: A recursive procedure to generate all cuts for 0-1
mixed integer programs. Mathematical Programming, Ser. A 46, 379–390 (1990)
Prize-Collecting Steiner Network Problems
1 Introduction
Prize-collecting Steiner problems are well-known network design problems with
several applications in expanding telecommunications networks (see for exam-
ple [JMP00, SCRS00]), cost sharing, and Lagrangian relaxation techniques (see
e.g. [JV01, CRW01]). A general form of these problems is the Prize-Collecting
Steiner Forest problem1 : given a network (graph) G = (V, E), a set of source-
sink pairs P = {{s1 , t1 }, {s2 , t2 }, . . . , {sk , tk }}, a non-negative cost function
c : E → + , and a non-negative penalty function π : P → + , our goal is
Part of this work was done while the authors were meeting at DIMACS. We would
like to thank DIMACS for hospitality.
Partially supported by NSF Award Grant number 0829959.
1
In the literature, this problem is also called “prize-collecting generalized Steiner
tree”.
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 71–84, 2010.
c Springer-Verlag Berlin Heidelberg 2010
72 M. Hajiaghayi et al.
a minimum-cost way of installing (buying) a set of links (edges) and paying the
penalty for those pairs which are not connected via installed links. When all
penalties are ∞, the problem is the classic APX-hard Steiner Forest problem, for
which the best known approximation ratio is 2 − n2 (n is the number of nodes of
the graph) due to Agrawal, Klein, and Ravi [AKR95] (see also [GW95] for a more
general result and a simpler analysis). The case of Prize-Collecting Steiner Forest
problem when all sinks are identical is the classic Prize-Collecting Steiner Tree
problem. Bienstock, Goemans, Simchi-Levi, and Williamson [BGSLW93] first
considered this problem (based on a problem earlier proposed by Balas [Bal89])
and gave for it a 3-approximation algorithm. The current best ratio for this
problem is 1.992 by Archer, Bateni, Hajiaghayi,
! and Karloff [ABHK09], im-
proving upon a primal-dual 2 − n−1 1
-approximation algorithm of Goemans
and Williamson [GW95]. When in addition all penalties are ∞, the problem is
the classic Steiner Tree problem, which is known to be APX-hard [BP89] and
for which the best approximation ratio is 1.55 [RZ05]. Very recently, Byrka et
al. [BGRS10] have announced an improved approximation algorithm for the
Steiner tree problem.
The general form of the Prize-Collecting Steiner Forest problem first has been
formulated by Hajiaghayi and Jain [HJ06]. They showed how by a primal-dual
algorithm to a novel integer programming formulation of the problem with
doubly-exponential variables, we can obtain a 3-approximation algorithm for
the problem. In addition, they show that the factor 3 in the analysis of their
algorithm is tight. However they show how a direct randomized LP-rounding al-
gorithm with approximation factor 2.54 can be obtained for this problem. Their
approach has been generalized by Sharma, Swamy, and Williamson [SSW07] for
network design problems where violated arbitrary 0-1 connectivity constraints
are allowed in exchange for a very general penalty function. The work of Ha-
jiaghayi and Jain has also motivated a game-theoretic version of the problem
considered by Gupta et al. [GKL+ 07].
In this paper, we consider a much more general high-connectivity version of
Prize-Collecting Steiner Forest, called Prize-Collecting Steiner Network, in which
we are also given connectivity requirements ruv for pairs of nodes u and v and
a penalty function in case we do not satisfy all ruv . Our goal is to find a mini-
mum way of constructing a network (graph) in which we connect u and v with
ruv ≤ ruv edge-disjoint paths and paying a penalty for all violated connectivity
between source-sink pairs. This problem can arise in real-world network design,
in which a typical client not only might want to connect to the network but
also might want to connect via a few disjoint paths (e.g., to have a higher band-
width or redundant connections in case of edge failures) and a penalty might
be charged if we cannot satisfy its connectivity requirement. When all penalties
are ∞, the problem is the classic Steiner Network problem. Improving on a long
line of earlier research that applied primal-dual methods, Jain [Jai01] obtained
a 2-approximation algorithm for Steiner Network using the iterative rounding
method. This algorithm was generalized to so called “element-connectivity” by
Fleischer, Jain, and Williamson [FJW01] and by Cheriyan, Vempala, and Vetta
Prize-Collecting Steiner Network Problems 73
[CVV06]. Recently, some results were obtained for the node-connectivity version;
the currently best known ratios for the node-connectivity case are O(R3 log n)
for general requirements [CK09] and O(R2 ) for rooted requirements [Nut09],
where R = maxu,v∈V ruv is the maximum requirement. See also the survey by
Kortsarz and Nutov [KN07] for various min-cost connectivity problems.
Hajiaghayi and Nasri [HN10] generalize the iterative rounding approach of
Jain to Prize-Collecting Steiner Network when there is a separate non-increasing
marginal penalty function for each pair u, v whose ruv -connectivity requirement
is not satisfied. They obtain an iterative rounding 3-approximation algorithm for
this case. For the special case when penalty functions are linear in the violation
of the connectivity requirements, Nagarajan, Sharma, and Williamson [NSW08]
using Jains iterative rounding algorithm as a black box give a 2.54-factor approx-
imation algorithm. They also generalize the 0-1 requirements of Prize-Collecting
Steiner Forest problem introduced by Sharma, Swamy, and Williamson [SSW07]
to include general connectivity requirements. Assuming the monotone submod-
ular penalty function of Sharma et al. is generalized to a multiset function that
can be decomposed into functions in the same type as that of Sharma et al.,
they give an O(log R)-approximation algorithm (recall that R is the maximum
connectivity requirement). In this algorithm, they assume that we can use each
edge possibly many times (without bound). They raise the question whether we
can obtain a constant ratio without all these assumptions, when penalty is a sub-
modular multi-set function of the set of disconnected pairs? More importantly
they pose as an open problem to design a good approximation algorithm for the
all-or-nothing version of penalty functions: penalty functions which charge the
penalty even if the connectivity requirement is slightly violated. In this paper,
we answer affirmatively all these open problems by proving the first constant
factor 2.54-approximation algorithm which is based on a novel LP formulation
of the problem. We further generalize our results for element-connectivity and
node-connectivity. In fact, for all types of connectivities, we prove a very gen-
eral result (see Theorem 1) stating that if Steiner Network (the version without
penalties) admits an LP-based ρ-approximation algorithm, then the correspond-
ing prize-collecting version admits a (ρ + 1)-approximation algorithm.
is when there is a “root” s that belongs to all pairs {ui , vi }. We consider the
following “prize-collecting” version of GSN.
k
val (H) = c(H) + pi (λSH (ui , vi )).
i=1
between u and v is “mixed”, meaning it may contain both edges in the graph
and nodes from S. Note that if T (i, S) then δ(T ) ∪ (V \ (T ∪ T )) is such
a mixed cut that separates between ui and vi . Intuitively, Menger’s Theorem
for S-connectivity (c.f. [KN07]) states that the S-connectivity between ui and
vi equals the minimum size of such a mixed cut. Formally, for a node pair ui , vi
of a graph H = (V, E) and S ⊆ V we have:
λSH (ui , vi ) = min (|δ(T )|+ |V \ (T ∪T )|) = min (|δ(T )|+ |V |− (|T |+ |T |))
T (i,S) T (i,S)
Hence if λSH (ui , vi ) ≥ ri for a graph H = (V, E), then for any setpair T with
T (i, S) we must have |δ(T )| ≥ ri (T ), where ri (T ) = max{ri + |T | + |T | −
|V |, 0}. Consequently, a standard “cut-type” LP-relaxation of the GSN problem
is as follows (c.f. [KN07]):
⎧ ⎫
⎨ ⎬
min ce xe | xe ≥ ri (T ) ∀T (i, S), ∀i ∈ K, xe ∈ [0, 1] ∀e . (1)
⎩ ⎭
e∈E e∈δ(T )
2 A New LP Relaxation
We use the following LP-relaxation for the PC-GSN problem. We introduce vari-
ables xe for e ∈ E (xe = 1 if e ∈ H), fi,e for i ∈ K and e ∈ E (fi,e = 1 if
i ∈ unsat(H) and e appears on a chosen set of ri S-disjoint {ui , vi }-paths in
H), and zI for I ⊆ K (zI = 1 if I = unsat(H)).
Minimize e∈E ce xe + I⊆K π(I)zI
Subject to fi,e ≥ (1 − I:i∈I zI )ri (T ) ∀i ∀T (i, S)
e∈δ(T )
fi,e ≤ 1 − I:i∈I zI ∀i ∀e
xe ≥ fi,e ∀i ∀e (2)
I⊆K zI =1
xe , fi,e , zI ∈ [0, 1] ∀i ∀e ∀I
for all i and T (i, S). Here is an example demonstrating that the integrality
gap of this LP can be as large as R = maxi ri even for edge-connectivity. Let G
consist of R − 1 edge-disjoint paths between two nodes s and t. All the edges
have cost 0. There is only one pair {u1 , v1 } = {s, t} that has requirement r1 = R
and penalty π({1}) = 1. Let π(∅) = 0. Clearly, π is submodular and monotone
non-decreasing. We have S = ∅. No integral solution can satisfy the requirement
r1 , hence an optimal integral solution pays the penalty π({1}) and has value 1.
A feasible fractional solution (without the flow variables) sets xe = 1 for all e,
sets z{1} = 1/R, z∅ = 1 − 1/R. The new set of constraints is satisfied since
and
e∈δ(T ) xe ≥ (1 − 1/R) · R = (1 − z{1} )r1 (T ) for any {s, t}-cut T . Thus the
optimal LP-value is at most 1/R, giving a gap of at least R.
With flow variables, however, we have an upper bound f1,e ≤ 1 − z{1} . Since
there
is an {s, t}-cut T with |δ(T )| = R − 1, we cannot satisfy the constraints
e∈δ(T ) f1,e ≥ (1 − z{1} )r1 (T ) and f1,e ≤ 1 − z{1} simultaneously unless we set
z{1} = 1. Thus in this case, our LP (2) with flow variables has the same optimal
value of as the integral optimum.
78 M. Hajiaghayi et al.
We will prove the following two statements that together imply Theorem 1.
Lemma 2. Any basic feasible solution to (2) has a polynomial number of non-
zero variables. Furthermore, an optimal basic solution to (2) (the non-zero en-
tries) can be computed in polynomial time.
Lemma 3. Suppose that there exists a polynomial time algorithm that computes
an integral solution to LP (1) of cost at most ρ times the optimal value of LP (1)
for any subset of node pairs. Then there exists a polynomial time algorithm that
given a feasible solution to (2) computes as a solution to PC-GSN a subgraph H
of G so that val(H) = c(H) + π(unsat(H)) is at most (1 − e−1/ρ )−1 times the
value of this solution, assuming π is submodular and monotone non-decreasing.
Before proving these lemmas, we prove some useful results. The following state-
ment can be deduced from a theorem of Edmonds for polymatroids (c.f. [KV02,
Chapter 14.2]), as the dual LP d(γ) in the lemma seeks to optimize a linear
function over a polymatroid. We provide a direct proof for completeness of ex-
position.
Lemma 4. Let γ ∈ [0, 1]k be a vector. Consider a primal LP
⎧ ⎫
⎨ ⎬
p(γ) := min π(I)zI | zI ≥ γi ∀i ∈ K, zI ≥ 0 ∀I ⊆ K
⎩ ⎭
I⊆K I:i∈I
Let σ be a permutation of K such that γσ(1) ≤ γσ(2) ≤ . . . ≤ γσ(k) . Let us also use
the notation that γσ(0) = 0. The optimum solutions to p(γ) and d(γ) respectively
are given by
γσ(i) − γσ(i−1) , for I = {σ(i), . . . , σ(k)}, i ∈ K
zI =
0, otherwise;
and
k
k
= γi · (π({i, . . . , k}) − π({i + 1, . . . , k})) = γi · yi .
i=1 i=1
Thus from weak LP duality, they in fact form optimum solutions to primal and
dual LPs respectively.
Recall that a sub-gradient of a convex function g : k → at a point γ ∈ k
is a vector d ∈ k such that for any γ ∈ k , we have g(γ ) − g(γ) ≥ d ·
(γ − γ). For a differentiable convex function g, the sub-gradient corresponds
to gradient ∇g. The function p(γ) defined in Lemma 4 is essentially Lovasz’s
continuous extension of the submodular function π. The fact that p is convex
and its subgradient can be computed efficiently is given in [Fuj05]. We provide
a full proof for completeness of exposition.
Lemma 5. The function p(γ) in Lemma 4 is convex and given γ ∈ [0, 1]k , both
p(γ) and its sub-gradient ∇p(γ) can be computed in polynomial time.
Proof. We first prove that p is convex. Fix γ1 , γ2 ∈ [0, 1]k and α ∈ [0, 1]. To show
that p is convex, we will show p(αγ1 + (1 − α)γ2 ) ≤ αp(γ1 ) + (1 − α)p(γ2 ). Let
{zI1 } and {zI2 } be the optimum solutions of the primal LP defining p for γ1 and
γ2 respectively. Note that the solution {αzI1 + (1 − α)zI2 } is feasible for this LP
for γ = αγ1 + (1 − α)γ2 . Thus the optimum solution has value not greater than
the value of this solution which is αp(γ1 ) + (1 − α)p(γ2 ).
From Lemma 4, it is clear that given γ ∈ [0, 1]k , the value p(γ) can be com-
puted in polynomial time. Lemma 4 also implies that the optimum dual solution
y ∗ = (y1∗ , . . . , yk∗ ) ∈ k+ can be computed in polynomial time. We now argue that
y ∗ is a sub-gradient of p at γ. Fix any γ ∈ k . First note that, from LP duality,
p(γ) = y ∗ · γ. Thus we have
p(γ) + y ∗ · (γ − γ) = y ∗ · γ + y ∗ · (γ − γ) = y ∗ · γ ≤ p(γ ).
The last inequality holds from weak LP duality since y ∗ is a feasible solution for
the dual LP d(γ ) as well. The lemma follows.
80 M. Hajiaghayi et al.
3 Proof of Lemma 3
Proof. Consider the LP-relaxation (1) of the GSN problem with good require-
ments only, with K replaced by Kg ; namely, we seek a minimum cost sub-
graph H of G that satisfies the set Kg of good requirements. We claim that
x∗∗ ∗
e = min {1, xe /(1 − α)} for each e ∈ E is a feasible solution to LP (1). Thus
the optimum value of LP (1) is at most e∈E ce x∗∗ e . Consequently, using the
algorithm that computes an integral solution to LP (1) of cost at most ρ times
the optimal value of LP (1), we can construct a subgraph H that satisfies all
ρ
good requirements and has cost at most c(H) ≤ ρ e∈E ce x∗∗ e ≤ 1−α e c e x∗
e,
as desired.
∗∗
We now∗∗ show that {xe } is a feasible solution to LP (1), namely, that
x ≥ ri (T ) for any i ∈ Kg and any T (i, S). Let i ∈ Kg and let ζi =
) e
e∈δ(T
1 − I:i∈I zI∗ . Note that ζi ≥ 1 − α, by the definition of Kg . By the second and
the third sets of constraints in LP (2), for every e ∈ E we have min{ζi , x∗e } ≥ fi,e∗
.
∗
∗
fi,e f∗
= i,e
ζi 1− zI∗ .
Consequently, combining with the first set of constraints in
I:i∈I
∗
e∈δ(T ) fi,e
LP (2), for any T (i, S) we obtain that e∈δ(T ) x∗∗
e ≥ 1−
z ∗ ≥ ri (T ).
I:i∈I I
Let H be as in Lemma 6, and recall that unsat(H) denotes the set of require-
ments not satisfied by H. Clearly each requirement i ∈ unsat(H) is bad. The
following lemma bounds the total penalty we pay for unsat(H).
Lemma 7. π(unsat(H)) ≤ α1 · I π(I)zI∗ .
To complete the proof of β1 -approximation, we now argue that the above expec-
tation is at most β1 · e∈E (ce x∗e + I π(I)zI∗ ).
$ %
Since Eα 1−αρ
= β1 , the first term in (3) is at most β1 · e∈E ce x∗e . Since
unsat(H) ⊆ {i | I:i∈I zI∗ ≥ α} and & sinceπ is monotone'non-decreasing, the
second term in (3) is at most Eα π {i | I:i∈I zI∗ ≥ α} . Lemma 8 bounds
this quantity as follows. The ideas used here are also presented in Sharma et
al. [SSW07].
Lemma 8. We have
( ) *+
1
Eα π {i | zI∗ ≥ α} ≤ · π(I)zI∗ . (4)
β
I:i∈I I
Proof. Let γi = I:i∈I zI∗ for all i ∈ K. Let us, without loss of generality, order
the elements i ∈ K such that γ1 ≤ γ2 ≤ · · · ≤ γk . We also use the notation
γ0 = 0. Note that {zI∗ } forms a feasible solution to the primal LP p(γ) given in
Lemma 4. Therefore, from Lemma 4, its objective value is at least that of the
optimum solution:
k
π(I)zI∗ ≥ [(γi − γi−1 ) · π({i, . . . , k})] . (5)
I i=1
We now observe that the LHS of (4) can be expressed as follows. Since α is picked
uniformly at random from (0, β], we have that for all 1 ≤ i ≤ k, with probability
at most γi −γ i−1
, the random variable α lies in the interval (γi−1 , γi ]. When this
β
event happens, we get that {i | I:i ∈I zI∗ ≥ α} = {i | γi ≥ α} = {i, . . . , k}.
Thus the expectation in LHS of (4) is at most
k "
#
γi − γi−1
· π({i, . . . , k}) . (6)
i=1
β
4 Proof of Lemma 2
We next show that even if LP (2) has exponential number of variables and
constraints, the following lemma holds.
Lemma 9. Any basic feasible solution to LP (2) has a polynomial number of
non-zero variables.
Proof. Fix a basic feasible solution {x∗e , fi,e
∗
, zi∗ } to (2). For i ∈ K, let
∗
min e∈δ(T ) fi,e
T :T i
γi = 1 − and γi = 1 − max fi,e
∗
.
ri e
Now fix the values of variables {xe , fi,e } to {x∗e , fi,e
∗
} and project the LP (2) onto
variables {zI } as follows.
⎧
⎨
ce x∗e + min π(I)zI |
⎩
e∈E I⊆K
⎫
⎬
zI = 1, γi ≤ zI ≤ γi ∀i ∈ K, zI ≥ 0 ∀I ⊆ K . (7)
⎭
I⊆K I:i∈I
sub-gradient of the function e∈E ce xe + p(γ) w.r.t. variables {xe , γi }. The sub-
gradient of e∈E ce xe w.r.t. x is simply the cost vector c. The sub-gradient
of p(γ) w.r.t. γ is computed using Lemma 5, denote it by y ∈ k+ . From the
definition of sub-gradient, we have that the sub-gradient (c, y) to the objective
function at point (x, γ) satisfies
) * ) *
ce xe + p(γ ) − ce xe + p(γ) ≥ (c, y) · ((x , γ ) − (x, γ)) .
e∈E e∈E
Now fix any feasible solution (x∗ , γ ∗ ), i.e., the one that satisfies e∈E ce x∗e +
p(γ ∗ ) ≤ opt. Substituting (x , γ ) = (x∗ , γ ∗ ) in the above equation we get,
) * ) *
0 = opt − opt > ce x∗e + p(γ ∗ ) − ce xe + p(γ)
e∈E e∈E
≥ (c, y) · (x∗ , γ ∗ ) − (c, y) · (x, γ).
Thus (c, y) defines a separating hyperplane between the point (x, γ) and any
point (x∗ , γ ∗ ) that satisfies e∈E ce x∗e + p(γ ∗ ) ≤ opt. Hence we have a polyno-
mial time separation oracle for the objective function as well.
Thus we can solve (8) using the ellipsoid algorithm. The proof of Lemma 2 is
hence complete.
References
[ABHK09] Archer, A., Bateni, M., Hajiaghayi, M., Karloff, H.: A technique for im-
proving approximation algorithms for prize-collecting problems. In: Proc.
50th IEEE Symp. on Foundations of Computer Science, FOCS (2009)
[AKR95] Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation
algorithm for the generalized Steiner problem on networks. SIAM J. Com-
put. 24(3), 440–456 (1995)
[Bal89] Balas, E.: The prize collecting traveling salesman problem. Networks 19(6),
621–636 (1989)
[BGRS10] Byrka, J., Grandoni, F., Rothvoss, T., Sanita, L.: An improved lp-based
approximation for steiner tree. In: Proceedings of the 42nd annual ACM
Symposium on Theory of computing, STOC (2010)
[BGSLW93] Bienstock, D., Goemans, M., Simchi-Levi, D., Williamson, D.: A note on
the prize collecting traveling salesman problem. Math. Programming 59(3,
Ser. A), 413–420 (1993)
[BP89] Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2.
Information Processing Letters 32, 171–176 (1989)
[CK09] Chuzhoy, J., Khanna, S.: An O(k3 log n)-approximation algorithms for
vertex-connectivity network design. In: Proceedings of the 50th Annual
IEEE Symposium on Foundations of Computer Science, FOCS (2009)
[CRW01] Chudak, F., Roughgarden, T., Williamson, D.: Approximate k-MSTs and
k-Steiner trees via the primal-dual method and Lagrangean relaxation. In:
Aardal, K., Gerards, B. (eds.) IPCO 2001. LNCS, vol. 2081, pp. 60–70.
Springer, Heidelberg (2001)
84 M. Hajiaghayi et al.
[CVV06] Cheriyan, J., Vempala, S., Vetta, A.: Network design via iterative rounding
of setpair relaxations. Combinatorica 26(3), 255–275 (2006)
[FJW01] Fleischer, L., Jain, K., Williamson, D.: An iterative rounding 2-
approximation algorithm for the element connectivity problem. In: Proc.
of the 42nd IEEE Symp. on Foundations of Computer Science (FOCS), pp.
339–347 (2001)
[Fuj05] Fujishige, S.: Submodular functions and optimization. Elsevier, Amster-
dam (2005)
[GKL+ 07] Gupta, A., Könemann, J., Leonardi, S., Ravi, R., Schäfer, G.: An efficient
cost-sharing mechanism for the prize-collecting steiner forest problem. In:
Proc. of the 18th ACM-SIAM Symposium on Discrete algorithms (SODA),
pp. 1153–1162 (2007)
[GW95] Goemans, M., Williamson, D.: A general approximation technique for con-
strained forest problems. SIAM J. Comput. 24(2), 296–317 (1995)
[HJ06] Hajiaghayi, M., Jain, K.: The prize-collecting generalized Steiner tree prob-
lem via a new approach of primal-dual schema. In: Proc. of the 17th ACM-
SIAM Symp. on Discrete Algorithms (SODA), pp. 631–640 (2006)
[HN10] Hajiahayi, M., Nasri, A.: Prize-collecting Steiner networks via iterative
rounding. In: LATIN (to appear, 2010)
[Jai01] Jain, K.: A factor 2 approximation algorithm for the generalized Steiner
network problem. Combinatorica 21(1), 39–60 (2001)
[JMP00] Johnson, D., Minkoff, M., Phillips, S.: The prize collecting Steiner tree
problem: theory and practice. In: Proceedings of the Eleventh Annual
ACM-SIAM Symposium on Discrete Algorithms, pp. 760–769 (2000)
[JV01] Jain, K., Vazirani, V.: Approximation algorithms for metric facility loca-
tion and k-median problems using the primal-dual schema and Lagrangian
relaxation. J. ACM 48(2), 274–296 (2001)
[KN07] Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity prob-
lems. In: Gonzales, T.F. (ed.) Approximation Algorithms and Metahueris-
tics, ch. 58. CRC Press, Boca Raton (2007)
[KV02] Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms.
Springer, Berlin (2002)
[NSW08] Nagarajan, C., Sharma, Y., Williamson, D.: Approximation algorithms for
prize-collecting network design problems with general connectivity require-
ments. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426,
pp. 174–187. Springer, Heidelberg (2009)
[Nut09] Nutov, Z.: Approximating minimum cost connectivity problems via un-
crossable bifamilies and spider-cover decompositions. In: Proc. of the 50th
IEEE Symposium on Foundations of Computer Science, FOCS (2009)
[RZ05] Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approx-
imation. SIAM J. on Discrete Mathematics 19(1), 122–134 (2005)
[SCRS00] Salman, F., Cheriyan, J., Ravi, R., Subramanian, S.: Approximating the
single-sink link-installation problem in network design. SIAM J. on Opti-
mization 11(3), 595–610 (2000)
[SSW07] Sharma, Y., Swamy, C., Williamson, D.: Approximation algorithms for
prize collecting forest problems with submodular penalty functions. In:
Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms
(SODA), pp. 1275–1284 (2007)
On Lifting Integer Variables in Minimal
Inequalities
1 Introduction
There has been a renewed interest recently in the study of cutting planes for
general mixed integer linear programs (MILPs) that cut off a basic solution
of the linear programming relaxation. More precisely, consider a mixed integer
linear set in which the variables are partitioned into a basic set B and a nonbasic
set N , and K ⊆ B ∪ N indexes the integer variables:
xi = fi − j∈N aij xj for i ∈ B
x≥0 (1)
xk ∈ Z for k ∈ K.
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 85–95, 2010.
c Springer-Verlag Berlin Heidelberg 2010
86 A. Basu et al.
B ⊆ K, i.e. all basic variables are integer. Andersen, Louveaux, Weismantel and
Wolsey [1] studied the corner polyhedron when |B| = 2 and B = K, i.e. all
nonbasic variables are continuous. They give a complete characterization of the
corner polyhedron using intersection cuts (Balas [2]) arising from splits, triangles
and quadrilaterals. This very elegant result has been extended to |B| > 2 and
B = K by showing a correspondence between minimal valid inequalities and
maximal lattice-free convex sets [5], [7]. These results and their extensions [6],
[10] are best described in an infinite model, which we motivate next.
A classical family of cutting planes for (1) is that of Gomory mixed integer
cuts.
For a given row of the tableau, the Gomory mixed integer cut is of the form
j∈N \K ψ(aij )xj + j∈N ∩K π(aij )xj ≥ 1 where ψ and π are functions given by
simple formulas. A nice feature of the Gomory mixed integer cut is that, for fixed
fi , the same functions ψ, π are used for any possible choice of the aij s in (1). It is
well known that the Gomory mixed integer cuts are also valid for X. More gener-
ij , i ∈ B; we are interested
ally, let aj be the vector with entries a in pairs (ψ, π)
of functions such that the inequality j∈N \K ψ(aj )xj + j∈N ∩K π(aj )xj ≥ 1
is valid for X for any possible choice of the nonbasic coefficients aij . Since we
are interested in nonredundant inequalities, we can assume that the function
(ψ, π) is pointwise minimal. While a general characterization of minimal valid
functions seems hopeless (see for example [4]), when N ∩ K = ∅ the minimal
valid functions ψ are well understood in terms of maximal lattice-free convex
sets, as already mentioned. Starting from such a minimal valid function ψ, an
interesting question is how to generate a function π such that (ψ, π) is valid and
minimal. Recent papers [8], [9] study when such a function π is unique. Here we
prove a theorem that generalizes and unifies results from these two papers.
In order to formalize the concept of valid function (ψ, π), we introduce the
following infinite model. In the setting below, we also allow further linear con-
straints on the basic variables. Let S be the set of integral points in some rational
polyhedron in Rn such that dim(S) = n (for example, S could be the set of non-
negative integer points). Let f ∈ Rn \ S. Consider the following semi-infinite
relaxation of (1), introduced in [10].
x= f+ rsr + ryr , (2)
r∈Rn r∈Rn
x ∈ S,
sr ∈ R+ , ∀r ∈ Rn ,
yr ∈ Z+ , ∀r ∈ Rn ,
s, y have finite support
where the nonbasic continuous variables have been renamed s and the nonbasic
integer variables have been renamed y. Given π : Rn → R, (ψ, π)
two functions ψ,
is said to be valid for (2) if the inequality r∈Rn ψ(r)sr + r∈Rn π(r)yr ≥ 1
holds for every (x, s, y) satisfying (2). We also consider the semi-infinite model
where we only have continuous nonbasic variables.
On Lifting Integer Variables in Minimal Inequalities 87
x= f+ rsr (3)
r∈Rn
x ∈ S,
sr ∈ R+ , ∀r ∈ Rn ,
s has finite support.
A function ψ : Rn → R is said to be valid for (3) if the inequality r∈Rn ψ(r)sr ≥
1 holds for every (x, s) satisfying (3). Given a valid function ψ for (3), a function
π is a lifting of ψ if (ψ, π) is valid for (2). One is interested only in (pointwise)
minimal valid functions, since non-minimal ones are implied by some minimal
valid function. If ψ is a minimal valid function for (3) and π is a lifting of ψ such
that (ψ, π) is a minimal valid function for (2) then we say that π is a minimal
lifting of ψ.
While minimal valid functions for (3) have a simple characterization [6], min-
imal valid functions for (2) are not well understood. A general idea to derive
minimal valid functions for (2) is to start from some minimal valid function ψ
for (3), and construct a minimal lifting π of ψ. While there is no general tech-
nique to compute such minimal lifting π, it is known that there exists a region
Rψ , containing the origin in its interior, where ψ coincides with π for any mini-
mal lifting π. This latter fact was observed by Dey and Wolsey [9] for the case
of S = Z2 and by Conforti, Cornuéjols and Zambelli [8] for the general case.
Furthermore, it is remarked in [8] and [10] that, if π is a minimal lifting of ψ,
then π(r) = π(r ) for every r, r ∈ Rn such that r − r ∈ Zn ∩ lin(conv(S)).
Therefore the coefficients of any minimal lifting π are uniquely determined in
the region Rψ + (Zn ∩ lin(conv(S))). In particular, whenever translating Rψ by
integer vectors in lin(conv(S)) covers Rn , ψ has a unique minimal lifting. The
purpose of this paper is to give a precise description of the region Rψ .
To state our main result, we need to explain the characterization of minimal
valid functions for (3). We say that a convex set B ⊆ Rn is S-free if B does not
contain any point of S in its interior. A set B is a maximal S-free convex set if it
is an S-free convex set that is not properly contained in any S-free convex set.
It was proved in [6] that maximal S-free convex sets are polyhedra containing a
point of S in the relative interior of each facet.
Given an S-free polyhedron B ⊆ Rn containing f in its interior, B can be
uniquely written in the form
B = {x ∈ Rn : ai (x − f ) ≤ 1, i ∈ I},
ψB (r) = max ai r, ∀r ∈ Rn .
i∈I
Note in particular that, since maximal S-free convex sets are polyhedra, the
above function is defined for all maximal S-free convex sets B.
88 A. Basu et al.
Theorem 1. [6] Let ψ be a minimal valid function for (3). Then the set
Bψ := {x ∈ Rn | ψ(x − f ) ≤ 1}
We define ,
Rψ := R(x).
x∈S∩Bψ
In the above expression, equality holds if and only if h ∈ I(r) and h ∈ I(x−f −r).
x3 R(x3) R(x ) x f
f 2 2
x1 x2
Bψ
R(x2)
R(x1)
R(x1)
x1
Bψ
l1 l
(a) A maximal Z2 -free triangle with (b) A wedge
three integer points
x3 R(x3)
x1
R(x1)
Bψ x1 x2
f
x6 R(x1)
x2
R(x2) R(x6) R(x2)
f
R(x5)
R(x4)
Bψ
x3 x4 x5
R(x3)
(c) A maximal Z2 -free triangle with integer (d) A truncated wedge
vertices
Fig. 1. Regions R(x) for some maximal S-free convex sets in the plane. The thick dark
line indicates the boundary of Bψ . For a particular x, the dark gray regions denote
R(x). The jagged lines in a region indicate that it extends to infinity. For example, in
Figure 1(b), R(x1 ) is the strip between lines l1 and l. Figure 1(c) shows an example
where R(x) is full-dimensional for x2 , x4 , x6 , but is not full-dimensional for x1 , x3 , x5 .
90 A. Basu et al.
Given
a minimal valid function ψ for (3) and scalar λ, we say that the inequality
r∈Rn ψ(r)sr + λyr ∗ ≥ 1 is valid for (4) if it holds for every (x,
s, yr∗ ) satisfy-
ing (4). We denote by ψ ∗ (r∗ ) the minimum value of λ for which r∈Rn ψ(r)sr +
λyr∗ ≥ 1 is valid for (4).
We observe that, for any lifting π of ψ, we have
ψ ∗ (r∗ ) ≤ π(r∗ ).
Indeed, r∈Rn ψ(r)sr + π(r∗ )yr∗ ≥ 1 is valid for (4), since, for any (s̄, ȳr∗ )
satisfying (4), the vector (s̄, ȳ), defined by ȳr = 0 for all r ∈ Rn \{r∗ }, satisfies (2).
Moreover, the following fact was shown in [8].
Lemma 1. If ψ is a minimal valid function for (3) and π is a minimal lifting
of ψ, then π ≤ ψ.
So we have the following relation for every minimal lifting π of ψ :
In general ψ ∗ is not a lifting of ψ, but if it is, then the above relation implies
that it is the unique minimal lifting of ψ.
Remark 1. For any r ∈ Rn such that ψ ∗ (r) = ψ(r), we have π(r) = ψ(r) for
every minimal lifting π of ψ. Conversely, if ψ ∗ (r∗ ) < ψ(r∗ ) for some r∗ ∈ Rn ,
then there exists some lifting π of ψ such that π(r∗ ) < ψ(r∗ ).
Proof. The first part follows from ψ ∗ ≤ π ≤ ψ. For the second part, given
r∗ ∈ Rn such that ψ ∗ (r∗ ) < ψ(r∗ ), we can define π by π(r∗ ) = ψ ∗ (r∗ ) and
π(r) = ψ(r) for all r ∈ Rn , r = r∗ . Since ψ is valid for (3), it follows by the
definition of ψ ∗ (r∗ ) that π is a lifting of ψ.
Remark 2. The proof of Theorem 3 in [6] implies the following. Given a maximal
S-free convex set B, there exists δ > 0 such that there is no point of S \ B at
distance less than δ from B.
ai r̄ ≤ 0, i ∈ I,
92 A. Basu et al.
This implies that there exists some ε̄ > 0 such that for all ε ≤ ε̄,
μi ai + γC = 0
i∈I
∗
(λ − ε)( μi ) − ( μi ai )r∗ > 0,
i∈I i∈I
since λ∗ − ai r∗ ≥ 0, i ∈ I.
Corollary 1. Let ψ be a minimal valid function for (3). Then ψ ∗ (r∗ ) = ψ(r∗ )
if and only if there exists x̄ ∈ S such that
We show the converse. Since ψ is a valid function for (3), ψ(x̄−f −r∗ )+ψ(r∗ ) ≥ 1.
Since ψ is a minimal valid function for (3), by Theorem 1 there exists a maximal
S-free convex set B such that ψ = ψB . Let Bψ = {x ∈ Rn | ai (x − f ) ≤ 1, i ∈ I}.
∗ ∗ ∗
x̄Assume ψ∗ (r ) = ψ(r ). By Theorem 5, there exists a point x̄ ∈ S such that
1 ∈ B(ψ(r )). Therefore
ai (x̄ − f ) + ψ(r∗ ) − ai r∗ ≤ 1, i ∈ I.
Thus
4 Conclusion
In this paper we give an exact characterization of the region where a minimal
valid inequality ψ and any minimal lifting π of ψ coincide. This was exhibited in
Theorem 2, which generalizes results from [8] and [9] about liftings of minimal
valid inequalities.
As already mentioned in the introduction, the following theorem was proved
in [8].
Theorem 6. Let ψ be a minimal valid function for (3). If Rψ + (Zn ∩ lin
(conv(S))) covers all of Rn , then there exists a unique minimal lifting π of ψ.
We conjecture that the converse also holds.
Conjecture 7 Let ψ be a minimal valid function for (3). There exists a unique
minimal lifting π of ψ if and only if Rψ + (Zn ∩ lin(conv(S))) covers all of Rn .
Acknowledgements
The authors would like to thank Marco Molinaro for helpful discussions about
the results presented in this paper.
References
1. Andersen, K., Louveaux, Q., Weismantel, R., Wolsey, L.A.: Cutting Planes from
Two Rows of a Simplex Tableau. In: Fischetti, M., Williamson, D.P. (eds.) IPCO
2007. LNCS, vol. 4513, pp. 1–15. Springer, Heidelberg (2007)
2. Balas, E.: Intersection Cuts - A New Type of Cutting Planes for Integer Program-
ming. Operations Research 19, 19–39 (1971)
3. Barvinok, A.: A Course in Convexity. In: Graduate Studies in Mathematics, vol. 54.
American Mathematical Society, Providence (2002)
4. Basu, A., Conforti, M., Cornuejols, G., Zambelli, G.: A Counterexample to a Con-
jecture of Gomory and Johnson. Mathematical Programming Ser. A (to appear
2010)
5. Basu, A., Conforti, M., Cornuejols, G., Zambelli, G.: Maximal Lattice-free Convex
Sets in Linear Subspaces (2009) (manuscript)
6. Basu, A., Conforti, M., Cornuejols, G., Zambelli, G.: Minimal Inequalities for an
Infinite Relaxation of Integer Programs. SIAM Journal of Discrete Mathematics
(to appear 2010)
7. Borozan, V., Cornuéjols, G.: Minimal Valid Inequalities for Integer Constraints.
Mathematics of Operations Research 34, 538–546 (2009)
8. Conforti, M., Cornuejols, G., Zambelli, G.: A Geometric Perspective on Lifting
(May 2009) (manuscript)
9. Dey, S.S., Wolsey, L.A.: Lifting Integer Variables in Minimal Inequalities corre-
sponding to Lattice-Free Triangles. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.)
IPCO 2008. LNCS, vol. 5035, pp. 463–475. Springer, Heidelberg (2008)
10. Dey, S.S., Wolsey, L.A.: Constrained Infinite Group Relaxations of MIPs (March
2009) (manuscript)
On Lifting Integer Variables in Minimal Inequalities 95
11. Gomory, R.E.: Some Polyhedra related to Combinatorial Problems. Linear Algebra
and its Applications 2, 451–558 (1969)
12. Gomory, R.E., Johnson, E.L.: Some Continuous Functions Related to Corner Poly-
hedra, Part I. Mathematical Programming 3, 23–85 (1972)
13. Johnson, E.L.: On the Group Problem for Mixed Integer Programming. In: Math-
ematical Programming Study, pp. 137–179 (1974)
14. Schrijver, A.: Theory of Linear and Integer Programming. John Wiley & Sons,
New York (1986)
15. Meyer, R.R.: On the Existence of Optimal Solutions to Integer and Mixed-Integer
Programming Problems. Mathematical Programming 7, 223–235 (1974)
Efficient Edge Splitting-Off Algorithms
Maintaining All-Pairs Edge-Connectivities
1 Introduction
The edge splitting-off operation plays an important role in many basic graph
problems, both in proving theorems and obtaining efficient algorithms. Splitting-
off a pair of edges (xu, xv) means deleting these two edges and adding a new
edge uv if u = v. This operation is introduced by Lovász [18] who showed that
splitting-off can be performed to maintain the global edge-connectivity of a graph.
Mader extended Lovász’s result significantly to prove that splitting-off can be
performed to maintain the local edge-connectivity for all pairs:
Theorem 1 (Mader [19]). Let G = (V, E) be an undirected graph that has at
least r(s, t) edge-disjoint paths between s and t for all s, t ∈ V − x. If there is
no cut edge incident to x and d(x) = 3, then some edge pair (xu, xv) can be
split-off so that in the resulting graph there are still at least r(s, t) edge-disjoint
paths between s and t for all s, t ∈ V − x.
These splitting-off theorems have applications in various graph problems. Lovász
[18] and Mader [19] used their splitting-off theorems to derive Nash-Williams’ graph
orientation theorems [23]. Subsequently these theorems and their extensions have
found applications in a number of problems, including edge-connectivity augmen-
tation problems [4, 8, 9], network design problems [7, 13, 16], tree packing problems
[1, 6, 17], and graph orientation problems [11].
Efficient splitting-off algorithms have been developed to give fast algorithms
for the above problems [4, 6, 12, 20, 22]. However, most of the efficient algorithms
are developed only in the global edge-connectivity setting, although there are
important applications in the more general local edge-connectivity setting.
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 96–109, 2010.
c Springer-Verlag Berlin Heidelberg 2010
Efficient Edge Splitting-Off Algorithms 97
Mader’s theorem can be applied repeatedly until d(x) = 0 when d(x) is even and
there is no cut edge incident to x. This is called a complete edge splitting-off at
x, which is a key subroutine in algorithms for connectivity augmentation, graph
orientation, and tree packing.
A straightforward algorithm to compute a complete splitting-off sequence is
to split-off (xu, xv) for every pair u, v ∈ N (x) where N (x) is the neighbor set
of x, and then check whether the connectivity requirements are violated by
computing all-pairs edge-connectivities in the resulting graph, and repeat this
procedure until d(x) = 0.
Several efficient algorithms are proposed for the complete splitting-off prob-
lem, but only Gabow’s algorithm [12] can be used in the local edge-connectivity
setting, with running time O(rmax 2 · n3 ). Our algorithms improve the running
time of Gabow’s algorithm by a factor of Ω̃(n). In applications where rmax is
small, the improvement of the randomized algorithm could be a factor of Ω̃(n2 ).
Theorem 2. In the local edge-connectivity setting, there is a deterministic
Õ(rmax 2 · n2 )-time algorithm and a randomized Õ(m + rmax 3 · n)-time algorithm
for the complete edge splitting-off problem in unweighted graphs.
These edge splitting-off algorithms can be used directly to improve the run-
ning time of various graph algorithms [7, 9, 12, 13, 17, 23]. For instance, us-
ing Theorem 2 in Gabow’s local edge-connectivity augmentation algorithm [12]
in unweighted graphs, the running time can be improved from Õ(rmax 2 n3 ) to
Õ(rmax 2 n2 ) time. Similarly, using Theorem 2 in Gabow’s orientation algorithm
[12], one can find a well-balanced orientation in unweighted graphs in Õ(rmax 3 n2 )
expected time, improving the O(rmax 2 n3 ) result by Gabow [12]. We will not dis-
cuss the details of these applications in this paper.
Our edge splitting-off algorithms are conceptually very simple, which can be
seen as refinements of the straightforward algorithm. The improvements come
from some new structural results, and a recent fast Gomory-Hu tree construc-
tion algorithm by Bhalgat, Hariharan, Kavitha, and Panigrahi [5]. First, in
Section 3.2, we show how to find a complete edge splitting-off sequence by using
at most O(|N (x)|) splitting-off attempts, instead of O(|N (x)|2 ) attempts by the
straightforward algorithm. This is based on an alternative proof of Mader’s the-
orem in Section 3.1. Then, in Section 3.4, we show how to reduce the problem of
checking local edge-connectivities for all pairs, to the problem of checking local
98 L.C. Lau and C.K. Yung
2 Preliminaries
Let G = (V, E) be a graph. For X, Y ⊆ V , denote by δ(X, Y ) the set of edges
with one endpoint in X − Y and the other endpoint in Y − X and d(X, Y ) :=
¯
|δ(X, Y )|, and also define d(X, Y ) := d(X ∩ Y, V − (X ∪ Y )). For X ⊆ V , define
δ(X) := δ(X, V − X) and the degree of X as d(X) := |δ(X)|. Denote the degree
of a vertex as d(v) := d({v}). Also denote the set of neighbors of v by N (v), and
call a vertex in N (v) a v-neighbor.
Let λ(s, t) be the maximum number of edge-disjoint paths between s and t in
V , and let r(s, t) be an edge-connectivity requirement for s, t ∈ V . The connec-
tivity requirement is global if rs,t = k for all s, t ∈ V , otherwise it is local. We
say a graph G satisfies the connectivity requirements if λ(s, t) ≥ r(s, t) for any
s, t ∈ V . The requirement r(X) of a set X ⊆ V is the maximum edge-connectivity
requirement between u and v with u ∈ X and v ∈ V − X. By Menger’s theorem,
to satisfy the requirements, it suffices to guarantee that d(X) ≥ r(X) for all
X ⊂ V . The surplus s(X) of a set X ⊆ V is defined as d(X) − r(X). A graph
satisfies the edge-connectivity requirements if s(X) ≥ 0 for all ∅ = X ⊂ V . For
X ⊂ V − x, X is called dangerous if s(X) ≤ 1 and tight if s(X) = 0. The
following proposition will be used throughout our proofs.
Proposition 4 ([10] Proposition 2.3). For X, Y ⊆ V at least one of the
following inequalities holds:
Efficient Edge Splitting-Off Algorithms 99
Lemma 7 ([7] Lemma 2.7). If d(x) = 3 and there is no cut edge incident to
x, then there are no maximal dangerous sets X, Y, Z and u, v, w ∈ N (x) with
u ∈ X ∩ Y , v ∈ X ∩ Z, w ∈ Y ∩ Z and u, v, w ∈
/ X ∩ Y ∩ Z.
Nagamochi and Ibaraki [21] gave a fast algorithm to find a sparse subgraph that
satisfies edge-connectivity requirements, which will be used in Section 3.3 as a
preprocessing step.
Theorem 8 ([21] Lemma 2.1). There is an O(m)-time algorithm to construct
a subgraph with O(rmax · n) edges that satisfies all the connectivity requirements.
As a key tool in checking local edge-connectivities, we need to construct a
Gomory-Hu tree, which is a compact representation of all pairwise min-cuts
of an undirected graph. Let G = (V, E) be an undirected graph, a Gomory-Hu
tree is a weighted tree T = (V, F ) with the following property. Consider any
s, t ∈ V , the unique s-t path P in T , an edge e = uv on P with minimum
weight, and any component K of T − e. Then the local edge-connectivity be-
tween s and t in G is equal to the weight of e in T , and δ(K) is a minimum s-t
cut in G. To check whether the connectivity requirements are satisfied, we only
need to check the pairs with λ(u, v) ≤ rmax . A partial Gomory-Hu tree Tk of G is
obtained from a Gomory-Hu tree T of G by contracting all edges with weight at
least k. Therefore, each node in Tk represents a subset of vertices S in G, where
the local edge-connectivity between each pair of vertices in S is at least k. For
vertices u, v ∈ G in different nodes of Tk , their local edge-connectivity (which
is less than k) is determined in the same way as in an ordinary Gomory-Hu
tree. Bhalgat et.al. [5] gave a fast randomized algorithm to construct a partial
Gomory-Hu tree. We will use the following theorem by setting k = rmax . The
following result can be obtained by using the algorithm in [15], with the fast tree
packing algorithm in [5].
Theorem 9 ([5, 15]). A partial Gomory-Hu tree Tk can be constructed in
Õ(km) expected time.
Proof. We prove the lemma by a simple induction. The statement holds trivially
for |U | = 2 by Proposition 5. Consider U = {u1 , u2 , . . . , uk+1 } ⊆ N (x) where ev-
ery pair (ui , uj ) is non-admissible. By induction, since every pair (ui , uj ) is non-
admissible, there are maximal dangerous sets X, Y such that {u1 , ..., uk−1 , uk } ⊆
X and {u1 , ..., uk−1 , uk+1 } ⊆ Y . Since (uk , uk+1 ) is non-admissible, by Propo-
sition 5, there is a dangerous set Z containing uk and uk+1 . If uk+1 ∈ / X and
uk ∈ / Y and there is some ui ∈ / Z, then X, Y and Z form a 3-dangerous-set
structure with u = ui , v = uk , w = uk+1 . Hence either X, Y or Z contains U .
Proof. We consider three cases based on the size of C. When |C| = 0, we simply
assign C = {u}. When |C| = 1, pick the vertex v ∈ C, and split-off (u, v) to
capacity. Either case (1) applies when either u or v becomes void, or case (2)
applies in the resulting graph after (u, v) is split-off to capacity. Hence, when
|C| ≤ 1, either case (1) or case (2) applies after only one splitting-off attempt.
102 L.C. Lau and C.K. Yung
that Trmax has at least two nodes. Let X be the node in Trmax that contains x
in G, and U1 , . . . , Up be the nodes adjacent to X in Trmax , and let XU1 be the
edge in Trmax with largest weight among XUi for 1 ≤ i ≤ p. See Figure (a).
X x U1
t
U2 Up W1 Wq
U1 U2 … Up … …
(a) (b)
Since each iteration reduces the degree of x by 2q−2 , with at most 2l+1 =
O(rmax ) successful iterations, we can then reduce d(x) to 2l+q−1 , i.e. reduce
d(x) by half. This procedure is applicable as long as q ≥ 3. Therefore, we can
reduce d(x) to 2l+2 by using this procedure for O(log n) times. The total running
time is thus Õ(2l+1 · log n · rmax 2 · n) = Õ(rmax 3 · n). Note that there are at most
Õ(rmax ) iterations and the failure probability of each iteration is at most 1/nc .
By the union bound, the probability for above randomized algorithm to fail
is at most 1/nc−1 . Therefore, with high probability, the algorithm succeeds in
Õ(rmax 3 · n) time to reduce d(x) to O(rmax ). Since the correctness of solution
can be verified by a Gomory-Hu Tree, this also gives a Las Vegas algorithm with
the same expected runtime.
Lemma 16 ([2] Lemma 5.4, [24] Lemma 2.6). If |DP | ≥ 3, then inequal-
ity (4a) holds for every X, Y ∈ DP . Furthermore, X ∩ Y = {v} and is a tight
set for any X, Y ∈ DP .
Lemma 17. |DP | ≤ rmax − 1 when |DP | ≥ 3.
Proof. By Lemma 16, we have X ∩ Y = {v} for any X, Y ∈ DP . For each set
X ∈ DP , we have d(x, v) ≥ 1 and d(x, X − v) ≥ 1 by the minimality of DP .
Therefore, we must have d(v, X − v) ≥ 1 by Proposition 15. By Lemma 16, X − v
and Y − v are disjoint for each pair X, Y ∈ DP . Since d(v, X − v) ≥ 1 for each
X ∈ DP and d(x, v) ≥ 1, it follows that |DP | ≤ d(v) − 1. By Lemma 16, {v} is
a tight set, and thus |DP | ≤ d(v) − 1 ≤ rmax − 1.
An Inductive Argument: The goal is to prove that |P | ≤ rmax − 1 + |DP |.
By Lemma 17, this holds if d(x, X − v) = 1 for every dangerous set X ∈ DP .
Hence we assume that there is a dangerous set A ∈ DP with d(x, A − v) ≥ 2;
this property will only be used at the very end of the proof. By Lemma 16,
inequality (4a) holds for A and B for every B ∈ DP . By the minimality of DP ,
there exists a x-neighbor a ∈ A which is not contained in any other set in DP .
Similarly, there exists b ∈ B which is not contained in any other set in DP . The
following lemma shows that the edge pair (xa, xb) is admissible.
Lemma 18. For any A, B ∈ DP satisfying inequality (4a), an edge pair (xa, xb)
is admissible if a ∈ A − B and b ∈ B − A.
Proof. Suppose, by way of contradiction, that (xa, xb) is non-admissible. Then,
by Proposition 5, there exists a maximal dangerous set C containing a and b. We
claim that v ∈ C; otherwise there exists a 3-dangerous-set structure, contradict-
ing Lemma 7. Then d(x, A ∩ C) ≥ d(x, {v, a}) ≥ 2, and so inequality (4b) cannot
¯ C) ≥
hold for A and C, since 1 + 1 ≥ s(A) + s(C) ≥ s(A − C) + s(C − A) + 2d(A,
0 + 0 + 2 · 2. Therefore, inequality (4a) must hold for A and C. Since A and
C are maximal dangerous sets, A ∪ C cannot be a dangerous set, and thus
1 + 1 ≥ s(A) + s(C) ≥ s(A ∪ C) + s(A ∩ C) + 2d(A, C) ≥ 2 + s(A ∩ C) + 0, which
implies that A ∩ C is a tight set, but this contradicts the assumption that each
tight set is a singleton as {v, a} ⊆ A ∩ C.
After splitting-off (xa, xb), let the resulting graph be G and P = P − {xa, xb}.
Clearly, since each edge in P is a non-admissible partner of xv in G, every edge
in P is still a non-admissible partner of xv in G . Furthermore, by contracting
non-trivial tight sets in G , each edge in P is still a non-admissible partner of
xv by Lemma 6. Hence we assume all tight sets in G are singletons. Let DP be a
108 L.C. Lau and C.K. Yung
minimal set of maximal dangerous sets such that (i) each set D ∈ DP covers the
edge xv and (ii) each edge in P is covered by some set D ∈ DP . The following
lemma shows that there exists DP with |DP | ≤ |DP | − 2.
Lemma 19. When |DP | ≥ 3, the edges in P can be covered by a set DP of
maximal dangerous sets in G such that (i) each set in DP covers xv, and (ii)
each edge in P is covered by some set in DP , and (iii) |DP | ≤ |DP | − 2.
Proof. We will use the dangerous sets in DP to construct DP . Since each pair of sets
in DP satisfies inequality (4a), we have s(A∪D) = 2 before splitting-off (xa, xb) for
each D ∈ DP . Also, before splitting-off (xa, xb), for A, B, C ∈ DP , inequality (4b)
cannot hold for A ∪ B and C because 2 + 1 = s(A ∪ B) + s(C) ≥ s((A ∪ B) − C) +
¯
s(C − (A∪B))+ 2d(A∪B, C) ≥ 2 + 0 + 2 ·1, where the last inequality follows since
v ∈ A∩B∩C and (A∪B)−C is not dangerous (as it covers the admissible edge pair
(xa, xb)). Therefore inequality (4a) must hold for A ∪ B and C, which implies that
s(A ∪ B ∪ C) ≤ 3 since 2 + 1 = s(A ∪ B) + s(C) ≥ s((A ∪ B) ∪ C) + s((A ∪ B) ∩ C).
For A and B as defined before Lemma 18, since s(A ∪ B) = 2 before splitting-off
(xa, xb), A∪B becomes a tight set after splitting-off (xa, xb). For any other set C ∈
DP −A−B, since s(A∪B ∪C) ≤ 3 before splitting-off (xa, xb), A∪B ∪C becomes
a dangerous set after splitting-off (xa, xb). Hence, after splitting-off (xa, xb) and
contracting the tight set A ∪ B into v, each set in DP − A − B becomes a dangerous
set. Then DP = DP − A − B is a set of dangerous sets covering each edge in P ,
satisfying properties (i)-(iii). By replacing a dangerous set C ∈ DP by a maximal
dangerous set C ⊇ C and removing redundant dangerous sets in DP so that it
minimally covers P , we have found DP as required by the lemma.
Recall that we chose A with d(x, A − v) ≥ 2, and hence d(x, v) ≥ 2 after the
splitting-off and contraction of tight sets. Therefore, inequality (4a) holds for
every two maximal dangerous sets in DP . By induction, when |DP | ≥ 3, we
have |P | = |P | + 2 ≤ rmax − 1 + |DP | + 2 ≤ rmax − 1 + |DP |. In the base case
when |DP | = 2 and A, B ∈ DP satisfy (4a), the same argument in Lemma 19 can
be used to show that the edges in P is covered by one tight set after splitting-off
(xa, xb), and thus |P | = |P |+ 2 ≤ rmax − 1 + 2 ≤ rmax − 1 + |DP |. This completes
the proof that |P | ≤ rmax − 1 + |DP |, proving the theorem.
5 Concluding Remarks
Theorem 3 can be applied to constrained edge splitting-off problems, and give
additive approximation algorithms for constrained augmentation problems. The
efficient algorithms can also be adapted to these problems. We refer the reader
to [25] for these results.
References
1. Bang-Jensen, J., Frank, A., Jackson, B.: Preserving and increasing local edge-
connectivity in mixed graphs. SIAM J. Disc. Math. 8(2), 155–178 (1995)
2. Bang-Jensen, J., Jordán, T.: Edge-connectivity augmentation preserving simplicity.
SIAM Journal on Discrete Mathematics 11(4), 603–623 (1998)
Efficient Edge Splitting-Off Algorithms 109
3. Bernáth, A., Király, T.: A new approach to splitting-off. In: Lodi, A., Panconesi, A.,
Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 401–415. Springer, Heidelberg
(2008)
4. Benczúr, A.A., Karger, D.R.: Augmenting undirected edge connectivity in O(n2 )
time. Journal of Algorithms 37(1), 2–36 (2000)
5. Bhalgat, A., Hariharan, R., Kavitha, T., Panigrahi, D.: An Õ(mn) Gomory-Hu
tree construction algorithm for unweighted graphs. In: STOC 2007, pp. 605–614
(2007)
6. Bhalgat, A., Hariharan, R., Kavitha, T., Panigrahi, D.: Fast edge splitting and
Edmonds’ arborescence construction for unweighted graphs. In: SODA ’08, pp.
455–464 (2008)
7. Chan, Y.H., Fung, W.S., Lau, L.C., Yung, C.K.: Degree Bounded Network Design
with Metric Costs. In: FOCS ’08, pp. 125–134 (2008)
8. Cheng, E., Jordán, T.: Successive edge-connectivity augmentation problems. Math-
ematical Programming 84(3), 577–593 (1999)
9. Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM
Journal on Discrete Mathematics 5(1), 25–53 (1992)
10. Frank, A.: On a theorem of Mader. Ann. of Disc. Math. 101, 49–57 (1992)
11. Frank, A., Király, Z.: Graph orientations with edge-connection and parity con-
straints. Combinatorica 22(1), 47–70 (2002)
12. Gabow, H.N.: Efficient splitting off algorithms for graphs. In: STOC ’94, pp. 696–
705 (1994)
13. Goemans, M.X., Bertsimas, D.J.: Survivable networks, linear programming relax-
ations and the parsimonious property. Math. Prog. 60(1), 145–166 (1993)
14. Gomory, R.E., Hu, T.C.: Multi-terminal network flows. Journal of the Society for
Industrial and Applied Mathematics 9(4), 551–570 (1961)
15. Hariharan, R., Kavitha, T., Panigrahi, D.: Efficient algorithms for computing all
low st edge connectivities and related problems. In: SODA ’07, pp. 127–136 (2007)
16. Jordán, T.: On minimally k-edge-connected graphs and shortest k-edge-connected
Steiner networks. Discrete Applied Mathematics 131(2), 421–432 (2003)
17. Lau, L.C.: An approximate max-Steiner-tree-packing min-Steiner-cut theorem.
Combinatorica 27(1), 71–90 (2007)
18. Lovász, L.: Lecture. Conference of Graph Theory, Prague (1974); See also Combi-
natorial problems and exercises. North-Holland (1979)
19. Mader, W.: A reduction method for edge-connectivity in graphs. Annals of Discrete
Mathematics 3, 145–164 (1978)
20. Nagamochi, H.: A fast edge-splitting algorithm in edge-weighted graphs. IEICE
Transactions on Fundamentals of Electronics, Communications and Computer Sci-
ences, 1263–1268 (2006)
21. Nagamochi, H., Ibaraki, T.: Linear time algorithm for finding a sparse k-connected
spanning subgraph of a k-connected graph. Algorithmica 7(1), 583–596 (1992)
22. Nagamochi, H., Ibaraki, T.: Deterministic O(nm) time edge-splitting in undirected
graphs. Journal of Combinatorial Optimization 1(1), 5–46 (1997)
23. Nash-Williams, C.S.J.A.: On orientations, connectivity and odd vertex pairings in
finite graphs. Canadian Journal of Mathematics 12, 555–567 (1960)
24. Szigeti, Z.: Edge-splittings preserving local edge-connectivity of graphs. Discrete
Applied Mathematics 156(7), 1011–1018 (2008)
25. Yung, C.K.: Edge splitting-off and network design problems. Master thesis, The
Chinese University of Hong Kong (2009)
On Generalizations of Network Design Problems with
Degree Bounds
Abstract. 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 direc-
tions: (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 al-
gorithms, hardness results, and integrality gaps for these problems.
1 Introduction
Iterative rounding and relaxation have arguably become the method of choice in dealing
with unconstrained and constrained network design problems. Starting with Jain’s ele-
gant iterative rounding scheme for the generalized Steiner network problem in [14], an
extension of this technique (iterative relaxation) has more recently lead to breakthrough
results in the area of constrained network design, where a number of linear constraints
are added to a classical network design problem. Such constraints arise naturally in
a wide variety of practical applications, and model limitations in processing power,
bandwidth or budget. The design of powerful techniques to deal with these problems is
therefore an important goal.
The most widely studied constrained network design problem is the minimum-cost
degree-bounded spanning tree problem. In an instance of this problem, we are given an
undirected graph, non-negative costs for the edges, and positive, integral degree-bounds
for each of the nodes. The problem is easily seen to be NP-hard, even in the absence
of edge-costs, since finding a spanning tree with maximum degree two is equivalent to
finding a Hamiltonian Path. A variety of techniques have been applied to this problem
[5,6,11,17,18,23,24], culminating in Singh and Lau’s breakthrough result in [27]. They
presented an algorithm that computes a spanning tree of at most optimum cost whose
degree at each vertex v exceeds its bound by at most 1, using the iterative relaxation
framework developed in [20,27].
The iterative relaxation technique has been applied to several constrained network
design problems: spanning tree [27], survivable network design [20,21], directed graphs
with intersecting and crossing super-modular connectivity [20,2]. It has also been ap-
plied to degree bounded versions of matroids and submodular flow [15].
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 110–123, 2010.
c Springer-Verlag Berlin Heidelberg 2010
On Generalizations of Network Design Problems with Degree Bounds 111
In this paper we further extend the applicability of iterative relaxation, and obtain
new or improved bicriteria approximation results for minimum crossing spanning tree
(MCST), crossing matroid intersection, and crossing lattice polyhedra. We also provide
hardness results and integrality gaps for these problems.
Notation. As is usual, when dealing with an undirected graph G = (V, E), for any
S ⊆ V we let δG (S) := {(u, v) ∈ E | u ∈ S, v ∈ S}. When the graph is clear from
context, the subscript is dropped. A collection {U1 , · · · , Ut } of vertex-sets is called
laminar if for every pair Ui , Uj in this collection, we have Ui ⊆ Uj , Uj ⊆ Ui , or
Ui ∩ Uj = ∅. A (ρ, f (b)) approximation for minimum cost degree bounded problems
refers to a solution that (1) has cost at most ρ times the optimum that satisfies the degree
bounds, and (2) satisfies the relaxed degree constraints in which a bound b is replaced
with a bound f (b).
results also cannot be used to obtain a small additive violation, especially if b is large.
In particular, both the results [4,8] for general MCST √ are based on the natural LP relax-
ation, for which there is an integrality gap of b + Ω( n) even without regard to costs
and when m = O(n) [26] (see also [3]). On the other hand, Theorem 1 shows that a
purely additive O(log n) guarantee on degree (relative to the LP relaxation and even in
presence of costs) is indeed achievable for MCST, when the degree-bounds arise from
a laminar cut-family.
The algorithm in Theorem 1 is based on iterative relaxation and uses two main new
ideas. Firstly, we drop a carefully chosen constant fraction of degree-constraints in each
iteration. This is crucial as it can be shown that dropping one constraint at a time as in
the usual applications of iterative relaxation can indeed lead to a degree violation of
Ω(Δ). Secondly, the algorithm does not just drop degree constraints, but in some itera-
tions it also generates new degree constraints, by merging existing degree constraints.
All previous applications of iterative relaxation to constrained network design treat
connectivity and degree constraints rather asymmetrically. While the structure of the
connectivity constraints of the underlying LP is used crucially (e.g., in the ubiquitous
uncrossing argument), the handling of degree constraints is remarkably simple. Con-
straints are dropped one by one, and the final performance of the algorithm is good only
if the number of side constraints is small (e.g., in recent work by Grandoni et al. [12]),
or if their structure is simple (e.g., if the ‘frequency’ of each element is small). In con-
trast, our algorithm for laminar MCST exploits the structure of degree constraints in a
non-trivial manner.
Hardness Results. We obtain the following hardness of approximation for the general
MCST problem (and its matroid counterpart). In particular this rules out any algorithm
for MCST that has additive constant degree violation, even without regard to costs.
Theorem 2. Unless N P has quasi-polynomial time algorithms, the MCST problem
admits no polynomial time O(logα m) additive approximation for the degree bounds
for some constant α > 0; this holds even when there are no costs.
The proof for this theorem is given in Section 3, and uses a a two-step reduction from
the well-known Label Cover problem. First, we show hardness for a uniform matroid
instance. In a second step, we then demonstrate how this implies the result for MCST
claimed in Theorem 2.
Note that our hardness bound nearly matches the result obtained by Chekuri et al.
in [8]. We note however that in terms of purely additive degree guarantees,√a large gap
remains. As noted above, there is a much stronger lower bound of b + Ω( n) for LP-
based algorithms [26] (even without regard to costs), which is based on discrepancy. In
light of the small number of known hardness results for discrepancy type problems, it
is unclear how our bounds for MCST could be strengthened.
Degree Bounds in More General Settings. We consider crossing versions of other clas-
sic combinatorial optimization problems, namely matroid intersection and lattice poly-
hedra. We discuss our results briefly and defer the proofs to the full version of the
paper [3].
On Generalizations of Network Design Problems with Degree Bounds 113
We remark that there are alternate definitions of matroid intersection (e.g., see Schri-
jver [25]) and that our result below extends to those as well.
Let Δ = maxe∈E |{i ∈ [m] | e ∈ Ei }| be the largest number of sets Ei that any
element of E belongs to, and refer to it as frequency.
Theorem 3. Any optimal basic solution x∗ of the linear relaxation of the minimum
crossing matroid intersection problem can be rounded into an integral solution x̂ such
that x̂(S) ≥ max{r1 (S), r2 (S)} for all S ⊆ E and
The algorithm for this theorem again uses iterative relaxation, and its proof is based on
a ‘fractional token’ counting argument similar to the one used in [2].
An interesting special case is for the bounded-degree arborescence problem (where
Δ = 1). As the set of arborescences in a digraph can be expressed as the intersection
of partition and graphic matroids, Theorem 3 readily implies a (2, 2b) approximation
for this problem. This is an improvement over the previously best-known (2, 2b + 2)
bound [20] for this problem.
The bounded-degree arborescence problem is potentially of wider interest since it is
a relaxation of ATSP, and it is hoped that ideas from this problem lead to new ideas
for ATSP. In fact Theorem 3 also implies an improved (2, 2b)-approximation for the
bounded-degree arborescence packing problem, where the goal is to pack a given num-
ber of arc-disjoint arborescences while satisfying degree-bounds on vertices (arbores-
cence packing can again be phrased as matroid intersection). The previously best known
bound for this problem was (2, 2b + 4) [2]. We also give the following integrality gap.
Theorem 4. For any > 0, there exists an instance of unweighted minimum crossing
arborescence for which the LP is feasible, and any integral solution must violate the
bound on some set {Ei }m
i=1 by a multiplicative factor of at least 2 − . Moreover, this
instance has Δ = 1, and just one non-degree constraint.
Thus Theorem 3 is the best one can hope for, relative to the LP relaxation. First,
Theorem 4 implies that the multiplicative factor in the degree cannot be improved be-
yond 2 (even without regard to costs). Second, the lower bound for arborescences with
costs presented in [2] implies that no cost-approximation ratio better than 2 is possible,
without violating degrees by a factor greater than 2.
Crossing Lattice Polyhedra. Classical lattice polyhedra form a unified framework for
various discrete optimization problems and go back to Hoffman and Schwartz [13] who
proved their integrality. They are polyhedra of type
setting. [15] also considered a degree-bounded version of the submodular flow problem
and gave a (1, b + 1) approximation guarantee.
The bounded-degree arborescence problem was considered in Lau et al. [20], where
a (2, 2b + 2) approximation guarantee was obtained. Subsequently Bansal et al. [2]
designed an algorithm that for any 0 < ≤ 1/2, achieves a (1/, bv /(1 − ) + 4)
approximation guarantee. They also showed that this guarantee is the best one can hope
for via the natural LP relaxation (for every 0 < ≤ 1/2). In the absence of edge-costs,
[2] gave an algorithm that violates degree bounds by at most an additive two. Recently
Nutov [22] studied the arborescence problem under weighted degree constraints, and
gave a (2, 5b) approximation for it.
Lattice polyhedra were first investigated by Hoffman and Schwartz [13] and the nat-
ural LP relaxation was shown to be totally dual integral. Even though greedy-type algo-
rithms are known for all examples mentioned earlier, so far no combinatorial algorithm
has been found for lattice polyhedra in general. Two-phase greedy algorithms have been
established only in cases where an underlying rank function satisfies a monotonicity
property [10], [9].
s.t. x(E(V )) = |V | − |F | − 1
x(E(U )) ≤ |U | − |F (U )| − 1 ∀U ⊂ V
x(δE (S)) ≤ b(S) ∀S ∈ L
xe ≥ 0 ∀e ∈ E
extreme point solution to this LP. By reducing degree bounds b(S), if needed, we as-
sume that x satisfies all degree bounds at equality (the degree bounds may therefore be
fractional-valued). Let α := 24.
Definition 2. An edge e ∈ E is said to be local for S ∈ L if e has at least one end-point
in S but is neither in E(C) nor in δ(C) ∩ δ(S) for any grandchild C of S. Let local(S)
denote the set of local edges for S. A node S ∈ L is said to be good if |local(S)| ≤ α.
The figure on the left shows a set S, its
children B1 and B2 , and grand-children
C1 , . . . , C4 ; edges in local(S) are drawn
S
solid, non-local ones are shown dashed. C4 B2
C1
Initially, E is the set of edges in the C 3
B1
given graph, F ← ∅, L is the original C2
laminar family of vertex sets for which
there are degree bounds, and an arbitrary
linear ordering is chosen on the children
of each node in L. In a generic iteration (F, E, L, b), the algorithm performs one of the
following steps (see also Figure 1):
Assuming that one of the above steps applies at each iteration, the algorithm terminates
when E = ∅ and outputs the final set F as a solution. It is clear that the algorithm
outputs a spanning tree of G. An inductive argument (see e.g. [20]) can be used to show
that the LP (1) is feasible at each each iteration and c(F ) + zcur ≤ zo where zo is
the original LP value, zcur is the current LP value, and F is the chosen edge-set at the
current iteration. Thus the cost of the final solution is at most the initial LP optimum zo .
Next we show that one of the four iterative steps always applies.
Lemma 1. In each iteration, one of the four steps above applies.
On Generalizations of Network Design Problems with Degree Bounds 117
S S
N1 T N2 N3 N4 N5
1 2 3 4 DropN step DropL step
Good non-leaf S Good leaves {Ni}5i=1
S
S
1 2 3 4 T
M1 M2
Fig. 1. Examples of the degree constraint modifications DropN and DropL
Proof. Let x∗ be the optimal basic solution of (1), and suppose that the first two steps
do not apply. Hence, we have 0 < x∗e < 1 for all e ∈ E. The fact that x∗ is a basic
solution together with a standard uncrossing argument (e.g., see [14]) implies that x∗ is
uniquely defined by
where S is a laminar subset of the tight spanning tree constraints, and L is a subset of
tight degree constraints, and where |E| = |S| + |L |.
A simple counting argument (see, e.g., [27]) shows that there are at least 2 edges
induced on each S ∈ S that are not induced on any of its children; so 2|S| ≤ |E|. Thus
we obtain |E| ≤ 2|L | ≤ 2|L|.
From the definition of local edges, we get that any edge e = (u, v) is local to at most
the following six sets: the smallest set S1 ∈ L containing u, the smallest set S2 ∈ L
containing v, the parents P1 and P2 of S1 and S2 resp., the least-common-ancestor L
of P1 and P2 , andthe parent of L. Thus S∈L |local(S)| ≤ 6|E|. From the above,
we conclude that S∈L |local(S)| ≤ 12|L|. Thus at least |L|/2 sets S ∈ L must have
|local(S)| ≤ α = 24, i.e., must be good. Now either at least |L|/4 of them must be
non-leaves or at least |L|/4 of them must be leaves. In the first case, step 3 holds and in
the second case, step 4 holds.
It remains to bound the violation in the degree constraints, which turns out to be rather
challenging. We note that this is unlike usual applications of iterative rounding/relaxation,
where the harder part is in showing that one of the iterative steps applies.
It is clear that the algorithm reduces the size of L by at least |L|/8 in each DropN or
DropL iteration. Since the initial number of degree constraints is at most 2n − 1, we get
the following lemma.
Lemma 2. The number of drop iterations (DropN and DropL) is T := O(log n).
Performance guarantee for degree constraints. We begin with some notation. The
iterations of the algorithm are broken into periods between successive drop iterations:
there are exactly T drop-iterations (Lemma 2). In what follows, the t-th drop iteration
118 N. Bansal et al.
is called round t. The time t refers to the instant just after round t; time 0 refers to the
start of the algorithm. At any time t, consider the following parameters.
– Lt denotes the laminar family of degree constraints.
– Et denotes the undecided edge set, i.e., support of the current
LP optimal solution.
– For any set B of consecutive siblings in Lt , Bnd(B, t) = N ∈B b(N ) equals the
sum of the residual degree bounds on nodes of B.
– For any set B of consecutive siblings in Lt , Inc(B, t) equals the number of edges
from δEt (∪N ∈B N ) included in the final solution.
Recall that b denotes the residual degree bounds at any point in the algorithm. The
following lemma is the main ingredient in bounding the degree violation.
Lemma 3. For any set B of consecutive siblings in Lt (at any time t), Inc(B, t) ≤
Bnd(B, t) + 4α · (T − t).
Observe that this implies the desired bound on each original degree constraint S: using
t = 0 and B = {S}, the violation is bounded by an additive 4α · T term.
Proof. The proof of this lemma is by induction on T − t. The base case t = T is trivial
since the only iterations after this correspond to including 1-edges: hence there is no
bound, i.e. Inc({N }, T) ≤ b(N ) for all N ∈ LT . Hence for any
violation in any degree
B ⊆ L, Inc(B, T ) ≤ N ∈B Inc({N }, T ) ≤ N ∈B b(N ) = Bnd(B, T ).
Now suppose t < T , and assume the lemma for t + 1. Fix a consecutive B ⊆ Lt . We
consider different cases depending on what kind of drop occurs in round t + 1.
DropN round. Here either all nodes in B get dropped or none gets dropped.
Case 1: None of B is dropped. Then observe that B is consecutive in Lt+1 as well;
so the inductive hypothesis implies Inc(B, t + 1) ≤ Bnd(B, t + 1) + 4α · (T − t − 1).
Since the only iterations between round t and round t + 1 involve edge-fixing, we have
Inc(B, t) ≤ Bnd(B, t) − Bnd(B, t + 1) + Inc(B, t + 1) ≤ Bnd(B, t) + 4α · (T − t − 1) ≤
Bnd(B, t) + 4α · (T − t).
Case 2: All of B is dropped. Let C denote the set of all children (in Lt ) of nodes in
B. Note that C consists of consecutive siblings in Lt+1 , and inductively Inc(C, t + 1) ≤
Bnd(C, t + 1) + 4α · (T − t − 1). Let S ∈ Lt denote the parent of the B-nodes;
so C are grand-children of S in Lt . Let x denote the optimal LP solution just before
round t + 1 (when the degree bounds are still given by Lt ), and H = Et+1 the support
edges of x. At that point, we have b(N ) = x(δ(N )) for all N ∈ B ∪ C. Also let
Bnd (B, t + 1) := N ∈B b(N ) be the sum of bounds on B-nodes just before round
t+ 1. Since S is t + 1, |Bnd (B,
a good node in round t + 1) − Bnd(C, t + 1)| =
| N ∈B b(N ) − M∈C b(M )| = | N ∈B x(δ(N )) − M∈C x(δ(M ))| ≤ 2α. The
last inequality follows since S is good; the factor of 2 appears since some edges, e.g.,
the edges between two children or two grandchildren of S, may get counted twice. Note
also that the symmetric difference of δH (∪N ∈B N ) and δH (∪M∈C M ) is contained in
local(S). Thus δH (∪N ∈B N ) and δH (∪M∈C M ) differ in at most α edges.
Again since all iterations between time t and t + 1 are edge-fixing:
The first inequality follows from simple counting; the second uses Claim 6, the third
is the induction hypothesis (since C is consecutive), and the fourth is Bnd(C, t + 1) ≤
Bnd (B, t + 1) + 2α (from above).
This completes the proof of the inductive step and hence Lemma 3.
3 Hardness Results
We now prove Theorem 2. The first step to proving this result is a hardness for the more
general minimum crossing matroid basis problem: given a matroid M on a ground set
V of elements, a cost function c : V → R+ , and degree bounds specified by pairs
i=1 (where each Ei ⊆ V and bi ∈ N), find a minimum cost basis I in M
{(Ei , bi )}m
such that |I ∩ Ei | ≤ bi for all i ∈ [m].
Theorem 7. Unless N P has quasi-polynomial time algorithms, the unweighted min-
imum crossing matroid basis problem admits no polynomial time O(logc m) additive
approximation for the degree bounds for some fixed constant c > 0.
Proof. We reduce from the label cover problem [1]. The input is a graph G = (U, E)
where the vertex set U is partitioned into pieces U1 , · · · , Un each having size q, and all
edges in E are between distinct pieces. We say that there is a superedge between Ui and
Uj if there is an edge connecting some vertex in Ui to some vertex in Uj . Let t denote
the total number of superedges; i.e.,
- .-
- [n] -
t = -- (i, j) ∈ : there is an edge in E between Ui and Uj --
2
The goal is to pick one vertex from each part {Ui }ni=1 so as to maximize the number of
induced edges. This is called the value of the label cover instance and is at most t.
It is well known that there exists a universal constant γ > 1 such that for every
k ∈ N, there is a reduction from any instance of SAT (having size N ) to a label cover
instance "G = (U, E), q, t# such that:
– If the SAT instance is satisfiable, the label cover instance has optimal value t.
– If the SAT instance is not satisfiable, the label cover instance has optimal value
< t/γ k .
– |G| = N O(k) , q = 2k , |E| ≤ t2 , and the reduction runs in time N O(k) .
We consider a uniform matroid M with rank t on ground set E (recall that any subset
of t edges is a basis in a uniform matroid). We now construct a crossing matroid basis
instance I on M. There is a set of degree bounds corresponding to each i ∈ [n]: for
every collection C of edges incident to vertices in Ui such that no two edges in C are
incident to the same vertex in Ui , there is a degree bound in I requiring at most one
element to be chosen from C. Note that the number of degree bounds m is at most
k
|E|q ≤ N O(k 2 ) . The following claim links the SAT and crossing matroid instances.
Its proof is deferred to the full version of this paper.
Claim 8. [Yes instance] If the SAT instance is satisfiable, there is a basis (i.e. subset
B ⊆ E with |B| = t) satisfying all degree bounds.
√subset B ⊆ E with |B | ≥ t/2
[No instance] If the SAT instance is unsatisfiable, every
k/2
violates some degree bound by an additive ρ = γ / 2.
On Generalizations of Network Design Problems with Degree Bounds 121
The steps described in the above reduction can be done in time polynomial in m and
|G|. Also, instead of randomly choosing vertices from the sets Wi , we can use condi-
tional expectations to derive a deterministic algorithm that recovers at least t/ρ2 edges.
Setting k = Θ(log log N ) (recall that N is the size of the original SAT instance), we
a
obtain an instance of bounded-degree matroid basis of size max{m, |G|} = N log N
and ρ = logb N , where a, b > 0 are constants. Note that log m = loga+1 N , which
implies ρ = logc m for c = a+1 b
> 0, a constant. Thus it follows that for this constant
c > 0 the bounded-degree matroid basis problem has no polynomial time O(logc m)
additive approximation for the degree bounds, unless N P has quasi-polynomial time
algorithms.
We now prove Theorem 2.
Proof. [Proof of Theorem 2] We show how the bases of a uniform matroid can be
represented in a suitable instance of the crossing spanning tree problem. Let the uniform √
matroid from Theorem 7 consist of e elements and have rank t ≤ e; recall that t ≥ e
and clearly m ≤ 2e . We construct a graph as in Figure 2, with vertices v1 , · · · , ve
corresponding to elements in the uniform matroid. Each vertex vi is connected to the
root r by two vertex-disjoint paths: "vi , ui , r# and "vi , wi , r#. There are no costs in
this instance. Corresponding to each degree bound (in the uniform matroid) of b(C)
on a subset C ⊆ [e], there is a constraint to pick at most |C| + b(C) edges from
δ({ui / | i ∈ C}). Additionally, there is a special degree bound of 2e − t on the edge-set
E = ei=1 δ(wi ); this corresponds to picking a basis in the uniform matroid.
Observe that for each i ∈ [e], any r
spanning tree must choose exactly three u
1
w
edges amongst {(r, ui ), (ui , vi ), (r, wi ), w
e
1
e u
(wi , vi )}, in fact any three edges suffice. u
i w
i
v1
v
Hence every spanning tree T in this graph e
Since B ∗ satisfies its degree-bounds, T ∗ satisfies all degree bounds derived from the
crossing matroid instance. For the special degree bound on E , note that |T ∗ ∩ E | =
2e − |B ∗ | = 2e − t; so this is also satisfied. Thus there is a spanning tree satisfying all
the degree bounds.
No instance. Every subset B ⊆ [e] with |B | ≥ t/2 (i.e. near basis) violates some
degree bound by an additive ρ = Ω(logc m) term, where c > 0 is a fixed constant.
Consider any spanning tree T that corresponds to subset X ⊆ [e] as described above.
122 N. Bansal et al.
References
1. Arora, S., Babai, L., Stern, J., Sweedyk, Z.: The hardness of approximate optima in lattices,
codes, and systems of linear equations. J. Comput. Syst. Sci. 54(2), 317–331 (1997)
2. Bansal, N., Khandekar, R., Nagarajan, V.: Additive guarantees for degree bounded network
design. In: STOC, pp. 769–778 (2008)
3. Bansal, N., Khandekar, R., Könemann, J., Nagarajan, V., Peis, B.: On Generalizations of
Network Design Problems with Degree Bounds (full version),Technical Report (2010)
4. Bilo, V., Goyal, V., Ravi, R., Singh, M.: On the crossing spanning tree problem. In: Jansen,
K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) RANDOM 2004 and APPROX 2004. LNCS,
vol. 3122, pp. 51–60. Springer, Heidelberg (2004)
5. Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: What would Edmonds do? Augment-
ing paths and witnesses for degree-bounded MSTs. In: Chekuri, C., Jansen, K., Rolim,
J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 26–39.
Springer, Heidelberg (2005)
6. Chaudhuri, K., Rao, S., Riesenfeld, S., Talwar, K.: Push relabel and an improved approxima-
tion algorithm for the bounded-degree MST problem. In: Bugliesi, M., Preneel, B., Sassone,
V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 191–201. Springer, Heidelberg
(2006)
7. Chazelle, B.: The Discrepancy Method: Randomness and Complexity. Cambridge University
Press, Cambridge (2000)
8. Chekuri, C., Vondrák, J., Zenklusen, R.: Dependent Randomized Rounding for Matroid Poly-
topes and Applications (2009), http://arxiv.org/abs/0909.4348
9. Faigle, U., Peis, B.: Two-phase greedy algorithms for some classes of combinatorial linear
programs. In: SODA, pp. 161–166 (2008)
10. Frank, A.: Increasing the rooted connectivity of a digraph by one. Math. Programming 84,
565–576 (1999)
11. Goemans, M.X.: Minimum Bounded-Degree Spanning Trees. In: FOCS, pp. 273–282 (2006)
12. Grandoni, F., Ravi, R., Singh, M.: Iterative Rounding for Multiobjective Optimization Prob-
lems. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 95–106. Springer,
Heidelberg (2009)
13. Hoffman, A., Schwartz, D.E.: On lattice polyhedra. In: Hajnal, A., Sos, V.T. (eds.) Proceed-
ings of Fifth Hungarian Combinatorial Coll, pp. 593–598. North-Holland, Amsterdam (1978)
14. Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem.
In: Combinatorica, pp. 39–61 (2001)
15. Király, T., Lau, L.C., Singh, M.: Degree bounded matroids and submodular flows. In: Lodi,
A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 259–272. Springer,
Heidelberg (2008)
On Generalizations of Network Design Problems with Degree Bounds 123
16. Klein, P.N., Krishnan, R., Raghavachari, B., Ravi, R.: Approximation algorithms for finding
low degree subgraphs. Networks 44(3), 203–215 (2004)
17. Könemann, J., Ravi, R.: A matter of degree: Improved approximation algorithms for degree
bounded minimum spanning trees. SIAM J. on Computing 31, 1783–1793 (2002)
18. Könemann, J., Ravi, R.: Primal-Dual meets local search: approximating MSTs with nonuni-
form degree bounds. SIAM J. on Computing 34(3), 763–773 (2005)
19. Korte, B., Vygen, J.: Combinatorial Optimization, 4th edn. Springer, New York (2008)
20. Lau, L.C., Naor, J., Salavatipour, M.R., Singh, M.: Survivable network design with degree or
order constraints (full version). In: STOC, pp. 651–660 (2007)
21. Lau, L.C., Singh, M.: Additive Approximation for Bounded Degree Survivable Network
Design. In: STOC, pp. 759–768 (2008)
22. Nutov, Z.: Approximating Directed Weighted-Degree Constrained Networks. In: Goel, A.,
Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX 2008 and RANDOM 2008. LNCS,
vol. 5171, pp. 219–232. Springer, Heidelberg (2008)
23. Ravi, R., Marathe, M.V., Ravi, S.S., Rosenkrantz, D.J., Hunt, H.B.: Many birds with one
stone: Multi-objective approximation algorithms. In: STOC, pp. 438–447 (1993)
24. Ravi, R., Singh, M.: Delegate and Conquer: An LP-based approximation algorithm for Min-
imum Degree MSTs. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP
2006. LNCS, vol. 4051, pp. 169–180. Springer, Heidelberg (2006)
25. Schrijver, A.: Combinatorial Optimization. Springer, Heidelberg (2003)
26. Singh, M.: Personal Communication (2008)
27. Singh, M., Lau, L.C.: Approximating minimum bounded degree spanning trees to within one
of optimal. In: STOC, pp. 661–670 (2007)
A Polyhedral Study of the Mixed Integer Cut
1 Introduction
Consider the integer program
min(cx : Ax = b, x ∈ Zn+ ), (1)
where A ∈ Zm×n , b ∈ Zm , and c ∈ Rn . Given a basis B of the LP relaxation of
(1), the group relaxation of X, is obtained by relaxing non-negativity on xB , i.e.
XGR = {x : BxB + N xN = b, xB ∈ Zm , xN ∈ Zn−m
+ }.
It follows that for an integer vector xN , xB is integral if and only if N xN ≡ b
(mod B); that is, N xN − b belongs to the lattice generated by the columns of
B.
Consider the group G of equivalence classes of Zn modulo B. Let N be the
set of distinct equivalence classes represented by the columns of N , and let g0
be the equivalence class represented by b. The group polyhedron is given by
⎧ ⎫
⎨ ⎬
|N |
P (N , g0 ) = conv t ∈ Z+ : gt(g) = g0 ,
⎩ ⎭
g∈N
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 124–134, 2010.
c Springer-Verlag Berlin Heidelberg 2010
A Polyhedral Study of the Mixed Integer Cut 125
When A consists of a single row, the master group polyhedron is of the form
⎧ ⎫
⎨ |D|−1
⎬
|D|−1
P (CD , r) = conv t ∈ Z+ : iti ≡ r (mod D)
⎩ ⎭
i=1
Further, we will always assume that r > 0 and that n ≥ 3. By observing that the
recession cone of P (Cn , r) is the non-negative orthant, one notes that P (Cn , r) is
of dimension n − 1. It is also easily observed that P (Km ) is of dimension m − 1.
By the assumption that n ≥ 3, it follows that the non-negativity constraints
are facet defining. In our discussion, these shall be referred to as the trivial facets.
126 S. Tyber and E.L. Johnson
When speaking of valid inequalities for the master knapsack polyhedra, we shall
use the same notation where entries are understood to be of appropriate dimen-
sion. Denote the mixed integer cut by (μ, 1), where
i
i≤r
μi = rn−i .
n−r i>r
For completeness, we include the following theorem to which we have already
referred:
Theorem 1 (Gomory [3]). (μ, 1) is a facet of P (Cn , r).
We consider the mixed integer cut as the polytope
PMIC (n, r) = P (Cn , r) ∩ {t : μt = 1}.
Since (μ, 1) is a facet of P (Cn , r) and P (Cn , r) is integral, PMIC (n, r) is also
integral. Note that a facet (π, π0 ) is adjacent to (μ, 1) if and only if it is a facet
of PMIC (n, r). We assume that 1 < r < n − 1, since otherwise the non-trivial
facets of PMIC (n, r) are clearly knapsack facets.
We shall now discuss the connection between PMIC (n, r) and the master knap-
sack polytopes P (Kr ) and P (Kn−r ). The following proposition highlights an
operation that we will call extending a knapsack solution.
Proposition 1. If x ∈ P (Kr ), x = (x1 , . . . , xr ), then t = (x1 , . . . , xr , 0, . . . , 0)
belongs to PMIC (n, r). Likewise, if x ∈ P (Kn−r ), x = (x1 , . . . , xn−r ), then t =
(0, . . . , 0, xn−r , . . . , x1 ) belongs to PMIC (n, r).
Proof. For x ∈ P (Kr ), the result is trivial. So take x ∈ P (Kn−r ). Since P (Kn−r )
is convex and integral, we may assume that x is integral. Rewriting i = n−(n−i)
for i = 1, . . . , r and applying the assumption that x is an integral knapsack
solution, the proposition follows.
In terms of facets, we shall focus on a family of facets introduced in [1]. Before
stating the theorem, we note that for any non-trivial knapsack facet, by taking
an appropriate linear combination with the knapsack equation, we may assume
the following:
Proposition 2. Let (ρ, ρ0 ) be a non-trivial facet of P (Km ). Without loss of
generality we may assume that (ρ, ρ0 ) ≥ 0, ρ0 = ρm = 1. Moreover, we may
assume there exists some i = m such that ρi = 0.
Theorem 2 (Aráoz et. al. [1]). Let (ρ, ρr ) be a non-trivial facet of P (Kr )
such that ρ ≥ 0, ρi = 0 for at least one i, and ρr = 1. Let
n−r−1 1
ρ = ρ1 , . . . , ρr = 1, ,..., .
n−r n−r
A Polyhedral Study of the Mixed Integer Cut 127
Proof. We argue for facets tilted from P (Kr ); an analogous argument proves the
result for facets tilted from P (Kn−r ).
Let (π, π0 ) be tilted from (ρ, 1), and let ρ be as described in Theorem 2 and
α be the corresponding tilting coefficient. Since (ρ, 1) is a facet of P (Kr ), there
exist r − 1 affinely independent extreme points x1 , . . . , xr−1 satisfying (ρ, 1)
at equality. As described in Proposition 1, these points may be extended to
points t1 , . . . , tr−1 ∈ PMIC (n, r), and clearly this preserves affine independence.
Moreover, for i = 1, . . . , r − 1, μti = 1 and ρti = ρx = 1, thus
Consider a tilted knapsack facet (π, π0 ) arising from the facet (ρ, 1) of P (Kr )
with tilting coefficient α. Letting μ denote first r coefficients of μ, the same
facet of P (Kr ) is described by (γ, 0) = (ρ, 1) − (μ , 1). In particular letting,
it follows that (π, π0 ) = (γ̄, 0)+(1+α)(μ, 1). The same applies to tilted knapsack
facets arising from P (Kn−r ).
128 S. Tyber and E.L. Johnson
Proof. For convenience, say that P (Kr ) has non-trivial facets (ρ1 , 0), . . . , (ρM , 0)
and that P (Kn−r ) has non-trivial facets (γ 1 , 0), . . . , (γ N , 0). Let (ρ̄i , 0) and
(γ̄ i , 0) denote the tilted knapsack facets from (ρi , 0) and (γ i , 0) respectively.
We shall show that the system
min c · t
s.t. μ · t = 1
ρ̄i · t ≥ 0 i = 1, . . . M (2)
γ̄ i · t ≥ 0 i = 1, . . . N
t ≥0
attains an integer optimum that belongs to PMIC (n, r) for every c.
Let c = (c1 , . . . ,!cr ) and c = (cn−1 , . . . , cr ), μ = 1r , . . . , r−1
r , 1 , and μ =
1 n−r−1
n−r , . . . , n−r , 1 . Consider the systems
min c · x
s.t. μ · x = 1
(3)
ρi · x ≥ 0 i = 1, . . . M
x ≥0
and
min c · x
s.t. μ · x = 1
(4)
γ i · x ≥ 0 i = 1, . . . N
x ≥0
representing P (Kr ) and P (Kn−r ) respectively. Since both systems are integral,
the minima are obtained at integer extreme points x0 and x 1 respectively. Now
∗
let t be obtained by extending the solution achieving the smaller objective value
to a feasible point of PMIC (n, r). Indeed this t∗ is feasible and integral; it remains
to show that it is optimal.
We now consider the duals. The dual of (3) is given by
11 , α0 ) and (λ
Let (λ 12 , β0 ) attain the maxima in (5) and (6) respectively. Setting
0 1 1
λ = min(λ1 , λ2 ), it easily follows from the zero pattern of (2) and non-negativity
of μ that (λ, 0 α0 , β0 ) is feasible to (7). Moreover λ
0 = c · t∗ , proving optimality.
Further observe that PMIC (n, r) is pointed, and so from this same proof we get
the following characterization of extreme points:
Theorem 4. A point t is an extreme point of PMIC (n, r) if and only if it can
be obtained by extending an extreme point of P (Kr ) or P (Kn−r ).
1 r−1 n−r−1 1
t1 + · · · + tr−1 + tr + tr+1 + · · · + tn−1 = 1
r r n−r n−r
or
" #
1 r−1 n−r−1 1
t1 + · · · + tr−1 + tr = 1 − tr+1 + · · · + tn−1 . (9)
r r n−r n−r
130 S. Tyber and E.L. Johnson
! !
⇒ r+1
r − n−r−1
n−r t r+1 + · · · + n−1
r − 1
n−r tn−1 = β r
n
⇒ n
r · n−r tr+1 + · · · + r · n−r tn−1
1 n n−r−1
= β nr
⇒ n−r tr+1 + · · · + n−r tn−1 =
1 n−r−1
β
" #
n−r−1 1
⇒ [tr+1 + · · · + tn−1 ] − tr+1 + · · · + tn−1 = β.
2 34 5 n−r n−r
(∗) 2 34 5
(∗∗)
implies that (∗∗) must be fractional. But this contradicts that β is integral.
Therefore (I) and (II) cannot simultaneously hold.
Here we review some general properties of facets of the master group polyhedra
and discuss extensions of our previous results. Throughout, some basic knowledge
of algebra is assumed.
Let G be an abelian group with identity 0, G+ = G \ 0, and g0 ∈ G+ . The
master group polyhedron, P (G, g0 ) is defined by
⎧ ⎫
⎨ ⎬
|G|−1
P (G, g0 ) = conv t ∈ Z+ : gt(g) = g0 .
⎩ ⎭
g∈G+
Because |G|g = 0 for all g ∈ G+ , the recession cone of P (G, g0 ) is the non-negative
orthant, and since P (G, g0 ) is nonempty, the polyhedron is of full dimension.
As before, let (π, π0 ) denote the inequality
π(g)t(g) ≥ π0 .
g∈G+
If |G| − 1 ≥ 2, then the inequality t(g) ≥ 0 is facet defining for all g ∈ G+ , and
it is easily verified that these are the only facets with π0 = 0. Likewise, we call
these the trivial facets of P (G+ , g0 ).
A Polyhedral Study of the Mixed Integer Cut 131
4.1 Automorphisms
Proof. Since (γ, γ0 ) and (π, π0 ) define adjacent facets, there exist affinely in-
dependent points t1 , . . . , t(|G|−2) satisfying both at equality. By the previous
remarks, we may define points (t1 ) , . . . , (t(|G|−2) ) satisfying both (π , π0 ) and
(γ , γ0 ) at equality. Since these are all defined by the same permutation of the
indices of t1 , . . . , t(|G|−2) , affine independence is preserved.
4.2 Homomorphisms
– Set N = N \ N (i)
3. For each k ∈ K+ , define sk by sk = s1 + |G|ek
A Polyhedral Study of the Mixed Integer Cut 133
where the first equality comes from the fact that ψ is a homomorphism and the
second equality follows by how we defined the above points. Therefore,
gs(g) ∈ g0 K,
g∈G+ \K
and by construction,
⎛ ⎞
ks(k) = g0 − ⎝ gs(g)⎠ .
k∈K g∈G+ \K
Thus s ∈ P (G, g0 ).
Note that we have the |H| − 2 points s1 , . . . , s|H|−2 . By Proposition 5, we
obtain (|H| − 1)(|K| − 1) points of the form sk,h for k ∈ K+ and h ∈ H+ , and
lastly, we obtain |K| − 1 points, sk for k ∈ K+ . Using the identity |G| = |K||H|,
it immediately follows that we have |G| − 2 points.
The affine independence of these points is easily verified. By constructing a
matrix for which the first |K| − 1 columns correspond to K, the next |H| − 1
columns corresponding to ϕ(H), and the remaining columns are arranged in
blocks by the cosets, it is readily observed by letting each row be one of the
above points and using the affine independence of t1 , . . . , t|H|−2 that the newly
defined points are affinely independent.
Given a point s ∈ P (G, g0 ) that satisfies the lifted facets at equality, we can
obtain a point t ∈P (H, h0 ) that satisfies (π, π0 ) and (γ, γ0 ) at equality under the
mapping t(h) = g∈G:ψ(g)=h s(g). By a fairly routine exercise in linear algebra,
one can use this to verify that s is in the affine hull of the points described above.
Hence we obtain the following theorem:
Theorem 10. Let (π, π0 ) and (γ, γ0 ) be non-trivial facets of P (H, h0 ), and let
(π , π0 ) and (γ , γ0 ) be facets of P (G, g0 ) obtained by homomorphic lifting using
the homomorphism ψ. Then (π , π0 ) and (γ , γ0 ) are adjacent if and only if (π, π0 )
and (γ, γ0 ) are adjacent.
Now consider G = Cn , g0 = r , a homomorphism ψ : Cn → Cn , ψ(r ) = r = 0,
and let (μ , 1) be obtained by applying homomorphic lifting to (μ, 1). Similarly
by applying Theorem 10, we know that the only lifted facets under ψ that are
adjacent to (μ , 1) come from tilted knapsack facets. Stated precisely:
134 S. Tyber and E.L. Johnson
References
1. Aráoz, J., Evans, L., Gomory, R.E., Johnson, E.L.: Cyclic group and knapsack facets.
Math. Program. 96(2), 377–408 (2003)
2. Dash, S., Günlük, O.: On the strength of gomory mixed-integer cuts as group cuts.
Math. Program. 115(2), 387–407 (2008)
3. Gomory, R.E.: Some polyhedra related to combinatorial problems. Linear Algebra
and Its Applications (2), 451–558 (1969)
4. Gomory, R.E., Johnson, E.L., Evans, L.: Corner polyhedra and their connection
with cutting planes. Math. Program. 96(2), 321–339 (2003)
Symmetry Matters for the Sizes of Extended
Formulations
1 Introduction
Linear Programming techniques have proven to be extremely fruitful for com-
binatorial optimization problems with respect to both structural analysis and
the design of algorithms. In this context, the paradigm is to represent the prob-
lem by a polytope P ⊆ Rm whose vertices correspond to the feasible solutions
of the problem in such a way that the objective function can be expressed by
a linear functional x %→ "c, x# on Rm (with some c ∈ Rm ). If one succeeds in
finding a description of P by means of linear constraints, then algorithms as
well as structural results from Linear Programming can be exploited. In many
cases, however, the polytope P has exponentially (in m) many facets, thus P
can only be described by exponentially many inequalities. Also it may be that
the inequalities needed to describe P are too complicated to be identified.
In some of these cases one may find an extended formulation for P , i.e., a
(preferably small and simple) description by linear constraints of another poly-
hedron Q ⊆ Rd in some higher dimensional space that projects to P via some
(simple) linear map p : Rd → Rm with p(y) = T y for all y ∈ Rd (and some
matrix T ∈ Rm×d ). Indeed, if p : Rm → Rd with p (x) = T t x for all x ∈ Rm
denotes the linear map that is adjoint to p (with respect to the standard bases),
then we have max{"c, x# : x ∈ P } = max{"p (c), y# : y ∈ Q}.
F. Eisenbrand and B. Shepherd (Eds.): IPCO 2010, LNCS 6080, pp. 135–148, 2010.
c Springer-Verlag Berlin Heidelberg 2010
136 V. Kaibel, K. Pashkovich, and D.O. Theis
As for an example, let us consider the spanning tree polytope Pspt (n) =
conv{χ(T ) ∈ {0, 1}En : T ⊆ En spanning tree of Kn }, where Kn = ([n], En )
denotes the complete graph with node set [n] = {1, . . . , n} and edge set En =
{{v, w} : v, w ∈ [n], v = w}, and χ(A) ∈ {0, 1}B is the characteristic vector of
the subset A ⊆ B of B, i.e., for all b ∈ B, we have χ(A)b = 1 if and only if b ∈ A.
Thus, Pspt (n) is the polytope associated with the bases of the graphical matroid
of Kn , and hence (see [7]), it consists of all x ∈ RE + satisfying x(En ) = n − 1
n
and x(En (S)) ≤ |S| − 1 for all ⊆ [n] with 2 ≤ |S| ≤ n − 1, where RE + is the
nonnegative orthant of R E
, we denote by En (S) the subset of all edges with both
nodes in S, and x(F ) = e∈F xe for F ⊆ En . This linear description of Pspt (n)
has an exponential (in n) number of constraints, and as all the inequalities define
pairwise disjoint facets, none of them is redundant.
The following much smaller exended formulation for Pspt (n) (with O(n3 ) vari-
ables and constraints) appears in [5] (and a similar one in [17], who attributes
it to [13]). Let us introduce additional 0/1-variables ze,v,u for all e ∈ En , v ∈ e,
and u ∈ [n] \ e. While each spanning tree T ⊆ En is represented by its char-
acteristic vector x(T ) = χ(T ) in Pspt (n), in the extended formulation it will be
(T )
represented by the vector y (T ) = (x(T ) , z (T ) ) with ze,v,u = 1 (for e ∈ En , v ∈ e,
u ∈ [n] \ e) if and only if e ∈ T and u is contained in the component of v in T \ e.
The polyhedron Qspt (n) ⊆ Rd defined by the nonnegativity constraints x ≥ 0,
z ≥ 0, the equations x(En ) = n − 1, x{v,w} − z{v,w},v,u − z{v,w},w,u = 0 for all
pairwise distinct v, w, u ∈ [n], as well as x{v,w} + u∈[n]\{v,w} z{v,u},u,w = 1 for
all distinct v, w ∈ [n], satisfies p(Qspt (n)) = Pspt (n), where p : Rd → RE is the
orthogonal projection onto the x-variables.
For many other polytopes (with exponentially many facets) associated with
polynomial time solvable combinatorial optimization problems polynomially sized
extended formulations can be constructed as well (see, e.g., the recent survey [5]).
Probably the most prominent problem in this class for which, however, no such
small formulation is known, is the matching problem. In fact, Yannakakis [17]
proved that no symmetric polynomially sized extended formulation of the match-
ing polytope exists.
Here, symmetric refers to the symmetric group S(n) of all permutations
π : [n] → [n] of the node set [n] of Kn acting on En via π.{v, w} = {π(v), π(w)}
for all π ∈ S(n) and {v, w} ∈ En . Clearly, this action of S(n) on En induces
an action on the set of all subsets of En . For instance, this yields an action
on the spanning trees of Kn , and thus, on the vertices of Pspt (n). The ex-
tended formulation of Pspt (n) discussed above is symmetric in the sense that,
for every π ∈ S(n), replacing all indices associated with edges e ∈ En and
nodes v ∈ [n] by π.e and π.v, respectively, does not change the set of constraints
in the formulation. Phrased informally, all subsets of nodes of Kn of equal cardi-
nality play the same role in the formulation. For a general definition of symmetric
extended formulations see Section 2.
In order to describe the main results of Yannakakis paper [17] and the
contributions of the present paper, let us denote by M (n) = {M ⊆ En :
M matching in Kn , |M | = } the set of all matchings of size (a matching
Symmetry Matters for the Sizes of Extended Formulations 137
being a subset of edges no two of which share a node), and by Pmatch (n) =
conv{χ(M ) ∈ {0, 1}En : M ∈ M (n)} the associated polytope. According to
n/2
Edmonds [6] the perfect matching polytope Pmatch (n) (for even n) is described
by
n/2
Pmatch (n) = {x ∈ RE
+ : x(δ(v)) = 1 for all v ∈ [n],
n
(with δ(v) = {e ∈ En : v ∈ e}). Yannakakis [17, Thm.1 and its proof] shows that
n/2
there is a constant C > 0 such that, for every extended formulation for Pmatch (n)
(with n even) that is symmetric
n in the sense above, the number of variables and
constraints is at least C · n/4 = 2Ω(n) . This in particular implies that there is
no polynomial size symmetric extended formulation for the matching polytope
of Kn (the convex hulls of characteristic vectors of all matchings in Kn ), of which
the perfect matching polytope is a face.
Yannakakis [17] also obtains a similar (maybe less surprising) result on travel-
ing salesman polytopes. Denoting the set of all (simple) cycles of length in Kn
by C (n) = {C ⊆ En : C cycle in Kn , |C| = }, and the associated polytopes by
Pcycl (n) = conv{χ(C) ∈ {0, 1}En : C ∈ C (n)}, the traveling salesman polytope
n/2
is Pncycl (n). Identifying Pmatch (n) (for even n) with a suitable face of P3n
cycl (3n),
Yannakakis concludes that all symmetric extended formulations for Pncycl (n) have
size at least 2Ω(n) as well [17, Thm. 2 and its proof].
Yannakakis’ results in a fascinating way illuminate the borders of our principal
abilities to express combinatorial optimization problems like the matching or the
traveling salesman problem by means of linear constraints. However, they only
refer to linear descriptions that respect the inherent symmetries in the problems.
In fact, the second open problem mentioned in the concluding section of [17] is
described as follows: “We do not think that asymmetry helps much. Thus, prove
that the matching and TSP polytopes cannot be expressed by polynomial size
LP’s without the asymmetry assumption.”
The contribution of our paper is to show that, in contrast to the assumption
expressed in the quotation above, asymmetry can help much, or, phrased differ-
ently, that symmetry requirements on extended formulations indeed can matter
significantly with respect to the minimal sizes of extended formulations. Our
log n log n
main results are that both Pmatch (n) and Pcycl (n) do not admit symmetric
extended formulations of polynomial size, while they have non-symmetric ex-
tended formulations of polynomial size (see Cor. 1 and 2 for matchings, as well as
Cor. 3 and 4 for cycles). The corresponding theorems from which these corollar-
ies are derived provide some more general and more precise results for Pmatch (n)
and Pcycl(n). In order to establish the lower bounds for symmetric extensions,
we generalize the techniques developed by Yannakakis [17]. The constructions
of the compact non-symmetric extended formulations rely on small families of
perfect hash functions [1,8,15].
The paper is organized as follows. In Section 2, we provide definitions of
extensions, extended formulations, their sizes, the crucial notion of a section
138 V. Kaibel, K. Pashkovich, and D.O. Theis
3 Yannakakis’ Method
Here, we provide an abstract view on the method used by Yannakakis [17] in or-
der to bound from below the sizes of symmetric extensions for perfect matching
polytopes, without referring to these concrete poytopes. That method is capable
of establishing lower bounds on the number of variables of weakly symmetric
subspace extensions of certain polytopes. By the following lemma, which is ba-
sically Step 1 in the proof of [17, Theorem 1], such bounds imply similar lower
bounds on the dimension of the ambient space and the number of facets for
general symmetric extensions (that are not necessarily subspace extensions).
Due to Lemma 5 one can prove that subspace extensions of some polytope P
with certain properties do not exist by finding, for such a hypothetical extension,
Symmetry Matters for the Sizes of Extended Formulations 141
(π.sj )(x) = sκ−1 (j) (x) = (κπ−1 .s(x))j = sj (π −1 .x) for all x ∈ X , (6)
π −1
from which one deduces 1.sj = sj for the one-element 1 in G as well as (ππ ).sj =
π.(π .sj ) for all π, π ∈ G. The isotropy group of sj ∈ S under this action is
isoG (sj ) = {π ∈ G : π.sj = sj }. From (6) one sees that, for all x ∈ X and
142 V. Kaibel, K. Pashkovich, and D.O. Theis
Proof. For odd , this follows from Theorem 1 using Lemmas 1, 2, and 4. For
match (n − 2) is (isomorphic to) a face of Pmatch (n) defined
even , the polytope P−1 −1
implies (7). Thus, for each j ∈ [d], the equivalence classes of the equivalence
relation defined by (8) refine the partitioning of X into orbits under Hj , and
we may use the collection of all these equivalence classes (for all j ∈ [d]) as the
family F in Remark 1. With
face the inequality x(V : V ) ≥ 1 is valid (where (V : V ) is the set of all edges
having one node in V and the other one in V ), since every matching M ∈ M
intersects (V : V ) in an odd number of edges. Therefore, in order to derive the
it suffices to find cx ∈ R (for all x ∈
desired
contradiction, X ) with
x∈X cx = 1, x∈X cx · 1F (x) ≥ 0F , and x∈X cx e∈(V :V ) xe = 0. For
the details on how this can be done we refer to [12].
−1
Pi = {x ∈ RE
+ : xE\Ei = 0, x(δ(φi (s))) = 1 for all s ∈ [2],
x(Ei (φ−1
i (S))) ≤ (|S| − 1)/2 for all S ⊆ [2], |S| odd} ,
/
where Ei = E \ j∈[2] E(φ−1
i (j)). This follows by Lemma 11 from Edmonds’
linear description (1) of the perfect matching polytope Pmatch (2) of K2 . As the
sum of the number of variables and the number of inequalities in the description
of Pi is at most 2O() + n2 (the summand n2 comes from the nonnegativity
constraints on x ∈ RE+ and the constant in O() is independent of i), we obtain an
extension of Pmatch (n) of size 2O() n2 log n by Lemma 10. This proves Theorem 3.