Network Formulations of Mixed-Integer Programs

(1)

Network Formulations of Mixed-Integer Programs

^∗

Michele Conforti^† Marco Di Summa^† Friedrich Eisenbrand^‡ Laurence A. Wolsey^§

June 3, 2008

Abstract

We consider mixed-integer sets of the type M IX^{T U} = {x : Ax ≥ b; xi integer, i ∈ I}, where A is a totally unimodular matrix, b is an arbitrary vector and I is a nonempty subset of the column indices of A. We show that the problem of checking nonemptiness of a set M IX^{T U}is NP-complete even in the case in which the system describes mixed-integer network flows with half-integral requirements on the nodes.

This is in contrast to the case where A is totally unimodular and contains at most two nonzeros per row. Denoting such mixed-integer sets by M IX^{2T U}, we provide an extended formulation for the convex hull of M IX^{2T U} whose constraint matrix is a dual network matrix with an integral right-hand-side vector. The size of this formulation depends on the number of distinct fractional parts taken by the continuous variables in the extreme points of conv(M IX^{2T U}). When this number is polynomial in the dimension of the matrix A, the extended formulation is of polynomial size. If, in addition, the corresponding list of fractional parts can be computed efficiently, then our result provides a polynomial algorithm for the optimization problem over M IX^{2T U}. We show that there are instances for which this list is of exponential size, and we also give conditions under which it is short and can be efficiently computed.

Finally we show that these results for the set M IX^{2T U} provide a unified framework leading to polynomial-size extended formulations for several generalizations of mixing sets and lot-sizing sets studied in the last few years.

1 Introduction

We study mixed-integer sets of the type

M IX^{T U} = {x : Ax ≥ b; x_i integer, i ∈ I},

where A is a totally unimodular (TU, for short) matrix, b is a vector that typically contains fractional components and I is a nonempty subset of the column indices of A. (Definitions

∗This work was partly carried out within the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract no. MRTN-CT-2003-504438.

†Dipartimento di Matematica Pura ed Applicata, Universit`a degli Studi di Padova. Via Trieste 63, 35121 Padova, Italy ([email protected], [email protected]).

‡Department of Mathematics, Paderborn University. Warburger Str. 100, D-33098, Paderborn, Germany ([email protected]).

§Center of Operations Research and Econometrics (CORE), Universit´e catholique de Louvain. 34, Voie du Roman Pays, 1348 Louvain-la-Neuve, Belgium ([email protected]).

(2)

and properties of TU matrices can be found in [14].) The study of such sets forms part of a recent effort to study and understand simple mixed-integer sets. In particular M IX^{T U} includes as a special case the mixing set

M IX = {(s, y) ∈ R₊× Zⁿ: s + y_j ≥ b_j, j = 1, . . . , n}, as well as the more general mixed-integer edge-covering problem

BIP (I) = {x ∈ R^V₊ : x_i+ x_j ≥ b_ij, ij ∈ E; x_i integer, i ∈ I}

on a bipartite graph G = (V, E) with I ⊆ V .

More specifically the motivation for this research was in part to understand the full scope of the proof technique based on fractionalities used in studying the mixing set and its generalizations [2, 3, 5, 18, 9, 13, 16], and also to see whether TU matrices play as important a role in mixed-integer programming as they do in pure integer programming.

From the complexity and polyhedral point of view our results are of two types. On the one hand we show that checking nonemptiness of M IX^{T U} is NP-complete, even if the system is of the form {x : Ax = b; x ≥ 0; x_i integer, i ∈ I} with A being the node-arc incidence matrix of a directed graph and b is half-integral, i.e., 2b is integral. This shows that finding an explicit inequality description of the polyhedron conv(M IX^{T U}) will most likely be an elusive task, where conv(M IX^{T U}) denotes the convex hull of the set M IX^{T U}.

On the other hand, if M IX^{2T U} denotes the mixed-integer set M IX^{T U} with the additional restriction that A is a TU matrix with at most two nonzero entries per row, which includes the sets M IX and BIP (I), we derive an extended formulation for the convex hull of M IX^{2T U}, i.e. an inequality description of a polyhedron Q = {(x, µ) : Ax + Bµ ≥ d} in a space that uses variables (x, µ) and includes the original x-space, so that conv(M IX^{2T U}) is the projection of Q onto the x-space.

The extended formulation of the polyhedron conv(M IX^{2T U}) takes explicitly into account all possible fractional parts taken by the continuous variables at the vertices of conv(M IX^{2T U}).

If the number of these fractional parts is small, this extended formulation is compact (of poly- nomial size in n, A, b). In such cases optimizing a linear function over sets M IX^{2T U} that have this property can be carried out efficiently through linear programming if the set of fractional parts is known. On the one hand we give conditions, including many interesting cases, in which this formulation is compact and the fractional parts can be computed. On the other, we show that for sets such as BIP (I) the size of our polyhedral description can be exponential.

Also using invertible linear transformations that map mixed-integer vectors into mixed- integer vectors, we show that a host of mixed-integer sets that have been investigated in the past decade can be mapped with these transformations into sets of the type M IX^{2T U} with a small number of fractional parts taken by the continuous variables. Therefore our result provides a general setting for the compact extended formulations of all these mixed-integer sets.

The outline of the paper is as follows. In Section 2 we remind the reader of some basic results on network matrices. In Section 3 we show that deciding the nonemptiness of sets M IX^{T U} is NP-complete. In Sections 4 and 5 we derive the extended formulation for conv(M IX^{2T U}). In Section 6 we show first that the length of the list of fractional values of all the extreme point solutions can be exponential, and then describe conditions under which

(3)

the length is of polynomial size (compact). In Section 7 we give examples of mixed-integer sets that can be transformed into the form M IX^{2T U}, and we finish in Section 8 with some concluding remarks.

2 Dual network matrices

Our main result is an extended formulation of mixed-integer sets M IX^{2T U}, which are defined by totally unimodular matrices A having at most two nonzero entries per row. In this section, we review some basic terminology of networks and relate such TU matrices to transposes of node-arc incidence matrices of directed graphs.

The node-arc incidence matrix C ∈ {0, ±1}^{V ×A} of a directed graph D = (V, A) has one row for each vertex and one column for each arc of D. The column representing the arc e = uv is zero everywhere, except in the rows corresponding to u and v. These entries are C(u, e) = 1 and C(v, e) = −1 respectively. A minimum cost flow problem is a linear program of the form min{c^Tx : Cx = b, 0 ≤ x ≤ u}, where C ∈ {0, ±1}^m×n is a node-arc incidence matrix, c and u are in Rⁿ.

A 0, ±1-matrix A with at most two nonzero entries per row is a dual network matrix if A has the following property:

If a_ij, a_ik are both nonzero and k 6= j, then a_ij = −a_ik.

Consequently a dual network matrix is the transpose of a node-arc incidence matrix plus some singleton rows with entries of +1 or −1, and such matrices arise as the constraint matrices of the linear-programming dual of a minimum cost flow problem without capacities. The problem of optimizing over such matrices is often referred to as the optimal node-potential or node-label assignment problem, see e.g. [1].

The following characterization is due to Heller and Tompkins [10], see e.g. Theorem 2.8 in [14]. Here N = {1, . . . , n} and {a_j, j ∈ N } denotes the set of columns of A.

Theorem 1 Let A be a 0, ±1-matrix with at most two nonzero entries per row. Then A is totally unimodular if and only if the set N can be partitioned into two sets R and B such that all entries of the vector P

j∈Ra_j−P

j∈Ba_j are 0, ±1.

Here, we focus on mixed-integer systems defined by TU matrices which have at most two nonzero entries per row. The next corollary shows that we can restrict our attention to dual network matrices by substituting some variables x_i by −x_i.

Corollary 2 Let A be a 0, ±1-matrix with at most two nonzero entries per row. Then A is totally unimodular if and only if N contains a subset R such that the matrix eA, obtained from A by multiplying the columns a_j, j ∈ R by −1, is a dual network matrix.

Proof: Let (R, B) be a partition of the column indices of A satisfying the condition of Theo- rem 1. Then eA is a dual network matrix. The converse is readily checked. 2

3 Complexity of the feasibility problem for M IX

^{T U}

In this section, we show that determining whether a mixed-integer set of the type M IX^{T U} is empty or not is NP-complete. More specifically, we show that feasibility of a half-integer version of the minimum cost flow problem is NP-complete.

(4)

Consider a mixed-integer set

{x : Cx = b/2; x ≥ 0; x_i integer, i ∈ I}, (1) where C is the node-arc incidence matrix of a directed graph D = (V, A) and b ∈ Z^V is an integral vector, which represents the requirements on the vertices of D. The set (1) is nonempty if and only if the following set is nonempty

{x : Cx = b; x ∈ Z₊; x_i even, i ∈ I}. (2) This can be seen as follows. Let x be a vertex of the convex hull of (1). Then x_i is integer for each i ∈ I and x_j is half-integer, i.e. 2x_j ∈ Z for each j ∈ N \ I. Consequently 2 · x is in the set (2). On the other hand, if x⁰ is in the set (2), then x⁰/2 lies in the set (1). This discussion shows that we can decide whether the following parity network flow problem has a solution, given an algorithm which decides whether a mixed-integer set of type M IX^{T U} is feasible or not.

(Parity network flow) Given a directed graph D = (V, A), a subset S ⊆ A of the arcs and integral vectors b ∈ Z^V, u ∈ Z^A, determine whether the network D with requirements b and capacities u has a feasible integral flow under the additional requirement that all flow-values of arcs in S are even.

Theorem 3 The problem of deciding the nonemptiness of a mixed-integer set M IX^{T U} is NP-complete, even if the set has the form (1).

Proof: The problem is clearly in NP. We reduce SAT to the parity network flow problem in a manner similar to that introduced by Even et al. in the proof that the edge-disjoint paths problem is NP-hard, see [7] and [12, p. 432].

Given a SAT formula over the variables x₁, . . . , x_n, consisting of clauses Z₁, . . . , Z_m, we construct an instance of the parity network flow problem as follows.

• The set V of nodes of D contains a source s, a sink t and a node z_j, 1 ≤ j ≤ m, that represents the corresponding clause.

Every variable x_i appearing in positive or negative form in clauses Z_i₁, . . . , Z_i_pi is rep- resented by a “value node” v_i and nodes xⁱⁿ_i,i_`, x^out_i,i_`, ¯xⁱⁿ_i,i_`, ¯x^out_i,i_`, 1 ≤ ` ≤ p_i.

Finally there is an additional value node v_n+1.

• The arcs of D that are not in the set S (unspecified capacities are unlimited) are:

– The arcs sxⁱⁿ_i,i_`, s¯xⁱⁿ_i,i_`, 1 ≤ i ≤ n, 1 ≤ ` ≤ p_i. – The arcs z_jt, 1 ≤ j ≤ m, having capacity 1.

– The arcs xⁱⁿ_i,i_`x^out_i,i_` and ¯xⁱⁿ_i,i_`x¯^out_i,i_`, 1 ≤ i ≤ n, 1 ≤ ` ≤ p_i, having capacity 2.

– If variable x_i occurs as a positive literal in clause Z_i_`, there is an arc x^out_i,i_`z_i_`. If variable x_i occurs as a negative literal in clause Z_i_`, there is an arc ¯x^out_i,i_`z_i_`.

• The following are the arcs in S and thus have to carry a flow of even value:

– The arcs v_ixⁱⁿ_i,i₁ and v_ix¯ⁱⁿ_i,i₁, 1 ≤ i ≤ n.

– The arcs x^out_i,i

piv_i+1 and ¯x^out_i,i

piv_i+1 , 1 ≤ i ≤ n.

(5)

x₃₂ⁱⁿ

z₁ z₂

x₃₂^out x₂₂^out

x₂₂ⁱⁿ x₂₁^out

x₂₁ⁱⁿ x₁₁^out

x₁₁ⁱⁿ

x32^out

_ x22^out

_ x21^out

_ x11^out

_

x32ⁱⁿ

_ x22ⁱⁿ

_ x21ⁱⁿ

_ x11ⁱⁿ

_

v v

v

v₁ ₂ ₃ ₄

s

2

2 2

2

2 2

2

1 1

2 t

Figure 1: The network corresponding to the SAT formula (x₁∨ ¯x₂) ∧ (x₂∨ x₃). Thick arcs are special arcs. Numbers on arcs are capacities.

– The arcs x^out_i,i_`xⁱⁿ_i,i_`+1 and ¯x^out_i,i_`x¯ⁱⁿ_i,i_`+1, 1 ≤ i ≤ n, 1 ≤ ` < p_i.

• The requirements on the nodes are:

– An in-flow of value m in the source s and an out-flow of value m in the sink t.

– An in-flow of value 2 at v₁ and an out-flow of value 2 at v_n+1.

Figure 1 shows the network relative to the SAT formula (x₁∨ ¯x₂) ∧ (x₂∨ x₃).

For 1 ≤ i ≤ n, define the upper path P_i^U to be v_i, xⁱⁿ_i,i₁, x^out_i,i₁, . . . , xⁱⁿ_i,i

pi, x^out_i,i

pi, v_i+1 and the lower path P_i^L to be v_i, ¯xⁱⁿ_i,i₁, ¯x^out_i,i₁, . . . , ¯xⁱⁿ_i,i

pi, ¯x^out_i,i

pi, v_i+1.

Observe that the arcs in S force any feasible circulation F to satisfy the following condi- tions:

• For every 1 ≤ i ≤ n, the arcs in S of one among P_i^U and P_i^L carry a flow of value 2, and the special arcs of the other carry a flow of value 0.

• For every 1 ≤ j ≤ m, F carries a flow of value 1 along a path of the type s, xⁱⁿ_i,j, xôut_i,j, z_j, t and the upper path P_iÛ is discharged (that is, its arcs in S carry a flow of value 0), or a flow of value 1 along a path of the type s, ¯xⁱⁿ_i,j, ¯xôut_i,j , z_j, t and the lower path P_i^L is discharged.

(6)

To any truth assignment T that satisfies the SAT-formula, we assign a flow value of 2 to P_i^L if x_i = true in T and a flow value of 2 to P_iÛ if x_i = f alse in T . For each clause Z_j we choose any literal x_i or ¯x_i which is true under T . Say x_i occurs as a positive literal in Z_j and x_i = true in T . Then P_iÛ is discharged and a flow of value 1 can be routed along s, xⁱⁿ_i,j, xôut_i,j , z_j, t.

It is immediate to see that the converse also holds: to any feasible circulation, a truth assignment that satisfies all clauses can be derived in the above manner. 2

4 The main result

Given a real number α, let f (α) = α − bαc denote its fractional part. Let F = {f₁, f₂, . . . , f_k} be an arbitrary list of decreasing fractional parts (that is, 1 > f₁ > · · · > f_k ≥ 0), K = {1, . . . , k} be its set of indices and N = {1, . . . , n}. Later we will make specific choices for these values. Let X^F be the set of points x ∈ Rⁿ such that there exist µⁱ, δⁱ_`, i ∈ N, ` ∈ K, satisfying the following constraints:

x_i= µⁱ+P_k

`=1f_`δ_`ⁱ, i ∈ N (3)

P_k

`=1δ_`ⁱ = 1, δⁱ_`≥ 0, i ∈ N, ` ∈ K (4)

x_i− x_j ≥ l_ij, (i, j) ∈ N^e (5)

x_i ≥ l_i, i ∈ N^l (6)

x_i≤ u_i, i ∈ N^u (7)

µⁱ integer, δ_`ⁱ integer, i ∈ N, ` ∈ K, (8) where N^e⊆ N ×N and N^l, N^u ⊆ N . In other words, X^F is the projection onto the x-space of the mixed-integer set (3)–(8). We remark that the above system may also include constraints of the type x_i− x_j ≤ u_ij, as this inequality is equivalent to x_j − x_i ≥ l_ij for l_ij = −u_ij. In this section we give an extended formulation for the polyhedron conv(X^F).

Consider the following unimodular transformation:

µⁱ₀ = µⁱ, µⁱ_` = µⁱ+ X` j=1

δⁱ_j, i ∈ N, ` ∈ K. (9)

Define f₀ = 1 and f_k+1= 0. For fixed i ∈ N , an equation in (3) becomes:

x_i = Xk

`=0

µⁱ_`(f_`− f_`+1) (10)

and the inequalities in (4) become:

µⁱ_k− µⁱ₀ = 1, µⁱ_`− µⁱ_`−1 ≥ 0, ` ∈ K. (11) 4.1 Modeling xi ≥ li, xi ≤ ui and xi − xj ≥ lij

Let `_l_i be the highest index ` ∈ {0, . . . , k} such that f_` ≥ f (l_i). Now if x_i, δ_`ⁱ, µⁱ_` satisfy (3), (4), (8), (9), then x_i≥ l_i if and only if

µⁱ_`

li ≥ bl_ic + 1. (12)

(7)

Similarly if `_u_i is the highest index such that f_` > f (u_i), then constraint x_i ≤ u_i is satisfied if and only if

µⁱ_`

ui ≤ bu_ic . (13)

Now we consider the constraint x_i− x_j ≥ l_ij. Define k_ij to be the highest index ` ∈ {0, . . . , k}

such that f_`+f (l_ij) ≥ 1. Given an index t ∈ K, define k_tto be the highest index ` ∈ {0, . . . , k}

such that f_`≥ f (f_t+ f (l_ij)).

Lemma 4 Assume x_i, x_j, δ_`ⁱ, δ_`^j, µⁱ_`, µ^j_` satisfy (3), (4), (8), (9). Then x_i− x_j ≥ l_ij if and only if the following set of inequalities is satisfied:

µⁱ_k_t− µ^j_t ≥ bl_ijc + 1, 1 ≤ t ≤ k_ij (14) µⁱ_k_t − µ^j_t ≥ bl_ijc , k_ij < t ≤ k. (15) Proof: Substituting for x_i and x_j, the inequality x_i− x_j ≥ l_ij becomes

µⁱ+ Xk

`=1

f_`δ_`ⁱ ≥ µ^j+ Xk

`=1

f_`δ_`^j+ bl_ijc + f (l_ij).

First we show that the inequality (15) is valid for t > k_ij. As P

`>ktf_`δ_`ⁱ ≤ f_k_t₊₁ and P_k

`=1f_`δ_`^j ≥P

`≤tf_`δ^j_` ≥ f_tP

`≤tδ_`^j, we obtain the valid inequality µⁱ+X

`≤kt

f_`δⁱ_`≥ µ^j+ f_tX

`≤t

δ^j_`+ bl_ijc + f (l_ij) − f_k_t₊₁.

Adding the valid inequality (1 − f_t) ≥ (1 − f_t)P

`≤tδ^j_` gives µⁱ+X

`≤kt

f_`δⁱ_`+ 1 − f_t≥ µ^j+X

`≤t

δ_`^j+ bl_ijc + f (l_ij) − f_k_t₊₁.

By definition f (l_ij) + f_t > f_k_t₊₁. Since δ_`ⁱ, δ^j_` ≥ 0 for all ` ∈ K, Chv´atal-Gomory rounding gives

µⁱ+X

`≤kt

δ_`ⁱ≥ µ^j+X

`≤t

δ^j_` + bl_ijc , or µⁱ_k_t ≥ µ^j_t+ bl_ijc .

The argument when t ≤ k_ij is the same, except that f (l_ij) − f_k_t₊₁+ f_t> 1.

To establish the converse, we consider the case in which δ_t^j = 1. Then µ^j_t = µ^j₀ + 1, µ^j_t−1= µ^j₀ and

x_j = µ^j₀+ Xk

`=1

(µ^j_`− µ^j_`−1)f_`= µ^j₀+ f_t.

Inequality µⁱ_k_t ≥ µ^j_t+ bl_ijc implies that either µⁱ₀ ≥ µ^j₀+ 1 + bl_ijc or that µⁱ₀ = µ^j₀+ bl_ijc and P

`≤ktδ_`ⁱ = 1. This implies that x_i≥ µ^j₀+ bl_ijc + f_k_t. Now, assuming t > k_ij, x_i− x_j ≥ µ^j₀+ bl_ijc + f_k_t− µ^j₀− f_t

= bl_ijc + f_k_t− f_t

≥ bl_ijc + f (l_ij),

as f_k_t ≥ f (f_t+ f (l_ij)) and f_t+ f (l_ij) < 1. Again the other case with t ≤ k_ij is similar. 2

(8)

4.2 Integrality of the extended formulation

Let Q^F be the polyhedron on the space of the variables {(x_i, µⁱ_`), i ∈ N, ` ∈ K ∪ {0}} defined by the inequalities

(10), (11), i ∈ N (12), i ∈ N^l (13), i ∈ N^u (14), (15), (i, j) ∈ N^e.

Theorem 5 The polyhedron conv(X^F) is the projection onto the space of the x-variables of the polyhedron Q^F.

Proof: Since, for i ∈ N , variable x_iis determined by the corresponding equation (10), we only need to show that the polyhedron defined by inequalities

(11), i ∈ N (12), i ∈ N^l (13), i ∈ N^u (14), (15), (i, j) ∈ N^e.

is integral. Let A_µbe the constraint matrix of the above system. By construction A_µis a dual network matrix. Since dual network matrices are totally unimodular and the right-hand-sides of the above inequalities are all integer, the statement follows from the theorem of Hoffman

and Kruskal [11]. 2

5 An extended formulation for conv(M IX

^{2T U}

)

Let X = {x : Ax ≥ b; x_i integer, i ∈ I} be a mixed-integer set, where (A | b) is a rational matrix and I is a nonempty subset of the column indices of A. A list F = {f₁ > f₂ > · · · > f_k} of fractional parts is complete for X if the following property is satisfied:

Every minimal face F of conv(X) contains a point ¯x such that for each i ∈ N , f (¯x_i) = f_j for some f_j ∈ F and for each i ∈ I, f (¯x_i) = 0.

In our applications, minimal faces are vertices and the above condition becomes:

If ¯x is a vertex of conv(X), then for each i ∈ N , f (¯x_i) = f_j for some f_j ∈ F.

Since I is nonempty, every complete list F must include the value 0, thus f_k= 0.

We now consider a mixed-integer set M IX^DN = {x : Ax ≥ b; x_i integer, i ∈ I}, where A is a dual network matrix. That is, the system Ax ≥ b is constituted by inequalities of the type (5)–(7). We assume that we are given a list F = {f₁> f₂> · · · > f_k} which is complete for M IX^DN. In order to obtain an extended formulation for conv(M IX^DN), we consider the

(9)

following mixed-integer set:

x_i= µⁱ+P_k

`=1f_`δⁱ_`, i ∈ N (16)

P_k

`=1δ_`ⁱ = 1, δ_`ⁱ ≥ 0, i ∈ N, ` ∈ K (17)

δ_`ⁱ = 0, i ∈ I, ` ∈ K \ {k} (18)

x_i− x_j ≥ l_ij, (i, j) ∈ N^e (19)

x_i≥ l_i, i ∈ N^l (20)

x_i≤ u_i, i ∈ N^u (21)

µⁱ integer, δ_`ⁱ integer, i ∈ N, ` ∈ K, (22) where inequalities (19)–(21) constitute the system Ax ≥ b.

Let M IX^F be the set of vectors x such that there exist µⁱ, δ_`ⁱ, i ∈ N, ` ∈ K satisfying the above constraints. Note that equations (18) force variables x_i, i ∈ I to be integer valued in M IX^F.

Lemma 6 conv(M IX^DN) = conv(M IX^F).

Proof: If ¯x ∈ M IX^F then ¯x satisfies the system Ax ≥ b (i.e. the inequalities (19)–(21)).

Furthermore equations (18) force x_i, i ∈ I to be integer. So ¯x ∈ M IX^DN. This shows M IX^F ⊆ M IX^DN and therefore conv(M IX^F) ⊆ conv(M IX^DN).

To prove the reverse inclusion, we show that all rays and minimal faces of conv(M IX^DN) belong to conv(M IX^F). If ¯x is a ray of conv(M IX^DN) then the vector defined by

x_i = ¯x_i, µ_i= ¯x_i, δ_`ⁱ= 0, i ∈ N, ` ∈ K

is a ray of the polyhedron which is the convex hull of the vectors satisfying (16)–(22). This implies that ¯x is a ray of conv(M IX^F).

Since the list F is complete, every minimal face F of conv(M IX^DN) contains a point

¯

x ∈ M IX^F. Furthermore F is an affine subspace which can be expressed as {x : x =

¯ x+P_h

t=1λ_tr_t, λ_t∈ R} for some subset of rays r₁, . . . , r_hof conv(M IX^DN). Since ¯x ∈ M IX^F and r₁, . . . , r_h are all rays of conv(M IX^F), then F ⊆ conv(M IX^F). 2 Applying the unimodular transformation (9), inequalities (16)–(17) become inequalities (10)–(11), while inequalities (19)–(21) become inequalities (12)–(15). Let Q be the polyhedron on the space of the variables {(x_i, µⁱ_`), i ∈ N, ` ∈ K ∪{0}} defined by the inequalities (10)–(15) corresponding to inequalities (16), (17), (19), (20), (21) under transformation (9) and let Q^I be the face of Q defined by equations

µⁱ_`− µⁱ_`−1 = 0, i ∈ I, ` ∈ K \ {k}, which are equivalent to equations (18) under transformation (9).

Theorem 7 The polyhedron conv(M IX^DN) is the projection onto the space of the x-variables of the face Q^I of Q.

Proof: Theorem 5 shows that every minimal face of Q contains a vector (¯x, ¯µ) with integral

¯

µ. So the same holds for Q^I, which is a face of Q. By applying the transformation which is the inverse of (9), this shows that every minimal face of the polyhedron defined by (16)–(21) contains a point (¯x, ¯µ, ¯δ) where (¯µ, ¯δ) is integral. So the projection of this polyhedron onto the x-space coincides with conv(M IX^F) and by Lemma 6 we are done. 2

(10)

We now consider a mixed-integer set M IX^{2T U} = {x : Ax ≥ b; x_i integer, i ∈ I}, where A is a TU matrix with at most two nonzero entries per row. By Corollary 2, A can be transformed into a dual network matrix by changing signs of some of its columns. Then M IX^{2T U} is transformed into a set of the type M IX^DN. Notice that if F = {f₁> · · · > f_k} is a list which is complete for M IX^{2T U}, then the list {0; f_`, 1 − f_`, 1 ≤ ` < k} is complete for the transformed set M IX^DN. Theorem 7 has the following implication:

If a mixed-integer set M IX^{2T U} admits a complete list F whose size is polynomial in the size of its description (given by the system Ax ≥ b), the extended formu- lation of the corresponding set M IX^DN given by the inequalities that define Q^I is compact. Therefore the problem of optimizing a linear function over such sets M IX^{2T U} can be solved in polynomial time provided that the list of fractionalities can be efficiently computed.

This implies the next corollary, since in this case a complete list of fractional parts is {0, 1/D, . . . , (D − 1)/D}:

Corollary 8 Let A ∈ {0, ±1} be a totally unimodular matrix, which has at most two nonzero entries per row, I ⊆ N , b ∈ Z^m, D ∈ Z₊\ {0} and c ∈ Rⁿ. The mixed-integer optimization problem

max{c^Tx : Ax ≥ (b/D); x_i integer, i ∈ I}

can be solved in time polynomial in m, n and D.

6 On the length of a complete list

In this section we first show that a complete list of fractional parts can have exponential length for a set of the type M IX^{2T U} and then describe conditions ensuring that the list (and thus the extended formulation) is compact.

6.1 A non-compact example We prove here the following result:

Theorem 9 In the set of vertices of the polyhedron Q defined by the inequalities σ_i+ r_j ≥ ³^(j−1)n+i

3ⁿ²⁺¹ , i, j ∈ N (23)

σ_i ≥ 0, r_j ≥ 0, i, j ∈ N (24)

the number of distinct fractional parts taken by variable σ_n is exponential in n.

Observation 1 Since the constraint matrix of inequalities (23)–(24) is a TU matrix with at most two nonzero entries per row, there exists a mixed-integer set M of the type M IX^{2T U} which is defined on continuous variables σ_i, r_j, i, j ∈ N and integer variables y_h, h ∈ I such that the polyhedron conv(M ) ∩ {(σ, r, y) : y_h = 0, h ∈ I} is a nonempty face of conv(M ) described by inequalities (23)–(24). Therefore Theorem 9 shows that any extended formula- tion of conv(M ) that explicitly takes into account a list of all possible fractional parts of the continuous variables will not be compact in the description of M .

(11)

Now let b_ij be as in the theorem, i.e. b_ij = ³^(j−1)n+i

3ⁿ²⁺¹ , i, j ∈ N .

Observation 2 b_ij < b_i⁰_j⁰ if and only if (j, i) ≺ (j⁰, i⁰), where ≺ denotes the lexicographic order. Thus b₁₁< b₂₁· · · < b_n1< b₁₂< · · · < b_nn.

Lemma 10 (i) Suppose that α ∈ Z^q₊ with α_t < α_t+1 for 1 ≤ t ≤ q − 1, and Φ(α) = P_q

t=1(−1)^q−t3^α^t. Then ³₂3^α^q > Φ(α) > ¹₂3^α^q.

(ii) Suppose that α is as above and β ∈ Z^q₊⁰ is defined similarly. Then Φ(α) = Φ(β) if and only if α = β.

Proof: (i)P_α_q₋₁

j=0 3^j = ³^αq₃₋₁⁻¹ < ¹₂3^α^q. Now Φ(α) ≥ 3^α^q −P_α_q₋₁

j=0 3^j > 3^α^q −¹₂3^α^q = ¹₂3^α^q, and Φ(α) ≤ 3^α^q+P_α_q₋₁

j=0 3^j < 3^α^q+ ¹₂3^α^q = ³₂3^α^q.

(ii) Suppose α 6= β. Wlog we assume q ≥ q⁰. Assume first (α_q−q⁰₊₁, . . . , α_q) = β. Then q > q⁰ (otherwise α = β) and, after defining ¯α = (α₁, . . . , α_q−q⁰), we have Φ(α) − Φ(β) = Φ(¯α) > 0 by (i). Now assume (α_q−q⁰₊₁, . . . , α_q) 6= β. Define h = min{τ : α_q−τ 6= β_q⁰_−τ} and suppose α_q−h > β_q⁰_−h (the other case is similar). If we define the vectors ¯α = (α₁, . . . , α_q−h) and β = (β¯ ₁, . . . , β_q⁰_−h), (i) gives Φ(α) − Φ(β) = Φ(¯α) − Φ( ¯β) > ¹₂3^α^q−h − ³₂3^β^q0−h ≥ 0, as

α_q−h > β_q⁰_−h. 2

We now give a construction of an exponential family of vertices of Q such that at each vertex variable σ_n takes a distinct fractional part. Therefore this construction proves Theo- rem 9.

Let (i₁, . . . , i_m) and (j₁, . . . , j_m−1) be two increasing subsets of N with i₁ = 1 and i_m= n.

For i, j ∈ N , let p(i) = max{t : i_t≤ i} and q(j) = max{t : j_t≤ j}, with q(j) = 0 if j < j₁. Consider the following system of equations:

σ_i₁ = 0

σ_i_t + r_j_t = b_i_t_j_t, 1 ≤ t ≤ m − 1 σ_i_t+1+ r_j_t = b_i_t+1_j_t, 1 ≤ t ≤ m − 1 σ_i_q(j)+1+ r_j = b_i_q(j)+1_j, j /∈ {j₁, . . . , j_m−1}

σ_i+ r_j_p(i) = b_ij_p(i), i /∈ {i₁, . . . , i_m}.

The unique solution of this system is:

σ_i₁ = 0 σ_i_t =

Xt−1

`=1

b_i_`+1_j_`− Xt−1

`=1

b_i_`_j_`, 2 ≤ t ≤ m

r_j_t = Xt

`=1

b_i_`_j_`− Xt−1

`=1

b_i_`+1_j_`, 1 ≤ t ≤ m − 1 σ_i = b_ij_p(i) − r_j_p(i), i /∈ {i₁, . . . , i_m} r_j = b_i_q(j)+1_j− σ_i_q(j)+1, j /∈ {j₁, . . . , j_m−1}.

As each of these variables σ_i, r_j takes a value of the form Φ(α)/3ⁿ²⁺¹, by Lemma 10 (i) we have that σ_i_t > ¹₂b_i_t_j_t−1 > 0 for 2 ≤ t ≤ m, r_j_t > ¹₂b_i_t_j_t > 0 for 1 ≤ t ≤ m − 1,

(12)

σ_i> ¹₂b_ij_p(i) > 0 for i /∈ {i₁, . . . , i_m}, and r_j > ¹₂b_i_q(j)+1_j > 0 for j /∈ {j₁, . . . , j_m−1}. Therefore the nonnegativity constraints are satisfied.

Now we show that the other constraints are satisfied. Consider the i, j constraint with j /∈ {j₁, . . . , j_m−1}. We distinguish some cases.

1. p(i) ≤ q(j). Then σ_i+ r_j ≥ r_j > ¹₂b_i_q(j)+1_j ≥ ¹₂b_i_p(i)+1_j ≥ ³₂b_ij > b_ij.

2. p(i) > q(j) and i /∈ {i₁, . . . , i_m}. Then σ_i+ r_j ≥ σ_i > ¹₂b_ij_p(i) ≥ ¹₂b_ij_q(j)+1 ≥ ³₂b_ij > b_ij. 3. p(i) = q(j) + 1 and i = i_t for some 1 ≤ t ≤ m (thus p(i) = t = q(j) + 1). In this case

the i, j constraint is satisfied at equality by construction.

4. p(i) > q(j) + 1 and i = i_t for some 1 ≤ t ≤ m (thus p(i) = t > q(j) + 1). Then σ_i+ r_j ≥ σ_i > ¹₂b_ij_t−1 ≥ ¹₂b_ij_q(j)+1 ≥ ³₂b_ij > b_ij.

The argument with i /∈ {i₁, . . . , i_m} is similar.

Finally suppose that i = i_tand j = j_u with u /∈ {t − 1, t}. If u > t, σ_i+ r_j ≥ r_j > ¹₂b_i_u_j_u≥

32b_i_t_j_u > b_ij. If u < t − 1, σ_i+ r_j ≥ σ_i> ¹₂b_i_t_j_t−1 ≥ ³₂b_i_t_j_u > b_ij.

This shows that the solution is feasible and as it is unique, it defines a vertex of the above polyhedron.

Now let a_ij = (j − 1)n + i, so that b_ij = 3^a^ij/3ⁿ²⁺¹ and take α = (a_i₁_j₁, a_i₂_j₁, a_i₂_j₂, a_i₃_j₂, . . . , a_i_m_j_m−1).

As σ_n = Φ(α)/3ⁿ²⁺¹, it follows from Lemma 10 (ii) that in any two vertices constructed as above by different sequences (i₁, . . . , i_m), (j₁, . . . , j_m−1) and (i⁰₁, . . . , i⁰_m0), (j₁⁰, . . . , j_m⁰ 0−1), the values of σ_n are distinct numbers in the interval (0, 1). As the number of such sequences is exponential in n, this proves Theorem 9.

6.2 Sufficient conditions for compactness of the formulation

We now describe conditions that ensure the existence of a compact formulation for a mixed- integer set X of the type M IX^{2T U}. Since X is described by a linear system Ax ≥ b where A is a TU matrix with at most two nonzero entries per row, the constraints defining X are of the following type:

x_i+ x_j ≥ l⁺⁺_ij , (i, j) ∈ N⁺⁺ (25) x_i− x_j ≥ l⁺⁻_ij , (i, j) ∈ N⁺⁻ (26)

−x_i− x_j ≥ l⁻⁻_ij , (i, j) ∈ N⁻⁻ (27) x_i≥ l_i, i ∈ N^l

x_i≤ u_i, i ∈ N^u x_i integer, i ∈ I,

where N⁺⁺, N⁺⁻, N⁻⁻ ⊆ N × N and N^l, N^u, I ⊆ N . Wlog we assume that if (i, j) ∈ N⁺⁺

then (j, i) /∈ N⁺⁺ and if (i, j) ∈ N⁻⁻ then (j, i) /∈ N⁻⁻.

Let G_X = (V, E) be the undirected graph with node set V = L = N \ I corresponding to the continuous variables of X. E contains an edge ij for each inequality of the type (25)–(27) with i, j ∈ L appearing in the linear system that defines X. Notice that since A is a TU