BCOL RESEARCH REPORT 15.03

arXiv:1705.05920v1 [math.OC] 16 May 2017

Industrial Engineering & Operations Research
University of California, Berkeley, CA 94720–1777

PATH COVER AND PATH PACK INEQUALITIES FOR THE
CAPACITATED FIXED-CHARGE NETWORK FLOW PROBLEM
ALPER ATAMTÜRK, BIRCE TEZEL AND SIMGE KÜÇÜKYAVUZ

Abstract. Capacitated fixed-charge network flows are used to model a variety of problems in telecommunication, facility location, production planning and supply chain management. In this paper, we investigate capacitated path substructures and derive strong
and easy-to-compute path cover and path pack inequalities. These inequalities are based
on an explicit characterization of the submodular inequalities through a fast computation
of parametric minimum cuts on a path, and they generalize the well-known flow cover
and flow pack inequalities for the single-node relaxations of fixed-charge flow models. We
provide necessary and sufficient facet conditions. Computational results demonstrate the
effectiveness of the inequalities when used as cuts in a branch-and-cut algorithm.

July 2015; October 2016; May 2017
1. Introduction
Given a directed multigraph with demand or supply on the nodes, and capacity, fixed and
variable cost of flow on the arcs, the capacitated fixed-charge network flow (CFNF) problem
is to choose a subset of the arcs and route the flow on the chosen arcs while satisfying the
supply, demand and capacity constraints, so that the sum of fixed and variable costs is
minimized.
There are numerous polyhedral studies of the fixed-charge network flow problem. In a
seminal paper Wolsey (1989) introduces the so-called submodular inequalities, which subsume almost all valid inequalities known for capacitated fixed-charge networks. Although
the submodular inequalities are very general, their coefficients are defined implicitly through
value functions. In this paper, we give explicit valid inequalities that simultaneously make
use of the path substructures of the network as well as the arc capacities.
For the uncapacitated fixed-charge network flow problem, van Roy and Wolsey (1985)
give flow path inequalities that are based on path substructures. Rardin and Wolsey (1993)
A. Atamtürk: Department of Industrial Engineering & Operations Research, University of California, Berkeley, CA 94720. atamturk@berkeley.edu
B. Tezel: Department of Industrial Engineering & Operations Research, University of California, Berkeley,
CA 94720. btezel@berkeley.edu
S. Küçükyavuz: Department of Industrial and Systems Engineering, University of Washington, Seattle, WA
98195. simge@uw.edu .
1

introduce a new family of dicut inequalities and show that they describe the projection of
an extended multicommodity formulation onto the original variables of fixed-charge network
flow problem. Ortega and Wolsey (2003) present a computational study on the performance
of path and cut-set (dicut) inequalities.
For the capacitated fixed-charge network flow problem, almost all known valid inequalities
are based on single-node relaxations. Padberg et al. (1985), van Roy and Wolsey (1986)
and Gu et al. (1999) give flow cover, generalized flow cover and lifted flow cover inequalities.
Stallaert (1997) introduces the complement class of generalized flow cover inequalities and
Atamtürk (2001) describes lifted flow pack inequalities. Both uncapacitated path inequalities and capacitated flow cover inequalities are highly valuable in solving a host of practical
problems and are part of the suite of cutting planes implemented in modern mixed-integer
programming solvers.
The path structure arises naturally in network models of the lot-sizing problem. Atamtürk
and Muñoz (2004) introduce valid inequalities for the capacitated lot-sizing problems with
infinite inventory capacities. Atamtürk and Küçükyavuz (2005) give valid inequalities for
the lot-sizing problems with finite inventory and infinite production capacities. Van Vyve
(2013) introduces path-modular inequalities for the uncapacitated fixed charge transportation problems. These inequalities are derived from a value function that is neither globally
submodular nor supermodular but that exhibits sub or supermodularity under certain set
selections. Van Vyve and Ortega (2004) and Gade and Küçükyavuz (2011) give valid inequalities and extended formulations for uncapacitated lot-sizing with fixed charges on stocks.
For uncapacitated lot-sizing with backlogging, Pochet and Wolsey (1988) and Pochet and
Wolsey (1994) provide valid inequalities and Küçükyavuz and Pochet (2009) provide an
explicit description of the convex hull.
Contributions. In this paper we consider a generic path relaxation, with supply and/or
demand nodes and capacities on incoming and outgoing arcs. By exploiting the path substructure of the network and introducing notions of path cover and path pack we provide
two explicitly-described subclasses of the submodular inequalities of Wolsey (1989). The
most important consequence of the explicit derivation is that the coefficients of the submodular inequalities on a path can be computed efficiently. In particular, we show that the
coefficients of such an inequality can be computed by solving max-flow/min-cut problems
parametrically over the path. Moreover, we show that all of these coefficients can be computed with a single linear-time algorithm. For a path with a single node, the inequalities
reduce to the well-known flow cover and flow pack inequalities. Moreover, we show that
the path cover and path pack inequalities dominate flow cover and flow pack inequalities
for the corresponding single node relaxation of a path obtained by merging the path into a
single node. We give necessary and sufficient facet-defining conditions. Finally, we report
on computational experiments demonstrating the effectiveness of the proposed inequalities
when used as cuts in a branch-and-cut algorithm.
Outline. The remainder of this paper is organized as follows: In Section 2, we describe
the capacitated fixed-charge flow problem on a path, its formulation and the assumptions
we make. In Section 3, we review the submodular inequalities, discuss their computation
on a path, and introduce two explicit subclasses: path cover inequalities and path pack
2

inequalities. In Section 4, we analyze sufficient and necessary facet-defining conditions. In
Section 5, we present computational experiments showing the effectiveness of the path cover
and path pack inequalities compared to other network inequalities.
2. Capacitated fixed-charge network flow on a path
Let G = (N 0 , A) be a directed multigraph with nodes N 0 and arcs A. Let sN and tN be
the source and the sink nodes of G. Let N := N 0 \ {sN , tN }. Without loss of generality,
we label N := {1, . . . , n} such that a directed forward path arc exists from node i to node
i + 1 and a directed backward path arc exists from node i + 1 to node i for each node
i = 1, . . . , n − 1 (see Figure 1 for an illustration). In Remarks 1 and 2, we discuss how to
obtain a “path” graph G from a more general directed multigraph.
Let E + = {(i, j) ∈ A : i = sN , j ∈ N } and E − = {(i, j) ∈ A : i ∈ N, j = tN }.
Moreover, let us partition the sets E + and E − such that Ek+ = {(i, j) ∈ A : i ∈
/ N, j = k}
−
+
and Ek = {(i, j) ∈ A : i = k, j ∈
/ N } for k ∈ N . We refer to the arcs in E and E − as
non-path arcs. Finally, let E := E + ∪ E − be the set of all non-path arcs. For convenience,
we generalize this set notation scheme. Given an arbitrary subset of non-path arcs Y ⊆ E,
let Yj+ = Y ∩ Ej+ and Yj− = Y ∩ Ej− .
Remark 1. Given a directed multigraph G̃ = (Ñ , Ã) with nodes Ñ , arcs Ã and a path that
passes through nodes N , we can construct G as described above by letting E + = {(i, j) ∈
Ã : i ∈ Ñ \ N, j ∈ N } and E − = {(i, j) ∈ Ã : i ∈ N, j ∈ Ñ \ N } and letting all the arcs in
E + be the outgoing arcs from a dummy source sN and all the arcs in E − to be incoming
to a dummy sink tN .
Remark 2. If there is an arc t = (i, j) from node i ∈ N to j ∈ N , where |i − j| > 1,
then we construct a relaxation by removing arc t, and replacing it with two arcs t− ∈ Ei−
and t+ ∈ Ej+ . If there are multiple arcs from node i to node j, one can repeat the same
procedure.
Throughout the paper, we use the following notation: Let [k, j] = {k, k +1, . . . , j} if k ≤ j
P
P
Pj
and ∅ otherwise, c(S) = t∈S ct , y(S) = t∈S yt , (a)+ = max{0, a} and dkj = t=k dt if
j ≥ k and 0 otherwise. Moreover, let dim(A) denote the dimension of a polyhedron A and
conv(S) be the convex hull of a set S.
The capacitated fixed-charge network flow problem on a path can be formulated as a
mixed-integer optimization problem. Let dj be the demand at node j ∈ N . We call a node
j ∈ N a demand node if dj ≥ 0 and a supply node if dj < 0. Let the flow on forward path
arc (j, j + 1) be represented by ij with an upper bound uj for j ∈ N \ {n}. Similarly, let
the flow on backward path arc (j + 1, j) be represented by rj with an upper bound bj for
j ∈ N \ {n}. Let yt be the amount of flow on arc t ∈ E with an upper bound ct . Define
binary variable xt to be 1 if yt > 0, and zero otherwise for all t ∈ E. An arc t is closed if
xt = 0 and open if xt = 1. Moreover, let ft be the fixed cost and pt be the unit flow cost
of arc t. Similarly, let hj and gj be the costs of unit flow, on forward and backward arcs
(j, j + 1) and (j + 1, j) respectively for j ∈ N \ {n}. Then, the problem is formulated as
X
X
min
(ft xt + pt yt ) +
(hj ij + gj rj )
(1a)
t∈E

j∈N
3

sN
cti
b1
1
d1

b2

...

3

2
u1 d2

bn−1

b3

u2

d3

n
un−1

u3

dn

ctk
tN
Figure 1. Fixed-charge network representation of a path.
s. t.

ij−1 − rj−1 + y(Ej+ ) − y(Ej− ) − ij + rj = dj ,
0 ≤ yt ≤ ct xt ,

(F1)

t ∈ E,

j ∈ N,

(1b)
(1c)

0 ≤ ij ≤ uj ,

j ∈ N,

(1d)

0 ≤ rj ≤ bj ,

j ∈ N,

(1e)

xt ∈ {0, 1},

t ∈ E,

(1f)

i0 = in = r0 = rn = 0.

(1g)

Let P be the set of feasible solutions of (F1). Figure 1 shows an example network representation of (F1).
Throughout we make the following assumptions on (F1):
The set Pt = {(x, y, i, r) ∈ P : xt = 0} =
6 ∅ for all t ∈ E,
ct > 0, uj > 0 and bj > 0 for all t ∈ E and j ∈ N ,
ct ≤ d1n + c(E − ) for all t ∈ E + ,
ct ≤ bj−1 + uj + (dj )+ + c(Ej− ), for all j ∈ N, t ∈ Ej+ ,
ct ≤ bj + uj−1 + (−dj )+ + c(Ej+ ) for all j ∈ N, t ∈ Ej− .

Assumptions (A.1)–(A.2) ensure that dim conv(P) = 2|E| + |N | − 2. If (A.1) does not hold
for some t ∈ E, then xt = 1 for all points in P. Similarly, if (A.2) does not hold, the flow
on such an arc can be fixed to zero. Finally, assumptions (A.3)–(A.5) are without loss of
generality. An upper bound on yt can be obtained directly from the flow balance equalities
(1b) by using the upper and lower bounds of the other flow variables that appear in the
same constraint. As a result, the flow values on arcs t ∈ E cannot exceed the capacities
implied by (A.3)–(A.5).
Next, we review the submodular inequalities introduced by Wolsey (1989) that are valid
for any capacitated fixed-charge network flow problem. Furthermore, using the path structure, we provide an O(|E| + |N |) time algorithm to compute their coefficients explicitly.
(A.1)
(A.2)
(A.3)
(A.4)
(A.5)

4

3. Submodular inequalities on paths
Let S + ⊆ E + and L− ⊆ E − . Wolsey (1989) shows that the value function of the following
optimization problem is submodular:
X
v(S + , L− ) = max
at yt
(2a)
t∈E

s. t.

(F2)

ij−1 − rj−1 + y(Ej+ ) − y(Ej− ) − ij + rj ≤ dj ,

j ∈ N,

(2b)

0 ≤ ij ≤ uj ,

j ∈ N,

(2c)

0 ≤ rj ≤ bj ,

j ∈ N,

(2d)

0 ≤ yt ≤ ct ,

t ∈ E,

(2e)

i0 = in = r0 = rn = 0,
yt = 0,

+

+

(2f)
−

t ∈ (E \ S ) ∪ L ,

(2g)

where at ∈ {0, 1} for t ∈ E + and at ∈ {0, −1} for t ∈ E − . The set of feasible solutions of
(F2) is represented by Q.
We call the sets S + and L− that are used in the definition of v(S + , L− ) the objective sets.
For ease of notation, we also represent the objective sets as C := S + ∪ L− . Following this
notation, let v(C) := v(S + , L− ), v(C \ {t}) = v(S + \ {t}, L− ) for t ∈ S + and v(C \ {t}) =
v(S + , L− \ {t}) for t ∈ L− . Similarly, let v(C ∪ {t}) = v(S + ∪ {t}, L− ), for t ∈ S + and
v(C ∪ {t}) = v(S + , L− ∪ {t}) for t ∈ L− . Moreover, let
ρt (C) = v(C ∪ {t}) − v(C)
be the marginal contribution of adding an arc t to C with respect to the value function v.
Wolsey (1989) shows that the following inequalities are valid for P:
X
X
X
a t yt +
ρt (C \ {t})(1 − x̄t ) ≤ v(C) +
ρt (∅)x̄t ,
(3)
t∈E

X
t∈E

at yt +

t∈C

X

t∈E\C

ρt (E \ {t})(1 − x̄t ) ≤ v(C) +

t∈C

X

ρt (C)x̄t ,

(4)

t∈E\C

where the variable x̄t is defined as
(
x̄t =

xt ,

t ∈ E+

1 − xt ,

t ∈ E−.

In fact, inequalities (3) and (4) are also valid for fixed-charge network flow formulations
where the flow balance constraints (1b) are replaced with constraints (2b). However, in this
paper, we focus on formulations with flow balance equalities (1b).
We refer to submodular inequalities (3) and (4) derived for path structures as path inequalities. In this paper, we consider sets S + and L− such that (F2) is feasible for all
objective sets C and C \ {t} for all t ∈ C.

5

3.1. Equivalence to the maximum flow problem. Define sets K + and K − such that
the coefficients of the objective function (2a) are:

+


1, t ∈ K
at =

−1, t ∈ K −


0, otherwise,

(5)

where S + ⊆ K + ⊆ E + and K − ⊆ E − \ L− . We refer to the sets K + and K − as coefficient
sets. Let the set of arcs with zero coefficients in (2a) be represented by K̄ + = E + \ K + and
K̄ − = E − \ K − . Given a selection of coefficients as described in (5), we claim that (F2)
can be transformed to a maximum flow problem. We first show this result assuming dj ≥ 0
for all j ∈ N . Then, in Appendix A, we show that the nonnegativity of demand is without
loss of generality for the derivation of the inequalities.
Proposition 1. Let S + ⊆ E + and L− ⊆ E − be the objective sets in (F2) and let Y be the
nonempty set of optimal solutions of (F2). If dj ≥ 0 for all j ∈ N , then there exists at least
one optimal solution (y∗ , r∗ , i∗ ) ∈ Y such that yt∗ = 0 for t ∈ K̄ + ∪ K − ∪ L− .
Proof. Observe that yt∗ = 0 for all t ∈ E + \S + , due to constraints (2g). Since K̄ + ⊆ E + \S + ,
yt∗ = 0, for t ∈ K̄ + from feasibility of (F2). Similarly, yt∗ = 0 for all t ∈ L− by constraints
(2g).
Now suppose that, yt∗ =  > 0 for some t ∈ Kj− (i.e., at = −1 for arc t in (F2)). Let the
slack value at constraint (2b) for node j be


∗
sj = dj − i∗j−1 − rj−1
+ y ∗ (Ej+ ) − y ∗ (Ej− \ {t}) − yt∗ − i∗j + rj∗ .
If sj ≥ , then decreasing yt∗ by  both improves the objective function value and conserves
the feasibility of flow balance inequality (2b) for node j, since sj −  ≥ 0.
If sj < , then decreasing yt∗ by  violates flow balance inequality since sj −  < 0. In this
case, there must exist a simple directed path P from either the source node sN or a node
k ∈ N \ {j} to node j where all arcs have at least a flow of ( − sj ). This is guaranteed
because, sj <  implies that, without the outgoing arc t, there is more incoming flow to
node j than outgoing. Then, notice that decreasing the flow on arc t and all arcs in path
P by  − sj conserves feasibility. Moreover, the objective function value either remains the
same or increases, because decreasing yt by  − sj increases the objective function value by
 − sj and the decreasing the flow on arcs in P decreases it by at most  − sj . At the end
of this transformation, the slack value sj does not change, however; the flow at arc t is now
yt∗ = sj which is equivalent to the first case that is discussed above. As a result, we obtain
a new solution to (F2) where yt∗ = 0 and the objective value is at least as large. 
Proposition 2. If dj ≥ 0 for all j ∈ N , then (F2) is equivalent to a maximum flow problem
from source sN to sink tN on graph G.
Proof. At the optimal solution of problem (F2) with objective set (S + , L− ), the decision
variables yt , for t ∈ (E + \ S + ) ∪ K − ∪ L− can be assumed to be zero due to Proposition
1 and constraints (2g). Then, these variables can be dropped from (F2) since the value
v(S + , L− ) does not depend them and formulation (F2) reduces to

v(S + , L− ) = max y(S + ) : ij−1 − rj−1 + y(Sj+ ) − y(K̄j− ) − ij + rj ≤ dj , j ∈ N,
6

(2c) − (2f) .

(6)

Now, we reformulate (6) by representing the left hand side of the flow balance constraint by
a new nonnegative decision variable zj that has an upper bound of dj for each j ∈ N :

max y(S + ) : ij−1 − rj−1 + y(Sj+ ) − y(K̄j− ) − ij + rj = zj , j ∈ N,
0 ≤ zj ≤ dj , j ∈ N,

(2c) − (2f) .

The formulation above is equivalent the maximum flow formulation from the source node
sN to the sink node tN for the path structures we are considering in this paper. 
Under the assumption that dj ≥ 0 for all j ∈ N , Proposition 1 and Proposition 2 together
show that the optimal objective function value v(S + , L− ) can be computed by solving a
maximum flow problem from source sN to sink tN . We generalize this result in Appendix
A for node sets N such that dj < 0 for some j ∈ N . As a result, obtaining the explicit
coefficients of submodular inequalities (3) and (4) reduces to solving |E| + 1 maximum flow
problems. For a general underlying graph, solving |E| + 1 maximum flow problems would
take O(|E|2 |N |) time (e.g., see King et al. (1994)), where |E| and |N | are the number of
arcs and nodes, respectively. In the following subsection, by utilizing the equivalence of
maximum flow and minimum cuts and the path structure, we show that all coefficients of
(3) and (4) can be obtained in O(|E| + |N |) time using dynamic programming.
3.2. Computing the coefficients of the submodular inequalities. Throughout the
paper, we use minimum cut arguments to find the explicit coefficients of inequalities (3)
and (4). Figure 2a illustrates an example where N = [1, 5], E + = [1, 5], E − = [6, 10]
and in Figure 2b, we give an example of an sN − tN cut for S + = {2, 4, 5}, L− = {10}
and K̄ − = {7, 9, 10}. The dashed line in Figure 2b represents a cut that corresponds to
the partition {sN , 2, 5} and {tN , 1, 3, 4} with a value of b1 + d2 + c7 + u2 + c4 + b4 + d5 .
Moreover, we say that a cut passes below node j if j is in the source partition and passes
above node j if j is in the sink partition.
Let αju and αjd be the minimum value of a cut on nodes [1, j] that passes above and below
node j, respectively. Similarly, let βju and βjd be the minimum values of cuts on nodes [j, n]
that passes above and below node j respectively. Finally, let
S − = E − \ (K − ∪ L− ),
where K − is defined in (5). Recall that S + and L− are the given objective sets. Given the
notation introduced above, all of the arcs in sets S − and L− have a coefficient zero in (F2).
Therefore, dropping an arc from L− is equivalent to adding that arc to S − . We compute
{u,d}
{u,d}
αj
by a forward recursion and βj
by a backward recursion:
d
u
αju = min{αj−1
+ uj−1 , αj−1
} + c(Sj+ )

αjd

=

d
u
min{αj−1
, αj−1

+ bj−1 } + dj +

c(Sj− ),

(7)
(8)

where α0u = α0d = 0 and
u
d
βju = min{βj+1
, βj+1
+ bj } + c(Sj+ )
u
d
βjd = min{βj+1
+ uj , βj+1
} + dj + c(Sj− ),
7

(9)
(10)

c2

c1
u1

1

u2

2

d1

u3

3

c7

d2

c5
u4

4

b3

b2

b1
c6

c4

c3

c8

d3

5

b4
c9

d4

c10

d5

(a) A path graph with E + = [1, 5] and E − = [6, 10].

c2
1

u1

c4
2

3

c7

d2

u3

4

b3

b2

b1
d1

u2

c5

d3

u4

5

b4
c9

d4

d5

(b) An sN − tN cut for set S + = {2, 4, 5}, L− = {10} and K̄ − = {7, 9, 10}.

Figure 2. An example of an sN − tN cut.
u
d
where βn+1
= βn+1
= 0.
u
Let mj and mdj be the values of minimum cuts for nodes [1, n] that pass above and below
node j, respectively. Notice that

muj = αju + βju − c(Sj+ )

(11)

mdj = αjd + βjd − dj − c(Sj− ).

(12)

and

For convenience, let
mj := min{muj , mdj }.
Notice that mj is the minimum of the minimum cut values that passes above and below
node j. Since the minimum cut corresponding to v(C) has to pass either above or below
node j, mj is equal to v(C) for all j ∈ N . As a result, the minimum cut (or maximum flow)
value for the objective set C = S + ∪ L− is
v(C) = m1 = · · · = mn .

(13)

Proposition 3. All values mj , for j ∈ N , can be computed in O(|E| + |N |) time.
Obtaining the explicit coefficients of inequalities (3) and (4) also requires finding v(C \{t})
for t ∈ C and v(C ∪ {t}) for t ∈
/ C in addition to v(C). It is important to note that we do
not need to solve the recursions above repeatedly. Once the values muj and mdj are obtained
for the set C, the marginals ρt (C \ {t}) and ρt (C) can be found in O(1) time for each t ∈ E.
We use the following observation while providing the marginal values ρt (C) and ρt (C \{t})
in closed form.
Observation 1. Let c ≥ 0 and d := (b − a)+ , then,
1. min{a + c, b} − min{a, b} = min{c, d},
2. min{a, b} − min{a, b − c} = (c − d)+ .
8

In the remainder of this section, we give a linear-time algorithm to compute the coefficients ρt for inequalities (3) and (4) explicitly for paths.
Coefficients of inequality (3): Path cover inequalities. Let S + and L− be the objective sets in (F2) and S − ⊆ E − \ L− . We select the coefficient sets in (5) as K + = S + and
K − = E − \ (L− ∪ S − ) to obtain the explicit form of inequality (3). As a result, the set
definition of S − = E − \ (K − ∪ L− ) is conserved.
Definition 1. Let the coefficient sets in (5) be selected as above and (S + , L− ) be the
objective set. The set (S + , S − ) is called a path cover for the node set N if
v(S + , L− ) = d1n + c(S − ).
For inequality (3), we assume that the set (S + , S − ) is a path cover for N . Then, by
definition,
v(C) = m1 = · · · = mn = d1n + c(S − ).
After obtaining the values muj and mdj for a node j ∈ N using recursions in (7)-(10), it is
trivial to find the minimum cut value after dropping an arc t from Sj+ :
t ∈ Sj+ ,

v(C \ {t}) = min{muj − ct , mdj },

j ∈ N.

Similarly, dropping an arc t ∈ L−
j results in the minimum cut value:
t ∈ L−
j ,

v(C \ {t}) = min{muj , mdj + ct },

j ∈ N.

Using Observation 1, we obtain the marginal values
ρt (C \ {t}) = (ct − λj )+ ,

t ∈ S+

ρt (C \ {t}) = min{λj , ct },

t ∈ L−

and
where
λj = (muj − mdj )+ ,

j ∈ N.

On the other hand, all the coefficients ρt (∅) = 0 for arcs t ∈ E \ C. First, notice that,
for t ∈ E + \ S + , v({t}) = 0, because the coefficient at = 0 for t ∈ E + \ S + . Furthermore,
v({t}) = 0 for t ∈ E − \ L− , since all incoming arcs would be closed for an objective set
(∅, {t}). As a result, inequality (3) for the objective set (S + , L− ) can be written as
X
X
y(S + ) +
(ct − λj )+ (1 − xt ) ≤ d1n + c(S − ) +
min{ct , λj }xt + y(E − \ (L− ∪ S − )).
t∈L−

t∈S +

(14)
We refer to inequalities (14) as path cover inequalities.
Remark 3. Observe that for a path consisting of a single node N = {j} with demand
d := dj > 0, the path cover inequalities (14) reduce to the flow cover inequalities (Padberg
et al., 1985, van Roy and Wolsey, 1986). Suppose that the path consists of a single node
N = {j} with demand d := dj > 0. Let S + ⊆ E + and S − ⊆ E − . The set (S + , S − ) is a
flow cover if λ := c(S + ) − d − c(S − ) > 0 and the resulting path cover inequality
X
y(S + ) +
(ct − λ)+ (1 − xt ) ≤ d + c(S − ) + λx(L− ) + y(E − \ L− )
(15)
t∈S +
9

is a flow cover inequality.
Proposition 4. Let (S + , S − ) be a path cover for the node set N . The path cover inequality
for node set N is at least as strong as the flow cover inequality for the single node relaxation
obtained by merging the nodes in N .
Proof. Flow cover and path cover inequalities differ in the coefficients of variables xt for
t ∈ S + and t ∈ L− . Therefore, we compare the values λj , j ∈ N of path cover inequalities
(14) to the value λ of flow cover inequalities (15) and show that λj ≤ λ, for all j ∈ N . The
merging of node set N in graph G is equivalent to relaxing the values uj and bj to be infinite
for j ∈ [1, n − 1]. As a result, the value of the minimum cut that goes above a the merged
node is m̄u = c(S + ) and the value of the minimum cut that goes below the merged node is
m̄d = d1n + c(S − ). Now, observe that the recursions in (7)-(10) imply that the minimum
cut values for the original graph G are smaller:
muj = αju + βju − c(Sj+ ) ≤ c(S + ) = m̄u
and
mdj = αjd + βjd − dj − c(Sj− ) ≤ d1n + c(S − ) = m̄d
for all j ∈ N . Recall that the coefficient for the flow cover inequality is λ = (m̄u − m̄d )+
and the coefficients for path cover inequality are λj = (muj − mdj )+ for j ∈ N . The fact that
(S + , S − ) is a path cover implies that mdj = d1n + c(S − ) for all j ∈ N . Since m̄d = mdj and
muj ≤ m̄u for all j ∈ N , we observe that λj ≤ λ for all j ∈ N . Consequently, the path cover
inequality (14) is at least as strong as the flow cover inequality (15). 

c1 = 15

c2 = 35
u1 = 10

1

u2 = 10
2

b1 = 15
d1 = 10

c3 = 30

c4 = 10

u3 = 20
3

b2 = 15
d2 = 10

4
b3 = 10

d3 = 5

d4 = 15

Figure 3. A lot-sizing instance with backlogging.
Example 1. Consider the lot-sizing instance in Figure 3 where N = [1, 4], S + = {2, 3},
L− = ∅. Observe that mu1 = 45, md1 = 40, mu2 = 65, md2 = 40, mu3 = 60, md3 = 40, and
mu4 = 45, md4 = 40. Then, λ1 = 5, λ2 = 25, λ3 = 20, and λ4 = 5 leading to coefficients 10
and 10 for (1 − x2 ) and (1 − x3 ), respectively. Furthermore, the maximum flow values are
v(C) = 40, v(C \ {2}) = 30, and v(C \ {3}) = 30. Then, the resulting path cover inequality
(14) is
y2 + y3 + 10(1 − x2 ) + 10(1 − x3 ) ≤ 40,

(16)

and it is facet-defining for conv(P) as will be shown in Section 4. Now, consider the relaxation obtained by merging the nodes in [1, 4] into a single node with incoming arcs {1, 2, 3, 4}
and demand d = 40. As a result, the flow cover inequalities can be applied to the merged
10

node set. The excess value for the set S + = {2, 3} is λ = c(S + ) − d = 25. Then, the
resulting flow cover inequality (15) is
y2 + y3 + 10(1 − x2 ) + 5(1 − x3 ) ≤ 40,
and it is weaker than the path cover inequality (16). 
Coefficients of inequality (4): Path pack inequalities. Let S + and L− be the objective
sets in (F2) and let S − ⊆ E − \ L− . We select the coefficient sets in (5) as K + = E + and
K − = E − \ (S − ∪ L− ) to obtain the explicit form of inequality (4). As a result, the set
definition of S − = E − \ (K − ∪ L− ) is conserved.
Definition 2. Let the coefficients in (5) be selected as above and (S + , L− ) be the objective
set. The set (S + , S − ) is called a path pack for node set N if
v(S + , L− ) = c(S + ).
For inequality (4), we assume that the set (S + , S − ) is a path pack for N and L− = ∅
for simplicity. Now, we need to compute the values of v(C), v(E), v(E \ {t}) for t ∈ C and
v(C ∪ {t}) for t ∈ E \ C. The value of v(C ∪ {t}) can be obtained using the values muj and
mdj that are given by recursions (7)-(10). Then,
t ∈ Ej+ \ Sj+ ,

v(C ∪ {t}) = min{muj + ct , mdj },

j∈N

and
t ∈ Sj− ,

v(C ∪ {t}) = min{muj , mdj + ct },

j ∈ N.

Then, using Observation 1, we compute the marginal values
ρt (C) = min{ct , µj },

t ∈ Ej+ \ Sj+

and
ρt (C) = (ct − µj )+ ,

t ∈ Sj− ,

µj = (mdj − muj )+ ,

j ∈ N.

where
Next, we compute the values v(E) and v(E \{t}) for t ∈ C. The feasibility of (F1) implies
that (E + , ∅) is a path cover for N . By Assumption (A.1), (E + \ {t}, ∅) is also a path cover
for N for each t ∈ S + . Then v(E) = v(E \ {t}) = d1n and
ρt (E \ {t}) = 0,

t ∈ S + ∪ L− .

Then, inequality (4) can be explicitly written as
X
X
y(S + ) +
(yt − min{ct , µj }xt ) +
(ct − µj )+ (1 − xt ) ≤ c(S + ) + y(E − \ S − ). (17)
t∈E + \S +

t∈S −

We refer to inequalities (17) as path pack inequalities.
Remark 4. Observe that for a path consisting of a single node N = {j} with demand
d := dj > 0, the path pack inequalities (17), reduce to the flow pack inequalities ((Atamtürk,
2001)). Let (S + , S − ) be a flow pack and µ := d−c(S + )+c(S − ) > 0. Moreover, the maximum
flow that can be sent through S + for demand d and arcs in S − is c(S + ). Then, the value
11

function v(S + ) = c(S + ) and the resulting path pack inequality
X
X
(ct − µ)+ (1 − xt ) ≤ c(S + ) + y(E − \ S − ) (18)
y(S + ) +
(yt − min{ct , µ}xt ) +
t∈E + \S +

t∈S −

is equivalent to the flow pack inequality.
Proposition 5. Let (S + , S − ) be a path pack for the node set N . The path pack inequality
for N is at least as strong as the flow pack inequality for the single node relaxation obtained
by merging the nodes in N .
Proof. The proof is similar to that of Proposition 4. Flow pack and path pack inequalities
only differ in the coefficients of variables xt for t ∈ E + \ S + and t ∈ S − . Therefore, we
compare the values µj , j ∈ N of path pack inequalities (17) to the value µ of flow pack
inequalities (18) and show that µj ≤ µ for all j ∈ N . For the single node relaxation, the
values of the minimum cuts that pass above and below the merged node are m̄u = c(S + )
and m̄d = d1n + c(S − ), respectively. The recursions in (7)-(10) imply that
muj = αju + βju − c(Sj+ ) ≤ c(S + ) = m̄u
and
mdj = αjd + βjd − dj − c(Sj− ) ≤ d1n + c(S − ) = m̄d .
The coefficient for flow pack inequality is µ = (m̄d − m̄u )+ and for path pack inequality
µj = (mdj − muj )+ . Since (S + , S − ) is a path pack, the minimum cut passes above all nodes
in N and muj = c(S + ) for all j ∈ N . As a result, muj = m̄u for all j ∈ N and mdj ≤ m̄d .
Then, observe that the values
µj ≤ µ, j ∈ N.

Example 1 (continued). Recall the lot-sizing instance with backlogging given in Figure 3.
Let the node set N = [1, 4] with E − = ∅ and S + = {3}. Then, mu1 = 30, md1 = 40,
mu2 = 30, md2 = 40, mu3 = 30, md3 = 30, mu4 = 30, md4 = 30, leading to µ1 = 10, µ2 = 10,
µ3 = 0 and µ4 = 0. Moreover, the maximum flow values are v(C) = 30, v(C ∪ {1}) = 40,
v(C ∪ {2}) = 40, v(C ∪ {4}) = 30, v(E) = 40, and v(E \ {3}) = 40. Then the resulting path
pack inequality (17) is
y1 + y2 + y3 + y4 ≤ 30 + 10x1 + 10x2

(19)

and it is facet-defining for conv(P) as will be shown in Section 4. Now, suppose that the
nodes in [1, 4] are merged into a single node with incoming arcs {1, 2, 3, 4} and demand
d = 40. For the same set S + , we get µ = 40 − 30 = 10. Then, the corresponding flow pack
inequality (18) is
y1 + y2 + y3 + y4 ≤ 30 + 10x1 + 10x2 + 10x4 ,
which is weaker than the path pack inequality (19). 
Proposition 6. If |E + \S + | ≤ 1 and S − = ∅, then inequalities (14) and (17) are equivalent.
Proof. If E + \ S + = ∅ and S − = ∅, then it is easy to see that the coefficients of inequality
(17) are the same as (14). Moreover, if |E + \ S + | = 1 (and wlog E + \ S + = {j}), then the
12

resulting inequality (17) is
y(E + ) − y(E − ) ≤ v(C) + ρj (C)xj

= v(C) + v(C ∪ {j}) − v(C) xj
= v(C ∪ {j}) − ρj (C)(1 − xj ),
which is equivalent to path cover inequality (14) with the objective set (E + , ∅). 
4. The strength of the path cover and pack inequalities
The capacities of the forward and the backward path arcs play an important role in
finding the coefficients of the path cover and pack inequalities (14) and (17). Recall that
K + and K − are the coefficient sets in (5), (S + , L− ) is the objective set for (F2) and
S − = E − \ (K − ∪ L− ).
Definition 3. A node j ∈ N is called backward independent for set (S + , S − ) if
d
αju = αj−1
+ uj−1 + c(Sj+ ),

or
u
αjd = αj−1
+ bj−1 + dj + c(Sj− ).

Definition 4. A node j ∈ N is called forward independent for set (S + , S − ) if
d
βju = βj+1
+ bj + c(Sj+ ),

or
u
βjd = βj+1
+ uj + dj + c(Sj− ).

Intuitively, backward independence of node j ∈ N implies that the minimum cut either
passes through the forward path arc (j − 1, j) or through the backward path arc (j, j − 1).
Similarly, forward independence of node j ∈ N implies that the minimum cut either passes
through the forward path arc (j, j + 1) or through the backward path arc (j + 1, j). In
Lemmas 7 and 8 below, we further explain how forward and backward independence affect
+
−
the coefficients of path cover and pack inequalities. First, let Sjk
= ∪ki=j Si+ , Sjk
= ∪ki=j Si−
−
k
and L−
jk = ∪i=j Li if j ≤ k, and ∅ otherwise.
Lemma 7. If a node j ∈ N is backward independent for set (S + , S − ), then the values λj
+
−
and µj do not depend on the sets S1j−1
, S1j−1
and the value d1j−1 .
d
Proof. If a node j is backward independent, then either αju = αj−1
+ uj−1 + c(Sj+ ) or
−
+
d
u
u
d
αj = αj−1 + bj−1 + dj + c(Sj ). If αj = αj−1 + uj−1 + c(Sj ), then the equality in (7)
d
u
d
implies αj−1
+ uj−1 ≤ αj−1
. As a result, the equality in (8) gives αjd = αj−1
+ dj + c(Sj− ).
Following the definitions in (11)–(12), the difference

wj := muj − mdj
is βju − βjd + uj−1 which only depends on sets Sk+ and Sk− for k ∈ [j, n], the value djn and
the capacity of the forward path arc (j − 1, j).
u
u
d
If αjd = αj−1
+bj−1 +dj +c(Sj− ), then the equality in (8) implies αj−1
+bj−1 ≤ αj−1
. As a
+
u
u
u
result, the equality in (7) gives αj = αj−1 + c(Sj ). Then, the difference wj = βj − βjd − bj−1
13

which only depends on sets Sk+ and Sk− for k ∈ [j, n], the value djn and the capacity of the
backward path arc (j, j − 1).
Since the values λj and µj are defined as (wj )+ and (−wj )+ respectively, the result
follows. 
Remark 5. Let wj := muj − mdj . If a node j ∈ N is backward independent for a set (S + , S − ),
d
+ uj−1 + c(Sj+ ), then
then we observe the following: (1) If αju = αj−1
wj = βju − βjd + uj−1 ,
u
+ bj−1 + dj + c(Sj− ), then
and (2) if αjd = αj−1

wj = βju − βjd − bj−1 .
Lemma 8. If a node j ∈ N is forward independent for set (S + , S − ), then the values λj
+
−
and µj do not depend on the sets Sj+1n
, Sj+1n
and the value dj+1n .
d
d
Proof. The forward independence implies either βju = βj+1
+ bj + c(Sj+ ) and βjd = βj+1
+
−
+
−
u
u
d
u
dj + c(Sj ) or βj = βj+1 + c(Sj ) and βj = βj+1 + uj + dj + c(Sj ). Then, the difference
wj = muj − mdj is either αju + αjd + bj or αju + αjd − uj and in both cases, it is independent
of the sets Sk+ , Sk− for k ∈ [1, j − 1] and the value d1j−1 . 

Remark 6. Let wj := muj − mdj . If a node j ∈ N is forward independent for a set (S + , S − ),
d
then we observe the following: (1) If βju = βj+1
+ bj + c(Sj+ ), then
wj = αju − αjd + bj ,
u
and (2) if βjd = βj+1
+ uj + dj + c(Sj− ), then

wj = αju − αjd − uj .
Corollary 9. If a node j ∈ N is backward independent for set (S + , S − ), then the values
+
−
λk and µk for k ∈ [j, n] are also independent of the sets S1j−1
, S1j−1
and the value d1j−1 .
+
−
Similarly, if a node j ∈ N is forward independent for set (S , S ), then the values λk and
+
−
µk for k ∈ [1, j] are also independent of the sets Sj+1n
, Sj+1n
and the value dj+1n .
Proof. The proof follows from recursions in (7)–(10). If a node j is backward independent,
u
d
u
d
we write αj+1
and αj+1
in terms of αj−1
and αj−1
and observe that the difference wj+1 =
+
u
d
u
d
mj+1 − mj+1 does not depend on αj−1 nor αj−1 which implies independence of sets S1j−1
,
−
S1j−1 and the value d1n . We can repeat the same argument for wj , j ∈ [j + 2, n] to show
independence.
u
d
We show the same result for forward independence by writing βj−1
and βj−1
in terms of
u
d
u
d
βj+1 and βj+1 , we observe that wj does not depend on βj+1 nor βj+1 . Then, it is clear that
+
−
wj−1 is also independent of the sets Sj+1n
, Sj+1n
and the value dj+1n . We can repeat the
same argument for wj , j ∈ [1, j − 1] to show independence. 
Proving the necessary facet conditions frequently requires a partition of the node set N
into two disjoint sets. Suppose, N is partitioned into N1 = [1, j − 1] and N2 = [j, n] for
some j ∈ N . Let EN 1 and EN 2 be the set of non-path arcs associated with node sets N1
and N2 . We consider the forward and backward path arcs (j − 1, j) and (j, j − 1) to be in
the set of non-path arcs EN 1 and EN 2 since the node j − 1 ∈ Ni and j ∈
/ Ni for i = 1, 2. In
14

+
+
−
−
+
+
particular, EN
1 := (j, j − 1) ∪ E1j−1 , EN 1 := (j − 1, j) ∪ E1j−1 and EN 2 := (j − 1, j) ∪ Ejn ,
−
−
+
−
+
−
`
`
EN
2 := (j, j − 1) ∪ Ejn , where Ek` and Ek` are defined as ∪i=k Ei and ∪i=k Ei if k ≤ `
respectively, and as the empty set otherwise. Since the path arcs for N do not have associated
fixed-charge variables, one can assume that there exists auxiliary binary variables x̃k = 1 for
+
+
k ∈ {(j − 1, j), (j, j − 1)}. Moreover, we partition the sets S + , S − and L− into SN
1 ⊇ S1j−1 ,
−
−
−
−
+
+
−
−
−
−
SN 1 ⊇ S1j−1 , LN 1 := L1j−1 and SN 2 ⊇ Sjn , SN 2 ⊇ Sjn , LN 2 := Ljn . Then, let v1 and
v2 be the value functions defined in (F2) for the node sets N1 and N2 and the objective
+
−
+
−
u
d
u
d
sets (SN
1 , LN 1 ) and (SN 2 , LN 2 ). Moreover, let αj , αj , βj and βj be defined for j ∈ N in
+
−
−
−
recursions (7)-(10) for the set (S , S ) and recall that S = E \ (K − ∪ L− ).

Lemma 10. Let (S + , L− ) be the objective set for the node set for N = [1, n]. If αju =
+
d
u
αj−1
+ uj−1 + c(Sj+ ) or βj−1
= βjd + bj−1 + c(Sj−1
), then
+
−
+
−
v(S + , L− ) = v1 (SN
1 , LN 1 ) + v2 (SN 2 , LN 2 ),
+
+
+
where N1 = [1, j − 1], N2 = [j, n] and the arc sets are SN
1 = (j, j − 1) ∪ S1j−1 , SN 2 =
+
−
−
−
−
(j − 1, j) ∪ Sjn , SN 1 = S1j−1 , SN 2 = Sjn .

Proof. See Appendix B.1. 
Lemma 11. Let (S + , L− ) be the objective set for the node set for N = [1, n]. If αjd =
−
u
d
αj−1
+ bj−1 + dj−1 + c(Sj− ) or βj−1
= βju + uj−1 + dj−1 + c(Sj−1
), then
+
−
+
−
v(S + , L− ) = v1 (SN
1 , LN 1 ) + v2 (SN 2 , LN 2 ),
+
+
+
+
−
where N1 = [1, j − 1], N2 = [j, n] and the arc sets are SN
1 = S1j−1 , SN 2 = Sjn , SN 1 =
−
−
−
(j − 1, j) ∪ S1j−1
, SN
2 = (j, j − 1) ∪ Sjn .

Proof. See Appendix B.2. 
Lemma 12. Let (S + , L− ) be the objective set for the node set for N = [1, n]. If αju =
−
d
d
αj−1
+ uj−1 + c(Sj+ ) and βj−1
= βju + uj−1 + dj−1 + c(Sj−1
), then
−
+
−
+
v(S + , L− ) = v1 (SN
1 , LN 1 ) + v2 (SN 2 , LN 2 ),
+
+
+
+
where N1 = [1, j − 1], N2 = [j, n] and the arc sets are SN
1 = S1j−1 , SN 2 = (j − 1, j) ∪ Sjn ,
−
−
−
−
SN 1 = S1j−1 , SN 2 = (j, j − 1) ∪ Sjn .

Proof. See Appendix B.3. 
Lemma 13. Let (S + , L− ) be the objective set for the node set for N = [1, n]. If αjd =
+
u
u
αj−1
+ bj−1 + dj + c(Sj− ) and βj−1
= βjd + bj−1 + c(Sj−1
), then
+
−
+
−
v(S + , L− ) = v1 (SN
1 , LN 1 ) + v2 (SN 2 , LN 2 ),
+
+
+
+
where N1 = [1, j − 1], N2 = [j, n] and the arc sets are SN
1 = (j, j − 1) ∪ S1j−1 , SN 2 = Sjn ,
−
−
−
−
SN
1 = (j − 1, j) ∪ S1j−1 , SN 2 = Sjn .

Proof. See Appendix B.4. 
In the remainder of this section, we give necessary and sufficient conditions for path cover
and pack inequalities (14) and (17) to be facet-defining for the convex hull of P.
15

Theorem 14. Let N = [1, n], and dj ≥ 0 for all j ∈ N . If L− = ∅ and the set (S + , S − )
is a path cover for N , then the following conditions are necessary for path cover inequality
(14) to be facet-defining for conv(P):
(i) ρt (C \ {t}) < ct , for all t ∈ C,
(ii) maxt∈S + ρt (C \ {t}) > 0,
(iii) if a node j ∈ [2, n] is forward independent for set (S + , S − ), then node j − 1 is not
backward independent for set (S + , S − ),
(iv) if a node j ∈ [1, n − 1] is backward independent for set (S + , S − ), then node j + 1 is
not forward independent for set (S + , S − ),
(v) if maxt∈S + (ct − λi )+ = 0 for i = p, . . . , n for some p ∈ [2, n], then the node p − 1 is
i
not forward independent for (S + , S − ),
(vi) if maxt∈S + (ct − λi )+ = 0 for i = 1, . . . , q for some q ∈ [1, n − 1], then the node q + 1
i
is not backward independent for (S + , S − ).

Proof. (i) If for some t0 ∈ S + , ρt0 (C \ {t0 }) ≥ ct0 , then the path cover inequality with the
objective set S + \ {t0 } summed with yt0 ≤ ct0 xt0 results in an inequality at least as
strong. Rewriting the path cover inequality using the objective set S + , we obtain
X
(yt + ρt (S + \ {t})(1 − xt )) + yt0 ≤ v(S + ) − ρt0 (S + \ {t0 })(1 − xt0 ) + y(E − \ S − )
t∈S + \{t0 }

= v(S + \ {t0 }) + ρt0 (S + \ {t0 })xt0 + y(E − \ S − ).

Now, consider summing the path cover inequality for the objective set S + \ {t0 }
X
(yt + ρt (S + \ {t, t0 })(1 − xt )) ≤ v(S \ {t0 }) + y(E − \ S − ),
t∈S + \{t0 }

and yt0 ≤ ct0 xt0 . The resulting inequality dominates inequality (3) because ρt (S + \
{t}) ≤ ρt (S + \ {t, t0 }), from the submodularity of the set function v. If the assumption
of L− = ∅ is dropped, this condition extends for arcs t ∈ L− as ρt (C \ {t}) > −ct with
a similar proof.
(ii) If L− = ∅ and maxt∈S + ρt (C \ {t}) = 0, then summing flow balance equalities (1b) for
all nodes j ∈ N gives an inequality at least as strong.
(iii) Suppose a node j is forward independent for (S + , S − ) and the node j − 1 is backward
independent for (S + , S − ) for some j ∈ [2, n]. Lemmas 10–13 show that the nodes N
and the arcs C = S + ∪ L− can be partitioned into N1 = [1, j − 1], N2 = [j, n] and C1 ,
C2 such that the sum of the minimum cut values for N1 , N2 is equal to the minimum
cut for N . From Remarks 5 and 6 and Corollary 9, it is easy to see that λi for i ∈ N
will not change by the partition procedures described in Lemmas 10–13. We examine
the four cases for node j − 1 to be forward independent and node j to be backward
independent for the set (S + , S − ).
+
d
u
(a) Suppose αju = αj−1
+ uj−1 + c(Sj+ ) and βj−1
= βjd + bj−1 + c(Sj−1
). Consider
+
+
the partition procedure described in Lemma 10, where SN 1 = (j, j − 1) ∪ S1j−1
,
+
+
−
−
−
−
SN
=
(j
−
1,
j)
∪
S
,
S
=
S
,
S
=
S
.
Then,
the
path
cover
inequalities
jn
1j−1
jn
2
N1
N2
16

for nodes N1 and N2
rj−1 +

j−1 X
X

j−1
X

+
yt + (ct − λi )+ (1 − xt ) ≤ v1 (SN
)
+
y(Ei− \ Si− ) + ij−1
1

i=1 t∈S +
i

i=1

and
ij−1 +

n X
X

n
X

+
yt + (ct − λi )+ (1 − xt ) ≤ v2 (SN
)
+
y(Ei− \ Si− ) + rj−1
2

i=j t∈S +
i

i=j

summed gives
n X
X


yt + (ct − λi )+ (1 − xt ) ≤ v(S + ) + y(E − \ S − ),

i=1 t∈S +
i

which is the path cover inequality for N with the objective set S + .
−
u
d
(b) Suppose αjd = αj−1
+ bj−1 + dj−1 + c(Sj− ) and βj−1
= βju + uj−1 + dj−1 + c(Sj−1
).
+
+
+
+
Consider the partition described in Lemma 11, where SN 1 = S1j−1 , SN 2 = Sjn
,
−
−
−
−
SN 1 = (j − 1, j) ∪ S1j−1 , SN 2 = (j, j − 1) ∪ Sjn . The path cover inequalities for
nodes N1 and N2
j−1 X
X

j−1
X

+
yt + (ct − λi )+ (1 − xt ) ≤ v1 (SN
)
+
y(Ei− \ Si− )
1

i=1 t∈S +
i

i=1

and
n X
X

n
X

+
yt + (ct − λi ) (1 − xt ) ≤ v2 (SN 2 ) +
y(Ei− \ Si− ).
+

i=j t∈S +
i

i=j

summed gives the path cover inequality for nodes N and arcs C.
−
d
d
(c) Suppose αju = αj−1
+uj−1 +c(Sj+ ) and βj−1
= βju +uj−1 +dj−1 +c(Sj−1
). Consider
+
+
+
+
the partition described in Lemma 12, where SN 1 = S1j−1 , SN 2 = (j − 1, j) ∪ Sjn
,
−
−
−
−
SN 1 = S1j−1 , SN 2 = (j, j − 1) ∪ Sjn . The path cover inequalities for nodes N1 and
N2
j−1 X
X

j−1
X

+
yt + (ct − λi )+ (1 − xt ) ≤ v1 (SN
)
+
y(Ei− \ Si− ) + ij−1
1

i=1 t∈S +
i

i=1

and
ij−1 +

n X
X

n
X

+
yt + (ct − λi )+ (1 − xt ) ≤ v2 (SN
)
+
y(Ei− \ Si− ).
2

i=j t∈S +
i

i=j

summed gives the path cover inequality for nodes N and arcs C.
+
u
u
(d) Suppose αjd = αj−1
+ bj−1 + dj + c(Sj− ) and βj−1
= βjd + bj−1 + c(Sj−1
). Consider
+
+
+
+
the partition described in Lemma 13, where SN 1 = (j, j − 1) ∪ S1j−1 , SN
2 = Sjn ,
−
−
−
−
SN
1 = (j − 1, j) ∪ S1j−1 , SN 2 = Sjn . The path cover inequalities for nodes N1 and

17

N2
rj−1 +

j−1 X
X

j−1
X

+
yt + (ct − λi )+ (1 − xt ) ≤ v1 (SN
)
+
y(Ei− \ Si− )
1

i=1 t∈S +
i

and
n X
X

i=1

n
X

+
yt + (ct − λi )+ (1 − xt ) ≤ v2 (SN
)
+
y(Ei− \ Si− ) + rj−1 .
2

i=j t∈S +
i

i=j

summed gives the path cover inequality for nodes N and arcs C.
(iv) The same argument for condition (iii) above also proves the desired result here.
(v) Suppose (ct − λi )+ = 0 for all t ∈ Si+ and i ∈ [p, n] and the node p − 1 is forward
independent for some p ∈ [2, n]. Then, we partition the node set N = [1, n] into
+
u
N1 = [1, p − 1] and N2 = [p, n]. We follow Lemma 10 if βp−1
= βpd + bp−1 + c(Sp−1
)
−
+
−
+
d
u
and follow Lemma 11 if βp−1 = βp + up−1 + dp−1 + c(Sp−1 ) to define SN 1 , SN 1 , SN
2
−
and SN
2 . Remark 6 along with the partition procedure described in Lemma 10 or 11
implies that λi will remain unchanged for i ∈ N1 . The path cover inequality for nodes
N and arcs C is
y(S + ) +

p−1 X
X

(ct − λi )+ (1 − xt ) ≤ v(S + ) + y(E − \ S − ).

i=1 t∈S +
i
+
u
If βp−1
= βjd + bp−1 + c(Sp−1
), then the path cover inequality for nodes N1 and arcs
+
−
SN 1 , SN 1 described in Lemma 10 is

rp−1 +

p−1 X
X

p−1
X

+
yt + (ct − λi )+ (1 − xt ) ≤ v(SN
)
+
y(Ei− \ Si− ) + ip−1 .
1

i=1 t∈S +
i

i=1

Moreover, let m̄up and m̄dp be the values of minimum cut that goes above and below
+
−
node p for the node set N2 and arcs SN
2 , SN 2 and observe that
m̄up = βpu + up−1 and m̄dp = βpd .
Then, comparing the difference λ̄p := (m̄up − m̄dp )+ = (βpu − βpd + up−1 )+ to λp =
(mup − mdp )+ = (βpu − βpd + αpu − αpd + c(Sp+ ) − dp − c(Sp− ))+ , we observe that λ̄p ≥ λp
since αpu − αpd + c(Sp+ ) − dp − c(Sp− ) ≤ up−1 from (7)–(8). Since (ct − λp )+ = 0, then
(ct − λ̄p )+ = 0 as well. Using the same technique, it is easy to observe that λ̄i ≥ λi
+
for i ∈ [p + 1, n] as well. As a result, the path cover inequality for N2 with sets SN
2,
−
SN 2 is
ip−1 +

n
X

y(Si+ )

≤

+
v(SN
2)

+

i=p

n
X

y(Ei− \ Si− ) + rp−1 .

i=p

+
−
The path cover inequalities
and for N2 , SN
2 , SN 2 summed gives the
path cover inequality for N , S , S .
−
d
Similarly, if βp−1
= βju + up−1 + dp−1 + c(Sp−1
), the proof follows very similar to the
previous argument using Lemma 11. Letting m̄up and m̄dp be the values of minimum
+
for N1 , SN
1,
+
−

−
SN
1

18

+
−
cut that goes above and below node p for the node set N2 and arcs SN
2 , SN 2 , we get

m̄up = βpu and m̄dp + bp−1 = βpd
under this case. Now, notice that that αpu − αpd + c(Sp+ ) − dp − c(Sp− ) ≥ −bp−1 from
(7)–(8), which leads to λ̄p ≥ λp . Then the proof follows same as above.
(vi) The proof is similar to that of the necessary condition (v). We use Lemmas 12 and 13
and Remark 6 to partition the node set N and arcs S + , S − into node sets N1 = [1, q]
+
−
+
−
and N2 = [q + 1, n] for q ∈ [2, n] and arcs SN
1 , SN 1 and SN 2 , SN 2 . Next, we check the
values of minimum cut that goes above and below node q for the node set N1 and arcs
+
−
u
d
+
−
SN
1 , SN 1 . Then, observing −uq ≤ βq − αq + c(Sq ) − dq − c(Sq ) ≤ bq from (9)–(10), it
+
is easy to show that the coefficients xt for t ∈ SN
1 are equal to zero in the path cover
+
−
inequality for node set N1 . As a result, the path cover inequalities for N1 , SN
1 , SN 1
+
−
+
−
and for N2 , SN 2 , SN 2 summed gives the path cover inequality for N , S , S .


Remark 7. If the node set N consists of a single node, then the conditions (i) and (ii)
of Theorem 14 reduce to the sufficient facet conditions of flow cover inequalities given in
(Padberg et al., 1985, Theorem 4) and (van Roy and Wolsey, 1986, Theorem 6). In this
setting, conditions (iii)–(vi) are no longer relevant.
Theorem 15. Let N = [1, n], E − = ∅, dj > 0 and |Ej+ | = 1, for all j ∈ N and let the set
S + be a path cover. The necessary conditions in Theorem 14 along with
(i) (ct − λj )+ > 0 for all t ∈ Sj+ , j ∈ N ,
(ii) (ct − λj )+ < c(E + \ S + ) for all t ∈ Sj+ , j ∈ N
are sufficient for path cover inequality (14) to be facet-defining for conv(P).

Proof. Recall that dim conv(P) = 2|E| + n − 2. In this proof, we provide 2|E| + n − 2
affinely independent points that lie on the face F
(
)
X
F = (x, y, i, r) ∈ P : y(S + ) +
(ct − λj )+ (1 − xt ) = d1n .
t∈S +

First, we provide Algorithm 1 which outputs an initial feasible solution (x̄, ȳ, ī, r̄), where
all the arcs in S + have non-zero flow. Let d¯j be the effective demand on node j, that is,
the sum of dj and the minimal amount of flow that needs to be sent from the arcs in Sj+
to ensure v(S + ) = d1n . In Algorithm 1, we perform a backward pass and a forward pass
on the nodes in N . This procedure is carried out to obtain the minimal amounts of flow on
the forward and backward path arcs to satisfy the demands. For each node j ∈ N , these
minimal outgoing flow values added to the demand dj give the effective demand d¯j .
Algorithm 1 ensures that at most one of the path arcs (j − 1, j) and (j, j − 1) have
non-zero flow for all j ∈ [2, n]. Moreover, note that sufficient condition (i) ensures that all
the arcs in S + have nonzero flow. Moreover, for at least one node i ∈ N , it is guaranteed
that c(Si+ ) > d¯i . Otherwise, ρt (C) = ct for all t ∈ S + which contradicts the necessary
condition (i). Necessary conditions (iii) and (iv) ensure that īj < uj and r̄j < bj for all
19

Algorithm 1
Initialization: Let d¯j = dj for j ∈ N
for j = (n − 1)nto 1 do
+ o
,
Let ∆ = min uj , d¯j+1 − c(S + )
j+1

d¯j = d¯j + ∆, d¯j+1 = d¯j+1 − ∆,
īj = ∆.
end for
for j = 2 to n do
+
+
Let ∆ = d¯j−1 − c(Sj−1
) ,
d¯j = d¯j + ∆, d¯j−1 − ∆
r̄j−1 = ∆ − min{∆, īj−1 }
īj−1 = īj−1 − min{∆, īj−1 }
end for
ȳj = d¯j , for all j ∈ S + .
x̄j = 1 if j ∈ S + , 0 otherwise.
ȳj = x̄j = 0, for all j ∈ E − .

j = 1, . . . , n − 1. Let
e := arg max{c(Si+ ) − d¯i }
i∈N

be the node with the largest excess capacity. Also let 1j be the unit vector with 1 at position
j.
Next, we give 2|S + | affinely independent points represented by w̄t = (x̄t , ȳt , īt , r̄t ) and
t
w̃ = (x̃t , ỹt , ĩt , r̃t ) for t ∈ S + :
(i) Select w̄e = (x̄, ȳ, ī, r̄) given by Algorithm 1. Let ε > 0 be a sufficiently small value.
We define w̄t for e 6= t ∈ S + as ȳt = ȳe + ε1e − ε1t , x̄t = x̄e . If t < e, then īt = īe
and r̄jt = r̄je for j < t and for t ≥ e, r̄jt = r̄je + ε for t ≤ j < e.
(ii) In this class of affinely independent solutions, we close the arcs in S + one at a time and
P
open all the arcs in E + \ S + : x̃t = x̄ − 1t + j∈E + \S + 1j . Next, we send an additional
ȳt − (ct − λj )+ amount of flow from the arcs in S + \ {t}. This is a feasible operation
because v(C \ {t}) = d1n − (ct − λj )+ . Let (y∗ , i∗ , r∗ ) be the optimal solution of (F2)
corresponding to v(S + \{t}). Then let, ỹjt = yj∗ for j ∈ S + \{t}. Since v(C \{t}) < d1n ,
additional flow must be sent through nodes in E + \S + to satisfy flow balance equations
(1b). This is also a feasible operation, because of assumption (A.1). Then, the forward
and backward path flows ĩt and r̃t are calculated using the flow balance equations.
In the next set of solutions, we give 2|E + \S + |−1 affinely independent points represented
by ŵt = (x̂t , ŷt , ît , r̂t ) and w̌t = (x̌t , y̌t , ǐt , řt ) for t ∈ E + \ S + .
(iii) Starting with solution w̄e , we open arcs in E + \ S + , one by one. ŷt = ȳe , x̂t = x̄e + 1t ,
ît = īe , r̂t = r̄e .
(iv) If |E + \ S + | ≥ 2, then we can send a sufficiently small ε > 0 amount of flow from
arc t ∈ E + \ S + to t 6= k ∈ E + \ S + . Let this set of affinely independent points be
represented by w̌t for t ∈ E + \ S + . While generating w̌t , we start with the solution w̃e ,
20

where the non-path arc in Se+ is closed. The feasibility of this operation is guaranteed
by the sufficiency conditions (ii) and necessary conditions (iii) and (iv).
e
(a) If ỹte = ct , then there exists at least one arc t 6= m ∈ E + \S + such that 0 ≤ ỹm
< cm
+
+
e
due to sufficiency assumption (ii), then for each t ∈ E \ S such that ỹt = ct , let
Pm−1
y̌t = ỹe − ε1t + ε1m , x̌t = x̃e . If t < m, then ǐt = ĩe and řt = r̃e + ε i=t 1i . If
P
t−1
t > m, then ǐt = ĩe + ε i=m 1i and řt = r̃e .
e
e
(b) If ỹt < ct and there exists at least one arc t 6= m ∈ E + \ S + such that ỹm
= 0,
then the same point described in (a) is feasible.
e
(c) If ỹte < ct and there exists at least one arc t 6= m ∈ E + \ S + such that ỹm
= cm ,
t
e
then, we send ε amount of flow from t to m, y̌ = ỹ + ε1t − ε1m , x̌t = x̃e .
Pm−1
If t < m, then ǐt = ĩe + ε i=t 1i and řt = r̃e . If t > m, then ǐt = ĩe and
P
t−1
řt = r̃e + ε i=m 1i .
Finally, we give n − 1 points that perturb the flow on the forward path arcs (j, j + 1) for
j = 1, . . . , n − 1 represented by w̆j = (x̆j , y̆j , ĭj , r̆j ). Let k = min{i ∈ N : Si+ 6= ∅} and
` = max{i ∈ N : Si+ 6= ∅}. The solution given by Algorithm 1 guarantees īj < uj and
r̄j < bj for j = 1, . . . , n − 1 due to necessary conditions (iii) and (iv).
(v) For j = 1, . . . , n − 1, we send an additional ε amount of flow from the forward path
arc (j, j + 1) and the backward path arc (j + 1, j). Formally, the solution w̆j can be
obtained by: y̆j = ȳe , x̆j = x̄e , ĭj = īe + ε1j and r̆j = r̄e + ε1j .

Next, we identify conditions under which path pack inequality (17) is facet-defining for
conv(P).
Theorem 16. Let N = [1, n], dj ≥ 0 for all j ∈ N , let the set (S + , S − ) be a path pack
and L− = ∅. The following conditions are necessary for path pack inequality (17) to be
facet-defining for conv(P):
(i) ρj (S + ) < cj , for all j ∈ E + \ S + ,
(ii) maxt∈S − ρt (C) > 0,
(iii) if a node j ∈ [2, n] is forward independent for set (S + , S − ), then node j − 1 is not
backward independent for set (S + , S − ),
(iv) if a node j ∈ [1, n − 1] is backward independent for set (S + , S − ), then node j + 1 is
not forward independent for set (S + , S − ),
(v) if maxt∈E + \S + ρt (C) = 0 and maxt∈S − ρt (C) = 0 for i = p, . . . , n for some p ∈ [2, n],
i
i
i
then the node p − 1 is not forward independent for (S + , S − ),
(vi) if maxt∈E + \S + ρt (C) = 0 and maxt∈S − ρt (C) = 0 for i = 1, . . . , q for some q ∈
i
i
i
[1, n − 1], then the node q + 1 is not backward independent for (S + , S − ).
Proof. (i) Suppose that for some k ∈ E + \ S + , ρk (S + ) = ck . Then, recall the implicit
form of path pack inequality (17) is
X
X
y(E + \ {k}) + yk +
ρt (S + )(1 − xt ) ≤ v(S + ) +
ρt (S + )xt + ck xk + y(E − \ S − ).
t∈S −
21

k6=t∈E + \S +

Now, if we select ak = 0 in (F2), then the coefficients of xk and yk become zero and
summing the path cover inequality
X
X
ρt (S + )xt + y(E − \ S − ).
ρt (S + )(1 − xt ) ≤ v(S + ) +
y(E + \ {k}) +
t∈S −

k6=t∈E + \S +

with yk ≤ ck xk gives the first path cover inequality.
(ii) Suppose that ρj (S + ) = 0 for all j ∈ S − . Then the path pack inequality is
X

y(E + ) ≤ v(S + ) +
ρt (S + )xt + y E − \ (L− ∪ S − ) ,
t∈E + \S +

where L− = ∅. If an arc j is dropped from S − and added to L− , then v(S + ) =
v(S + ∪ {j}) since ρj (S + ) = 0 for j ∈ S − . Consequently, the path pack inequality with
S − = S − \ {j} and L− = {j}
X
X

y(E + ) +
ρt (S + ∪ {j})(1 − xt ) ≤ v(S + ) +
ρt (S + ∪ {j})xt + y E − \ (L− ∪ S − ) .
t∈S −

t∈E + \S +

But since 0 ≤ ρt (S + ∪ {j}) ≤ ρt (S + ) from submodularity of v and ρt (S + ) = 0 for all
t ∈ S − , we observe that the path pack inequality above reduces to
X

y(E + ) ≤ v(S + ) +
ρt (S + ∪ {j})xt + y E − \ (L− ∪ S − )
t∈E + \S +

and it is at least as strong as the first pack inequality for S + , S − and L− = ∅.
(iii)–(iv) We repeat the same argument of the proof of condition (iii) of Theorem 14. Suppose
a node j is forward independent for (S + , S − ) and the node j − 1 is backward
independent for (S + , S − ) for some j ∈ [2, n]. Lemmas 10–13 show that the nodes
N and the arcs C = S + ∪ L− can be partitioned into N1 = [1, j − 1], N2 = [j, n]
and C1 , C2 such that the sum of the minimum cut values for N1 , N2 is equal to
the minimum cut for N . From Remarks 5 and 6 and Corollary 9, it is easy to see
that µi for i ∈ N will not change by the partition procedures described in Lemmas
10–13. We examine the four cases for node j − 1 to be forward independent and
node j to be backward independent for the set (S + , S − ). For ease of notation, let
Q+
jk :=

k
X

X

(yt − min{µi , ct }xt )

i=j t∈E + \S +
i
i

and
Q−
jk :=

k X
X
i=j

(ct − µi )+ (1 − xt )

t∈Si−

for j ≤ k and j ∈ N , k ∈ N (and zero if j > k), where the values µi are the
coefficients that appear in the path pack inequality (17). As a result, the path pack
inequality can be written as
−
−
−
y(S + ) + Q+
1n ≤ v(C) + Q1n + y(E \ S ).
d
αj−1
+ uj−1 + c(Sj+ )

u
(a) Suppose αju =
and βj−1
=
the partition procedure described in Lemma 10,
22

(20)

+
βjd + bj−1 + c(Sj−1
). Consider
+
+
where SN
=
(j,
j
−
1) ∪ S1j−1
,
1

+
+
−
−
−
−
SN
2 = (j − 1, j) ∪ Sjn , SN 1 = S1j−1 , SN 2 = Sjn . Then, the path pack
inequalities for nodes N1 is
+
−
−
−
rj−1 + y(S1j−1
) + Q+
1j−1 ≤ v1 (C1 ) + Q1j−1 + y(E1j−1 \ S1j−1 )f + ij−1 .

(21)

Similarly, the path pack inequality for N2 is
+
−
−
−
ij−1 + y(Sjn
) + Q+
jn ≤ v2 (C2 ) + Qjn + y(Ejn \ Sjn ) + rj−1 .

(22)

Inequalities (21)–(22) summed gives the path pack inequality (20).
−
u
d
(b) Suppose αjd = αj−1
+ bj−1 + dj + c(Sj− ) and βj−1
= βju + uj−1 + dj−1 + c(Sj−1
).
+
+
+
+
Consider the partition described in Lemma 11, where SN 1 = S1j−1 , SN 2 = Sjn ,
−
−
−
−
SN
1 = (j − 1, j) ∪ S1j−1 , SN 2 = (j, j − 1) ∪ Sjn . The submodular inequality
(4) for nodes N1 where the objective coefficients of (F2) are selected as at = 1
+
−
−
for t ∈ E1j−1
, at = 0 for t = (j, j − 1), at = −1 for t ∈ EN
1 \ SN 1 and at = 0
−
for t ∈ SN 1 is
X
+
−
−
−
y(S1j−1
)+
kt (1 − xt ) + Q+
(23)
1j−1 ≤ v1 (C1 ) − Q1j−1 + y(E1j−1 \ S1j−1 ),
+
t∈SN
1

+
where kt for t ∈ SN
1 are some nonnegative coefficients. Similarly, the submodular inequality (4) for nodes N2 , where the objective coefficients of (F2)
+
are selected as at = 1 for t ∈ Ejn
, at = 0 for t = (j − 1, j), at = −1 for
−
−
−
t ∈ EN 2 \ SN 2 and at = 0 for t ∈ SN 2 is
X
+
−
−
−
y(Sjn
)+
kt (1 − xt ) + Q+
(24)
jn ≤ v2 (C2 ) − Qjn + y(Ejn \ Sjn ),
+
t∈SN
2

+
where kt for t ∈ SN
2 are some nonnegative coefficients. The sum of inequalities
(23)–(24) is at least as strong as the path pack inequality (20).
−
d
d
(c) Suppose αju = αj−1
+ uj−1 + c(Sj+ ) and βj−1
= βju + uj−1 + dj−1 + c(Sj−1
).
+
+
+
Consider the partition described in Lemma 12, where SN 1 = S1j−1 , SN 2 =
+
−
−
−
−
(j −1, j)∪Sjn
, SN
1 = S1j−1 , SN 2 = (j, j −1)∪Sjn . The submodular inequality
(4) for nodes N1 where the objective coefficients of (F2) are selected as at = 1
+
−
−
for t ∈ E1j−1
, at = 0 for t = (j, j − 1), at = −1 for t ∈ EN
1 \ SN 1 and at = 0
−
for t ∈ SN 1 is
X
+
−
−
−
y(S1j−1
)+
kt (1 − xt ) + Q+
(25)
1j−1 ≤ v1 (C1 ) − Q1j−1 + y(E1j−1 \ S1j−1 ) + ij−1 ,
+
t∈SN
1

+
where kt for t ∈ SN
1 are some nonnegative coefficients. The path pack inequality for N2 is
+
−
−
−
ij−1 + y(Sjn
) + Q+
jn ≤ v2 (C2 ) + Qjn + y(Ejn \ Sjn ).

(26)

The sum of inequalities (25)–(26) is at least as strong as inequality (20).
+
u
u
(d) Suppose αjd = αj−1
+ bj−1 + dj + c(Sj− ) and βj−1
= βjd + bj−1 + c(Sj−1
).
+
+
Consider the partition described in Lemma 13, where SN 1 = (j, j − 1) ∪ S1j−1 ,
+
+
−
−
−
−
SN
2 = Sjn , SN 1 = (j − 1, j) ∪ S1j−1 , SN 2 = Sjn . The path pack inequalities
23

for nodes N1 is
+
−
−
−
rj−1 + y(S1j−1
) + Q+
1j−1 ≤ v1 (C1 ) + Q1j−1 + y(E1j−1 \ S1j−1 ).

(27)

The submodular inequality (4) for nodes N2 where the objective coefficients of
+
(F2) are selected as at = 1 for t ∈ Ejn
, at = 0 for t = (j − 1, j), at = −1 for
−
−
−
t ∈ EN 2 \ SN 2 and at = 0 for t ∈ SN 2 is
X
+
−
−
−
y(Sjn
)+
kt (1 − xt ) + Q+
(28)
jn ≤ v2 (C2 ) − Qjn + y(Ejn \ Sjn ) + rj−1 ,
+
t∈SN
2

+
where kt for t ∈ SN
2 are some nonnegative coefficients. The sum of inequalities
(27)–(28) is at least as strong as the path pack inequality (20).
(v) Suppose (ct − µi )+ = 0 for all t ∈ Si− and i ∈ [p, n] and the node p − 1 is forward
independent. Then, we partition the node set N = [1, n] into N1 = [1, p − 1] and
+
u
N2 = [p, n]. We follow Lemma 10 if βp−1
= βpd + bp−1 + c(Sp−1
) and follow Lemma
−
+
−
+
−
d
u
11 if βp−1 = βp + up−1 + dp−1 + c(Sp−1 ) to define SN 1 , SN 1 , SN 2 and SN
2 . Remark
6 along with the partition procedure described in Lemma 10 or 11 implies that µi
will remain unchanged for i ∈ N1 .
+
u
If βp−1
= βjd + bp−1 + c(Sp−1
), then the coefficients µi of the path pack inequality
+
−
for nodes N1 and arcs SN 1 , SN 1 described in Lemma 10 is the same as the coefficients
of the path pack inequality for nodes N and arcs S + , S − . Moreover, let m̄up and
m̄dp be the values of minimum cut that goes above and below node p for the node
+
−
set N2 and arcs SN
2 , SN 2 and observe that

m̄up = βpu + up−1 and m̄dp = βpd .
Then, comparing the difference µ̄p := (m̄dp − m̄up )+ = (βpd − βpu − up−1 )+ to µp =
(mdp − mup )+ = (βpd − βpu + αpd − αpu − c(Sp+ ) + dp + c(Sp− ))+ , we observe that µ̄p ≥ µp
since αpd − αpu − c(Sp+ ) + dp + c(Sp− ) ≥ −up−1 from (7)–(8). Since (ct − µp )+ = 0,
then (ct − µ̄p )+ = 0 as well. Using the same technique, it is easy to observe that
µ̄i ≥ µi for i ∈ [p + 1, n] as well. As a result, the path pack inequality for N2 with
+
−
+
sets SN
2 , SN 2 , summed with the path pack inequality for nodes N1 and arcs SN 1 ,
−
+
−
SN
1 give the path pack inequality for nodes N and arc S , S .
−
d
u
Similarly, if βp−1 = βj + up−1 + dp−1 + c(Sp−1 ), the proof follows very similar
to the previous argument using Lemma 11. Letting m̄up and m̄dp be the values of
+
minimum cut that goes above and below node p for the node set N2 and arcs SN
2,
−
SN 2 , we get
m̄up = βpu and m̄dp + bp−1 = βpd
under this case. Now, notice that that αpd − αpu − c(Sp+ ) + dp + c(Sp− ) ≤ bp−1 from
(7)–(8), which leads to µ̄p ≥ µp . Then the proof follows same as above.
(vi) The proof is similar to that of the necessary condition (v) above. We use Lemmas
12–13 and Remark 6 to partition the node set N and arcs S + , S − into node sets
+
−
+
−
N1 = [1, q] and N2 = [q + 1, n] and arcs SN
1 , SN 1 and SN 2 , SN 2 . Next, we check
the values of minimum cut that goes above and below node q for the node set N1
+
−
d
u
+
−
and arcs SN
1 , SN 1 . Then, observing −bq ≤ βq − αq − c(Sq ) + dq + c(Sq ) ≤ uq from
−
+
+
(9)–(10), it is easy to see that the coefficients of xt for t ∈ SN 1 and t ∈ EN
1 \ SN 1
24

are equal to zero in the path pack inequality for node set N1 . As a result, the path
+
−
+
−
pack inequalities for N1 , SN
1 , SN 1 and for N2 , SN 2 , SN 2 summed gives the path
+
−
pack inequality for N , S , S .


Remark 8. If the node set N consists of a single node, then the conditions (i) and (ii) of
Theorem 16 reduce to the necessary and sufficient facet conditions of flow pack inequalities
given in (Atamtürk, 2001, Proposition 1). In this setting, conditions (iii)–(vi) are no longer
relevant.
Theorem 17. Let N = [1, n], E − = ∅, dj > 0 and |Ej+ | = 1, for all j ∈ N and let the
objective set S + be a path pack for N . The necessary conditions in Theorem 16 along with
(i) for each j ∈ E + \ S + , either S + ∪ {j} is a path cover for N or ρj (S + ) = 0,
(ii) for each t ∈ S + , there exists jt ∈ E + \ S + such that S + \ {t} ∪ {jt } is a path cover for
N,
(iii) for each j ∈ [1, n − 1], there exists kj ∈ E + \ S + such that the set S + ∪ {kj } is a path
cover and neither node j is backward independent nor node j +1 is forward independent
for the set S + ∪ {kj }
are sufficient for path pack inequality (17) to be facet-defining for conv(P).
Proof. We provide 2|E| + n − 2 affinely independent points that lie on the face:




X
F = (x, y, i, r) ∈ P : y(S + ) +
(yt − min{µj , ct }xt ) = c(S + ) .


+
+
t∈E \S

Let (y∗ , i∗ , r∗ ) ∈ Q be an optimal solution to (F2). Since S + is a path pack and E − = ∅,
v(S + ) = c(S + ). Then, notice that yt∗ = ct for all t ∈ S + . Moreover, let e be the arc
with largest capacity in S + , ε > 0 be a sufficiently small value and 1j be the unit vector
with 1 at position j. First, we give 2|E + \ S + | affinely independent points represented by
z̄ t = (x̄t , ȳt , īt , r̄t ) and z̃ t = (x̃t , ỹt , ĩt , r̃t ) for t ∈ E + \ S + .
(i) Let t ∈ E + \ S + , where S + ∪ {t} is a path cover for N . The solution z̄ t has arcs
in S + ∪ {t} open, x̄tj = 1 for j ∈ S + ∪ {t}, 0 otherwise, ȳjt = yj∗ for j ∈ S + and
ȳtt = ρt (S + ), 0 otherwise. The forward and backward path arc flow values ītj and r̄jt
can then be calculated using flow balance equalities (1b) where at most one of them
can be nonzero for each j ∈ N . Sufficiency condition (i) guarantees the feasibility of
z̄ t .
(ii) Let t ∈ E + \ S + , where ρt (S + ) = 0 and let t 6= ` ∈ E + \ S + , where S + ∪ {`} is a path
cover for N . The solution z̄ t has arcs in S + ∪{t, `} open, x̄tj = 1 for j ∈ S + ∪{t, `}, and
0 otherwise, ȳjt = yj∗ for j ∈ S + , ȳtt = 0, ȳ`t = ρ` (S + ), and 0 otherwise. The forward
and backward path arc flow values ītj and r̄jt can then be calculated using flow balance
equalities (1b) where at most one of them can be nonzero for each j ∈ N . Sufficiency
condition (i) guarantees the feasibility of z̄ t .
25

(iii) The necessary condition (i) ensures that ρt (S + ) < ct , therefore ȳtt < ct . In solution
z̃ t , starting with z̄ t , we send a flow of ε from arc t ∈ E + \ S + to e ∈ S + . Let
Pt−1
ỹt = ȳt + ε1t − ε1e and x̃t = x̄t . If e < t, then r̃t = r̄t + ε i=e 1i , ĩt = īt and if e > t,
Pe−1
then ĩt = īt + ε i=t 1i , r̃t = r̄t .
Next, we give 2|S + | − 1 affinely independent feasible points ẑ t and ž t corresponding to
t ∈ S + that are on the face F . Let k be the arc in E + \ S + with largest capacity.
(iv) In the feasible solutions ẑ t for e 6= t ∈ S + , we open arcs in S + ∪ {k} and send an
ε flow from arc k to arc t. Let ŷt = ȳk + ε1k − ε1t and x̂t = x̄k . If t < k, then
Pk−1
Pt−1
r̂t = r̄k + ε i=t 1i , ît = īk and if t > k, then ît = īk + ε i=k 1i , r̂t = r̄k .
(v) In the solutions ž t for t ∈ S + , we close arc t and open arc jt ∈ E + \ S + that is
introduced in the sufficient condition (ii). Then, x̌tj = 1 if j ∈ S + \ {t} and if j = jt
and x̌tj = 0 otherwise. From sufficient condition (ii), there exists y̌jt values that satisfy
the flow balance equalities (1b). Moreover, these y̌jt values satisfy inequality (17) at
equality since both S + ∪ {jt } and S + \ {t} ∪ {jt } are path covers for N . Then, the
forward and backward path arc flows are found using flow balance equalities where at
most one of ǐtj and řjt are nonzero for each j ∈ N .
Finally, we give n−1 points z̆ j corresponding to forward and backward path arcs connecting
nodes j and j + 1.
(vi) In the solution set z̆ j for j = 1, . . . , n − 1, starting with solution z̄ kj , where kj is
introduced in the sufficient condition (iii), we send a flow of ε from both forward path
arc (j − 1, j) and backward path arc (j, j − 1). Since the sufficiency condition (iii)
k
k
ensures that r̄j j < bj and īj j < uj , the operation is feasible. Let y̆j = ȳkj , x̆j = x̄kj ,
ĭj = īkj + ε1j and r̆j = r̄kj + ε1j .

5. Computational study
We test the effectiveness of path cover and path pack inequalities (14) and (17) by embedding them in a branch-and-cut framework. The experiments are ran on a Linux workstation
with 2.93 GHz Intel R CoreTM i7 CPU and 8 GB of RAM with 1 hour time limit and 1 GB
memory limit. The branch-and-cut algorithm is implemented in C++ using IBM’s Concert
Technology of CPLEX (version 12.5). The experiments are ran with one hour limit on
elapsed time and 1 GB limit on memory usage. The number of threads is set to one and the
dynamic search is disabled. We also turn off heuristics and preprocessing as the purpose is
to see the impact of the inequalities by themselves.
Instance generation. We use a capacitated lot-sizing model with backlogging, where constraints (1b) reduce to:
ij−1 − rj−1 + yj − ij + rj = dj ,

j ∈ N.

Let n be the total number of time periods and f be the ratio of the fixed cost to the variable
cost associated with a non-path arc. The parameter c controls how large the non-path
arc capacities are with respect to average demand. All parameters are generated from a
discrete uniform distribution. The demand for each node is drawn from the range [0, 30]
26

¯ 1.25 × c × d],
¯ where d¯
and non-path arc capacities are drawn from the range [0.75 × c × d,
is the average demand over all time periods. Forward and backward path arc capacities are
¯ 2.0 × d]
¯ and [0.3 × d,
¯ 0.8 × d],
¯ respectively. The variable costs pt , ht
drawn from [1.0 × d,
and gt are drawn from the ranges [1, 10], [1, 10] and [1, 20] respectively. Finally, fixed costs
ft are set equal to f × pt . Using these parameters, we generate five random instances for
each combination of n ∈ {50, 100, 150}, f ∈ {100, 200, 500, 1000} and c ∈ {2, 5, 10}.
Finding violated inequalities. Given a feasible solution (x∗ , y∗ , i∗ , r∗ ) to a linear programming (LP) relaxation of (F1), the separation problem aims to find sets S + and L− that
maximize the difference
X
X
y ∗ (S + ) − y ∗ (E − \ L− ) +
(ct − λj )+ (1 − x∗t ) −
(min{λj , ct })x∗t − d1n − c(S − )
t∈L−

t∈S +

for path cover inequality (14) and sets S + and S − that maximize
X
X
y ∗ (S + ) − y ∗ (E − \ S − ) −
min{ct , µj }x∗t +
(ct − µj )+ (1 − xt ) − c(S + )
t∈S −

t∈E + \S +

for path pack inequality (17). We use the knapsack relaxation based heuristic separation
strategy described in (Wolsey and Nemhauser, 1999, pg. 500) for flow cover inequalities to
choose the objective set S + with a knapsack capacity d1n . Using S + , we obtain the values
λj and µj for each j ∈ N and let S − = ∅ for path cover and path pack inequalities (14)
and (17). For path cover inequalities (14), we add an arc t ∈ E − to L− if λj x∗t < yt∗ and
λj < ct . We repeat the separation process for all subsets [k, `] ⊆ [1, n].
Results. We report multiple performance measures. Let zINIT be the objective function
value of the initial LP relaxation and zROOT be the objective function value of the LP
relaxation after all the valid inequalities added. Moreover, let zUB be the objective function
value of the best feasible solution found within time/memory limit among all experiments for
ROOT
INIT
, root gap= 100 × zUB −z
. We compute
an instance. Let init gap= 100 × zUBz−z
zUB
UB
the improvement of the relaxation due to adding valid inequalities as gap imp= 100 ×
init gap−root gap
−zLB
,
. We also measure the optimality gap at termination as end gap = zUBzUB
init gap
where zLB is the value of the best lower bound given by CPLEX. We report the average
number of valid inequalities added at the root node under column cuts, average elapsed
time in seconds under time, average number of branch-and-bound nodes explored under
nodes. If there are instances that are not solved to optimality within the time/memory
limit, we report the average end gap and the number of unsolved instances under unslvd
next to time results. All numbers except initial gap, end gap and time are rounded to the
nearest integers.
In Tables 1, 2 and 3, we present the performance with the path cover (14) and path pack
(17) inequalities under columns spi. To understand how the forward and backward path
arc capacities affect the computational performance, we also apply them to the single node
relaxations obtained by merging a path into a single node, where the capacities of forward
and backward path arcs within a path are considered to be infinite. In this case, the path
inequalities reduce to the flow cover and flow pack inequalities. These results are presented
under columns mspi.
27

Table 1. Effect of path size on the performance.
p≤5

p=1
n

f

c

init gap imp cuts

gap imp

p ≤ 0.5 × n
cuts

gap imp

gap (m)spi (m)spi spi mspi spi mspi spi

mspi

cuts

p≤n
gap imp

cuts

spi mspi spi mspi spi mspi

2 14.8
5 44.3
10 58.3

34%
56%
60%

21
52
54

87% 52% 212 106 97%
99% 69% 303 148 99%
96% 70% 277 147 99%

2 14.5
200 5 49.8
10 66.3

32%
43%
38%

22
44
47

81% 57% 257 133 96% 61% 1965 241 96% 61% 2387 241
99% 57% 378 162 100% 57% 1264 171 100% 57% 1420 171
98% 50% 392 169 99% 51% 1235 197 99% 51% 1283 197

2 19.1
500 5 54.4
10 73.0

23%
35%
34%

19
36
43

77% 48% 266 128 90% 49% 2286 222 90% 49% 3249 222
99% 49% 522 185 100% 49% 1981 205 100% 49% 2074 205
99% 40% 498 196 99% 40% 1336 236 99% 40% 1445 236

2 14.6
1000 5 59.7
10 76.9

18%
31%
30%

15
36
41

73% 39% 264 99 83% 40% 2821 211 83% 40% 3918 212
98% 45% 487 201 100% 45% 2077 239 100% 45% 2329 239
100% 36% 529 215 100% 37% 1935 268 100% 37% 2149 268

Average: 45.5

36%

36

92% 51% 365 157 97% 52% 1609 206 97% 52% 1894 206

100

50

52% 1164 158 97% 52% 1233 158
69% 664 151 99% 69% 664 151
70% 574 167 99% 70% 574 167

In Table 1, we focus on the impact of path size on the gap improvement of the path
cover and path pack inequalities for instances with n = 50. In the columns under p = 1,
we obtain the same results for both mspi and spi since the paths are singleton nodes.. We
present these results under (m)spi. In columns p ≤ q, we add valid inequalities for paths of
size 1, . . . , q and observe that as the path size increases, the gap improvement of the path
inequalities increase rapidly. On average 97% of the initial gap is closed as longer paths
are used. On the other hand, flow cover and pack inequalities from merged paths reduce
about half of the initial gap. These results underline the importance of exploiting path
arc capacities on strengthening the formulations. We also observe that the increase in gap
improvement diminishes as path size grows. We choose a conservative maximum path size
limit of 0.75 × n for the experiments reported in Tables 2, 3 and 4.
In Table 2, we investigate the computational performance of path cover and path pack
inequalities independently. We present the results for path cover inequalities under columns
titled cov, for path pack inequalities under pac and for both of them under the columns
titled spi. On average, path cover and path pack inequalities independently close the gap
by 63% and 53%, respectively. However, when used together, the gap improvement is 96%,
which shows that the two classes of inequalities complement each other very well.
In Table 3, we present other performance measures as well for instances with 50, 100,
and 150 nodes. We observe that the forward and backward path arc capacities have a large
impact on the performance level of the path cover and pack inequalities. Compared to flow
cover and pack inequalities added from merged paths, path cover and path pack inequalities
reduce the number of nodes and solution times by orders of magnitude. This is mainly due
to better integrality gap improvement (50% vs 95% on average).
28

In Table 4, we examine the incremental effect of path cover and path pack inequalities
over the fixed-charge network cuts of CPLEX, namely flow cover, flow path and multicommodity flow cuts. Under cpx, we present the performance of flow cover, flow path and
multi-commodity flow cuts added by CPLEX and under cpx spi, we add path cover and
path pack inequalities addition to these cuts. We observe that with the addition of path
cover and pack inequalities, the gap improvement increases from 86% to 95%. The number
of branch and bound nodes explored is reduced about 900 times. Moreover, with path cover
and path pack inequalities the average elapsed time is reduced to almost half and the total
number of unsolved instances reduces from 13 to 6 out of 180 instances.
Tables 1, 2, 3 and 4 show that submodular path inequalities are quite effective in tackling lot-sizing problems with finite arc capacities. When added to the LP relaxation, they
improve the optimality gap by 95% and the number of branch and bound nodes explored
decreases by a factor of 1000. In conclusion, our computational experiments indicate that
the use of path cover and path pack inequalities is beneficial in improving the performance
of the branch-and-cut algorithms.

Table 2. Effect of path cover (cov) and path pack (pac) inequalities when
used separately and together (spi).
gap imp

nodes

cuts

time

c

init
gap

cov

2
100 5
10

14.8
44.3
58.3

62% 18%
75% 37%
77% 39%

96%
97%
93%

273 6258
7 759
319 12366
9 357
213 29400 63 290

13 1151 0.3 0.6
25 435 0.1 1.0
11 386 0.1 2.1

0.2
0.1
0.1

2
200 5
10
50

14.5
49.8
66.3

73% 34% 92%
67% 38% 100%
61% 48% 97%

148 3268 18 1593
576 11525
3 736
226 8799 14 619

41 2469 0.7 0.3
36 1022 0.4 0.9
32 739 0.2 0.7

0.6
0.1
0.1

2
500 5
10

19.1
54.4
73.0

57% 57%
56% 75%
59% 65%

92% 635 1825 19 1587 316 2577 1.6 0.3
99% 348 363
1 902 148 1164 0.3 0.1
97% 8410 5284 11 727 67 698 3.0 0.5

1.0
0.1
0.1

2
1000 5
10

14.6
59.7
76.9

61% 65% 90% 278 258 60 1362 427 2094 0.8 0.3
59% 81% 100% 1063 208
2 1673 364 1792 1.3 0.1
51% 77% 99% 3791 1452
5 1202 155 1032 2.1 0.2

0.9
0.1
0.1

45.5 63% 53% 96% 1357 6751 18 984 136 1297 0.9 0.6

0.3

n

f

Average:

pac

spi

cov

29

pac spi cov pac

spi cov pac spi

Table 3. Comparison of path inequalities applied to paths (spi) versus
applied to merged paths (mspi).
gapimp
n

50

100

150

f

c

nodes

init
spi mspi spi
gap

cuts

mspi

spi mspi

time (endgap:unslvd)
spi

mspi

2 14.8 96% 52%
100 5 44.3 97% 69%
10 58.3 93% 70%

7
9
63

430 1151
553 435
468 386

195
146
160

0.2
0.1
0.1

0.2
0.1
0.1

2 14.5 92% 59%
200 5 49.8 100% 57%
10 66.3 97% 53%

18
3
14

330 2469
1112 1022
615 739

226
176
173

0.6
0.1
0.1

0.2
0.3
0.2

2 19.1 92% 43%
500 5 54.4 99% 48%
10 73.0 97% 48%

19
1
11

2041 2577
705 1164
5659 698

238
214
248

1.0
0.1
0.1

0.7
0.3
1.4

2 14.6 90% 45%
1000 5 59.7 100% 50%
10 76.9 99% 40%

60
2
5

612 2094
2265 1792
9199 1032

301
241
314

0.9
0.1
0.1

0.4
0.7
2.3

2 13.9 95% 65% 39
100 5 42.2 98% 70% 19
10 57.8 94% 59% 230

7073 3114
20897 1337
395277 1298

410
297
346

1.3
0.2
0.4

3.2
4.8
88.2

2 16.1 89% 56% 290
151860 6919
200 5 47.6 99% 55%
7
455192 2355
10 65.7 95% 54% 104 4130780 1872

478
331
399

11.0
0.3
0.5

58.4
126.1
962.3 (1.1:1)

2 17.5 84% 36% 1047
956745 11743
500 5 53.9 99% 41%
4
332041 3874
10 72.9 96% 42% 34 1175647 1495

475
444
474

47.7
0.4
0.3

390.9
115.5
352.5

2 17.9 91% 41% 173
57147 10919
1000 5 58.5 100% 45%
1
284979 3261
10 75.7 97% 36% 88 3158262 2358

570
501
657

21.3
23.0
0.3
92.8
0.5 1047.0 (0.7:1)

2 13.2 94% 64% 336
163242 5159
100 5 44.8 99% 65% 17 3024118 2087
10 56.9 95% 65% 404 7254052 1492

704
431
476

11.3 107.6
0.5 929.6
0.9 2087.3 (0.7:1)

2 14.7 92% 53% 519 2772494 12636
200 5 48.1 99% 55% 15 3802938 2462
10 65.2 95% 50% 330 9377122 2047

744
508
567

27.2 1390.6 (0.1:1)
0.6 1483.0 (1.2:2)
0.9 3585.9 (8.2:5)

2 19.3 86% 33% 7927 7619674 22275
500 5 54.4 100% 45%
7 7873043 4927
10 72.3 97% 41% 250 10219548 2678

792 1087.3 3165.6 (4.0:4)
641
0.8 2813.6 (4.3:3)
713
1.2 3422.8 (11.0:5)

2 19.6 88% 34% 2824 7316675 33729
1000 5 57.5 100% 39%
2 9661586 6710
10 75.8 96% 37% 99 9910056 3981

724 804.8 3260.3 (2.5:3)
709
0.8 3578.9 (9.7:5)
829
1.2 3412.3 (15.2:5)

Average: 45.2 95% 50% 416 2504012 4619 440

30

56.3

903.0 (1.6:36)

Table 4. Effectiveness of the path inequalities when used together with
CPLEX’s network cuts.
gapimp
n

f

c

nodes

init
cpx spi cpx cpx spi
gap

time (endgap:unslvd)

cpx

cpx spi

cpx

2
100 5
10

13.9
42.2
57.8

96%
99%
99%

85%
97%
93%

35
5
10

1715
75
2970

1.0
0.2
0.3

0.5
0.1
0.6

2
200 5
10

16.1
47.6
65.7

90%
99%
97%

79%
95%
89%

288
7
61

9039
52
3186

6.6
0.3
0.4

2.1
0.1
0.7

2
500 5
10

17.5
53.9
72.9

85%
99%
98%

63%
94%
89%

1232
6
11

455068
92
4621

57.3
0.4
0.4

95.2
0.1
0.9

2
1000 5
10

17.9
58.5
75.7

91%
100%
97%

76%
93%
85%

173
1
117

18109
156
5297

22.2
0.3
0.7

3.6
0.1
1.0

2
100 5
10

13.2
44.8
56.9

94%
100%
99%

86%
97%
92%

365
5
16

60956
119
15929

9.7
0.4
0.5

19.0
0.1
3.9

2
200 5
10

14.7
48.1
65.2

92%
99%
97%

80%
96%
91%

954
11
181

216436
284
3992

44.9
0.5
0.9

66.7
0.2
1.2

2
500 5
10

19.3
54.4
72.3

86%
100%
97%

69%
94%
88%

7647 4943603 1049.9
5
5434
0.8
141
141211
1.4

2
1000 5
10

19.6
57.5
75.8

88%
100%
96%

71%
90%
89%

3051 2788993 917.4 (0.2:1)
3
4322
0.8
196
10588
2.5

619.4 (0.4:1)
1.2
2.8

2
100 5
10

14.1
42.7
57.5

94%
100%
99%

82%
97%
93%

1623
8
26

384.0
0.1
13.8

2
200 5
10

16.3
48.0
65.0

89%
99%
98%

78%
95%
90%

4279 5634851 259.9
13
1310
0.9
128
163145
1.2

2
500 5
10

16.3
54.5
72.0

88%
99%
96%

72%
93%
90%

8083 6805861 1226.3 (0.3:1) 2137.6 (0.7:3)
7
6606
1.6
2.2
376
900152
3.2
302.4

2
1000 5
10

18.0
57.9
75.6

82%
100%
96%

63%
94%
84%

13906 9894589 3000.5 (1.2:4) 2835.9 (3.0:5)
4
1977
3.4
0.8
704 6127929 15.0
1785.0 (1.8:2)

Average: 45.0

95%

86%

1213 1087194 185.1 (0.0:6) 320.2 (0.2:13)

100

150

200

31

864841
213
45263

32.2
0.5
0.7

1215.1 (0.2:1)
1.6
35.9

1940.4 (0.1:1)
0.5
52.3

Acknowledgements
A. Atamtürk and Birce Tezel are supported, in part, the National Science Foundation
grant #0970180 and by grant FA9550-10-1-0168 from the Office of the Assistant Secretary
of Defense for Research and Engineering. Simge Küçükyavuz is supported, in part, by
the National Science Foundation grant #1055668. The authors are also thankful to the
Associate Editor and anonymous referees for their constructive feedback that improved the
paper substantially.

References
Atamtürk, A. (2001). Flow pack facets of the single node fixed–charge flow polytope. Operations Research Letters, 29:107–114.
Atamtürk, A. and Küçükyavuz, S. (2005). Lot sizing with inventory bounds and fixed costs.
Operations Research, 53:711 – 730.
Atamtürk, A. and Muñoz, J. C. (2004). A study of the lot–sizing polytope. Mathematical
Programming, 99:43–65.
Gade, D. and Küçükyavuz, S. (2011). A note on lot-sizing with fixed charges on stocks: the
convex hull. Discrete Optimization, 8:385–392.
Gu, Z., Nemhauser, G. L., and Savelsbergh, M. W. P. (1999). Lifted flow cover inequalities
for mixed 0–1 integer programs. Mathematical Programming, 85:439–467.
King, V., Rao, S., and Tarjan, R. (1994). A faster deterministic maximum flow algorithm.
Journal of Algorithms, 17(3):447–474.
Küçükyavuz, S. and Pochet, Y. (2009). Uncapacitated lot sizing with backlogging: the
convex hull. Mathematical Programming, 118(1):151–175.
Ortega, F. and Wolsey, L. A. (2003). A branch-and-cut algorithm for the single-commodity,
uncapacitated, fixed-charge network flow problem. Networks, 41:143–158.
Padberg, M. W., van Roy, T. J., and Wolsey, L. A. (1985). Valid linear inequalities for fixed
charge problems. Operations Research, 33:842–861.
Pochet, Y. and Wolsey, L. A. (1988). Lot-size models with backlogging: Strong reformulations and cutting planes. Mathematical Programming, 40(1-3):317–335.
Pochet, Y. and Wolsey, L. A. (1994). Polyhedra for lot-sizing with Wagner–Whitin costs.
Mathematical Programming, 67(1-3):297–323.
Rardin, R. L. and Wolsey, L. A. (1993). Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems. European
Journal of Operational Research, 71:95–109.
Stallaert, J. I. A. (1997). The complementary class of generalized flow cover inequalities.
Discrete Applied Mathematics, 77:73–80.
van Roy, T. J. and Wolsey, L. A. (1985). Valid inequalities and separation for uncapacitated
fixed charge networks. Operations Research Letters, 4:105–112.
van Roy, T. J. and Wolsey, L. A. (1986). Valid inequalities for mixed 0–1 programs. Discrete
Applied Mathematics, 14:199–213.
Van Vyve, M. (2013). Fixed-charge transportation on a path: optimization, LP formulations
and separation. Mathematical Programming, 142:371–395.
32

Van Vyve, M. and Ortega, F. (2004). Lot-sizing with fixed charges on stocks: the convex
hull. Discrete Optimization, 1:189–203.
Wolsey, L. A. (1989). Submodularity and valid inequalities in capacitated fixed charge
networks. Operations Research Letters, 8:119–124.
Wolsey, L. A. and Nemhauser, G. L. (1999). Integer and Combinatorial Optimization. Wiley
Series in Discrete Mathematics and Optimization. Wiley.

Appendix A. Equivalency of (F2) to the maximum flow problem
In Section 3, we showed the maximum flow equivalency of v(S + , L− ) under the assumption that dj ≥ 0 for all j ∈ N . In this section, we generalize the equivalency for the paths
where dj < 0 for some j ∈ N .
Observation 2. If dj < 0 for some j ∈ N , one can represent the supply amount as a dummy
arc incoming to node j (i.e., added to Ej+ ) with a fixed flow and capacity of −dj and set
the modified demand of node j to be dj = 0.
Given the node set N with at least one supply node, let T (N ) be the transformed path
using Observation 2. Transformation T ensures that the dummy supply arcs are always
open. As a result, they are always in the set S + . We refer to the additional constraints
that fix the flow to the supply value on dummy supply arcs as fixed-flow constraints. Notice
that, v(S + , L− ) computed for T (N ) does not take fixed-flow constraints into account. In
the next proposition, for a path structure, we show that there exists at least one optimal
solution to (F2) such that the fixed-flow constraints are satisfied.
Proposition 18. Suppose that dj < 0 for some j ∈ N . If (F2) for the node set N is
feasible, then it has at least one optimal solution that satisfies the fixed-flow constraints.
Proof. We need to show that v(S + , L− ) has an optimal solution where the flow at the
dummy supply arcs is equal to the supply values. The transformation T makes Proposition
1 applicable to the modified path T (N ). Let Y be the set of optimal solutions of (F2). Then,
there exists a solution (y∗ , i∗ , r∗ ) ∈ Y where yt∗ = 0 for t ∈ E − \ (S − ∪ L− ). Let p ∈ Sj+
represent the index of the dummy supply arc with cp = −dj . If yp∗ < cp , then satisfying the
fixed-flow constraints require pushing flow through the arcs in E − \ L− . We use Algorithm
2 to construct an optimal solution with yp∗ = cp . Note that each arc in Ek− \ L−
k for k ∈ N
appear in (F2) with the same coefficients, therefore we merge these outgoing arcs into one
P
in Algorithm 2. We represent the merged flow and capacity by Ȳk− = t∈E − \(S − ∪L− ) yt∗
k
k
k

and C̄k = c Ek− \ (Sk− ∪ L−
k ) for k ∈ N .

Proposition 18 shows that, under the presence of supply nodes, transformation T both
captures the graph’s structure and does not affect (F1)’s validity. As a result, Propositions
1 and 2 become relevant to the transformed path and submodular path inequalities (14)
and (17) are also valid for paths where dj < 0 for some j ∈ N .
33

Algorithm 2
J : Set of supply nodes in N where the nodes are sorted with respect to their order in N .
(y∗ , i∗ , r∗ ) ∈ Y: yt∗ = 0 for all t ∈ E − .
for q ∈ J do
Let p be the dummy supply arc in Sq+
∆ = cp − yp∗
for j = q to n do
Ȳj− = Ȳj− + min{C̄j − Ȳj− , ∆}
∆ = ∆ − min{C̄j − Ȳj− , ∆}
i∗j = i∗j + ∆
if i∗j > uj then
∆ = i∗j − uj
i∗j = uj
Let k := j
break inner loop
end if
end for
if ∆ > 0 then
for j = k to 1 do
Ȳj− = Ȳj− + min{C̄j − Ȳj− , ∆}
∆ = ∆ − min{C̄j − Ȳj− , ∆}
rj∗ = rj∗ + ∆
if rj∗ > bj then
∆ = rj∗ − bj
break inner loop
end if
end for
end if
if ∆ > 0 then
(F2) is infeasible for the node set N .
end if
end for

Appendix B. Proofs
+
−
B.1. Proof of Lemma 10. Recall that C = S + ∪ L− and let C1 = SN
1 ∪ LN 1 and
+
−
C2 = SN
2 ∪ LN 2 . In (13), we showed that the value of the minimum cut is

v(C) = mi = min{αiu + βiu − c(Si+ ), αid + βid − di − c(Si− )}
for all i ∈ N . For node set N1 and the arc set C1 , the value of the minimum cut is
u
d
v1 (C1 ) = min{αj−1
+ bj−1 , αj−1
}.
{u,d}

This is because of three observations: (1) the values αi
for i ∈ [1, j − 2] are the same
+
for the node sets N1 and N , (2) for the arc set C1 the set Sj−1 now includes the backward
path arc (j, j − 1) and (3) node j − 1 is the last node of the first path. Similarly, for node
34

set N2 and the arc set C2 , the value of the minimum cut is
v2 (C2 ) = min{βju + uj−1 , βjd }.
{u,d}

For nodes N2 and the arc set C2 , (1) the values βi
for i ∈ [j + 1, n] are the same for the
node sets N2 and N , (2) for the arc set C2 the set Sj+ now includes the forward path arc
(j − 1, j) and (3) node j is the first node of the second path.
d
d
Now, if αju = αj−1
+uj−1 +c(Sj+ ), then αjd = αj−1
+dj +c(Sj− ) from equations in (7)–(8).
d
Then, rewriting v(C) = mj and v1 (C1 ) in terms of αj−1
:
d
v(C) = αj−1
+ min{βju + uj−1 , βjd }

and
d
v1 (C1 ) = αj−1
.

As a result, the values v1 (C1 ) and v2 (C2 ) summed gives the value v(C) under the assumption
for the value of αju .
+
−
u
d
Similarly, if βj−1
= βjd + bj−1 + c(Sj−1
), then βj−1
= βjd + dj−1 + c(Sj−1
) from equations
in (9)–(10). Then, rewriting v(C) = mj−1 and v2 (C2 ) in terms of βjd :
u
d
v(C) = βjd + min{αj−1
+ bj−1 , αj−1
}

and
v2 (C2 ) = βjd .
As a result, the values v1 (C1 ) and v2 (C2 ) summed gives the value v(C) under the assumption
u
for the value of βj−1
.
B.2. Proof of Lemma 11. The proof follows closely to that of Lemma 10. Let C =
+
−
+
−
S + ∪ L− , C1 = SN
1 ∪ LN 1 and C2 = SN 2 ∪ LN 2 . For node set N1 and the arc set C1 , the
value of the minimum cut is
u
d
v1 (C1 ) = min{αj−1
, αj−1
+ uj−1 },
−
−
where uj−1 is added because c(SN
1 ) = c(S1j−1 ) + uj−1 . Similarly, for node set N2 and the
arc set C2 , the value of the minimum cut is

v2 (C2 ) = min{βju , βjd + bj−1 },
−
−
where bj−1 is added because c(SN
2 ) = c(Sjn ) + bj−1 .
u
u
Now, if αjd = αj−1
+ bj−1 + dj−1 + c(Sj− ), then αju = αj−1
+ c(Sj+ ) from equations in
u
(7)–(8). Then, rewriting v(C) = mj and v1 (C1 ) in terms of αj−1
:
u
v(C) = αj−1
+ min{βju , βjd + bj−1 }

and
u
v1 (C1 ) = αj−1
.

As a result, the values v1 (C1 ) and v2 (C2 ) summed gives the value v(C) under the assumption
for the value of αjd .
−
+
d
u
Similarly, if βj−1
= βju + uj−1 + dj−1 + c(Sj−1
), then βj−1
= βju + c(Sj−1
) from equations
u
in (9)–(10). Then, rewriting v(C) = mj−1 and v2 (C2 ) in terms of βj :
u
d
v(C) = βju + min{αj−1
, αj−1
+ uj−1 }
35

and
v2 (C2 ) = βju .
As a result, the values v1 (C1 ) and v2 (C2 ) summed gives the value v(C) under the assumption
d
for the value of βj−1
.
B.3. Proof of Lemma 12. The proof follows closely to that of Lemmas 10 and 11. Let
−
+
−
+
C = S + ∪ L− , C1 = SN
1 ∪ LN 1 and C2 = SN 2 ∪ LN 2 . For node set N1 and the arc set C1 ,
the value of the minimum cut is
u
d
v1 (C1 ) = min{αj−1
, αj−1
}

and for node set N2 and the arc set C2 , the value of the minimum cut is
v2 (C2 ) = min{βju + uj−1 , βjd + bj−1 }.
−
d
d
Now, if αju = αj−1
+ uj−1 + c(Sj+ ) and βj−1
= βju + uj−1 + dj−1 + c(Sj−1
), then αjd =
−
+
u
u
+ dj + c(Sj ) and βj−1 = βj + c(Sj ). Then, rewriting v(C) = mj , v1 (C1 ) and v2 (C2 ):

d
αj−1

d
d
v(C) = αj−1
+ min{uj−1 + βju , βjd } = αj−1
+ uj−1 + βju ,
d
v1 (C1 ) = αj−1
and v2 (C2 ) = βju + uj−1 .

As a result, the values v1 (C1 ) and v2 (C2 ) summed gives the value v(C) under the assumption
d
for the values of αju and βj−1
.
B.4. Proof of Lemma 13. The proof follows closely to that of Lemmas 10 and 11. Let
+
−
+
−
C = S + ∪ L− , C1 = SN
1 ∪ LN 1 and C2 = SN 2 ∪ LN 2 . For node set N1 and the arc set C1 ,
the value of the minimum cut is
u
d
v1 (C1 ) = min{αj−1
+ bj−1 , αj−1
+ uj−1 }

and for node set N2 and the arc set C2 , the value of the minimum cut is
v2 (C2 ) = min{βju , βjd }.
+
u
u
Now, if αjd = αj−1
+ bj−1 + dj + c(Sj− ) and βj−1
= βjd + bj−1 + c(Sj−1
), then αju =
u
d
αj−1
+ c(Sj+ ) and βj−1
= βjd + dj + c(Sj− ). Then, rewriting v(C) = mj , v1 (C1 ) and v2 (C2 ):
u
u
v(C) = αj−1
+ min{βju , βjd + bj−1 } = αj−1
+ βjd + bj−1 ,
u
v1 (C1 ) = αj−1
+ bj−1 and v2 (C2 ) = βjd .

As a result, the values v1 (C1 ) and v2 (C2 ) summed gives the value v(C) under the assumption
u
for the values of αjd and βj−1
.

36

