7/31/2019 Avella 05 - Bcp Cflp
1/27
A cutting plane algorithm for the
Capacitated Facility Location Problem
Pasquale Avella Maurizio Boccia
March 15, 2005
RCOST Research Center on Software Technology, Universita del Sannio,
C.so Garibaldi 107, 82100 Benevento, Italy, [email protected] di Ingegneria, Universita del Sannio, Piazza Roma 21, palazzo ex INPS,
82100 Benevento, Italy, [email protected]
7/31/2019 Avella 05 - Bcp Cflp
2/27
Abstract
The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities
with capacity constraints, to satisfy at the minimum cost the order-demands of a set of
clients.
In this paper we present a reformulation ofCFLPbased on Mixed Dicut Inequalities,
a family of knapsack inequalities of a mixed type, containing both binary and continuous
(flow) variables. By aggregating flow variables, any Mixed Dicut Inequality turns into a
binary knapsack inequality with a single continuous variable. We will refer to the convex
hull of the feasible solutions of this knapsack problem as the Mixed Dicut polytope.
We observe that the Mixed Dicut polytope is a rich source of valid inequalities for
CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover,
Flow Cover and Effective Capacity Inequalities, are valid for the Mixed Dicut polytope.
Furthermore we observe that new families of valid inequalities for CFLP can be derived
by the lifting procedures studied for the knapsack with a single continuous variable.
To deal with large-scale instances, we have developed a Branch-and-Price algorithm,
where the separation algorithm consists of the complete enumeration of the facets of the
Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities. We observe that
our procedure returns inequalities that dominate most of the known classes presented
in the literature. We report on computational experience with instances up to 1000
facilities and 1000 clients to validate the approach.
Keywords: Capacitated Facility Location Problem, Mixed Dicut Inequalities, Facet-
enumeration.
7/31/2019 Avella 05 - Bcp Cflp
3/27
7/31/2019 Avella 05 - Bcp Cflp
4/27
and Flow Cover and Effective Capacity Inequalities, are valid for the Mixed Dicut
polytope. Furthermore new families of valid inequalities can be derived by using the
lifting procedures introduced by Marchand and Wolsey [17] for the knapsack with a
single continuous variable.
A Branch-and-Price algorithm is proposed to handle large scale instances. The
LP-relaxation is solved by delayed column generation. The cutting plane generation
consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set
of candidate base Mixed Dicut Inequalities. The procedure returns valid inequalities
dominating most of the known classes presented in the literature.
The remainder of the paper is organized as follows. In Section 2 we describe the
standard formulation of CFLP. In Section 3 we review the literature concerning poly-
hedral properties of CFLP. In Section 4 we present the reformulation of CFLP as a
Fixed Charge Network Flow problem and introduce the family of the Mixed Dicut In-
equalities. In Section 5 we review all the known families of valid inequalities for CFLP
and prove that they are valid for the Mixed Dicut Polytope. In Section 6 we define
a new class of valid inequalities by extending to the Mixed Dicut Polytope the results
presented in [17] for the 0-1 Knapsack Problem with a Single Continuous Variable. In
Section 7 we describe the facet-enumeration and the selection of candidate Mixed Dicut
Inequalities. In Section 8 we describe the Branch-and-Cut-and-Price algorithm devel-
oped to deal with large-scale instances. Finally in Section 9 we report on computational
results validating the usefulness of the proposed approach.
2 Problem formulation
Let M = {1, . . . , m} be a set of facilities, N = {1, . . . , n} a set of clients and let
G(M N, A) be a complete bipartite graph. Let uk be the capacity of the facility k
and let dj be the demand of client j N. Let hk be the fixed cost of opening facility
k M. Let ckj be the cost of sending one unit of demand from the facility k M to
2
7/31/2019 Avella 05 - Bcp Cflp
5/27
the client j N through the arc kj A and let fkj be the flow of the demand from
facility k M to the client j N.
A subset K M of facilities is feasible if the client demands can be assigned to the
facilities in K while respecting the capacity bounds, i.e. if the following Transportation
Problem, denoted as Transp(K), admits a feasible solution:
min
kK
jN
ckjfkj
kK
fkj = dj, j N
jN
fkj uk, k K (1)
fkj 0, k M, j N (2)
Let c(K) be the value of the optimal solution ofTransp(K) and let h(K) =
kKhk
be the sum of the fixed costs of the open facilities. The Capacitated Facility Location
Problem (CFLP) is to find a feasible subset K M of open facilities, minimizing the
objective function z(K) = h(K) + c(H(K)).
Let yk be the binary variable associated with the facility k M, i.e. yk = 1 ifk is
open (i.e.k K), 0 otherwise. Formulation F1 of CFLP is:
min
kM
hkyk +
kM
jN
ckjfkj
kM
fkj = dj, j N (3)
jN
fkj ukyk, k M (4)
yk {0, 1}, k M
fkj 0, k M, j N
Constraints 3 require that the whole demand of each client be satisfied. Capacity
constraints 4 require that no client can be supplied from a closed facility and that the
total demand supplied from the facility k K does not exceed its capacity uk.
3
7/31/2019 Avella 05 - Bcp Cflp
6/27
3 Basic polyhedral results
Let X(G,d,u) be the set of the integer feasible solutions of formulation F1 and let
CAP(G,d,u) = conv(X(G,d,u)) be the Capacitated Facility Location Polytope. The
dimension of the CAP(G,d,u) is |M| + |N| + |M| |N| if G is a complete bipartite
graph [1]. In the following of this section we review the main classes of valid inequalities
introduced in the literature. For any S N, we will denote d(S) =jS
dj .
3.1 Variable Upper Bounds
Let k M, j N. The Variable Upper Bound
fkj ukyk (5)
is valid for CAP(G,d,u). The (5) can be strengthened to fkj djyk, if dj < uk.
Proposition 3.1 ([1]) Let k M, j N. The Variable Upper Bound fkj djyk is
facet-defining for CAP(G,d,u) ifhM
uh maxhM
uh > d(N) and dj < uk.
3.2 Cover Inequalities
Let C M be a subset of facilities and let C = M \ C. The set C is said a cover if
kC
uk < d(N). Since the capacity of the facilities in C is not large enough to satisfy the
client demand, at least one of the facilities in C must be open and the Cover Inequality
kC
yk 1 (6)
is valid for CAP(G,d,u). The cover C is minimal if each subset S C is not a cover.
Proposition 3.2 (Aardal [1]) LetC M be a minimal cover and let umin = minkC
uk
be the minimum capacity of a facility in C. The Cover Inequality:
kC
yk 1
is facet-defining for conv(X(G,d,u) {yk = 1, k M\ C}) if
kM\C
uk + umin > d(N).
Sequential lifting can make the (6) facet-defining for CAP(G,d,u) [1].
4
7/31/2019 Avella 05 - Bcp Cflp
7/27
3.3 Flow Cover and Effective Capacity inequalties
Let J N and let C M be a flow-cover, i.e. a subset of facilities with the property
thatkC
uk d(J) = > 0.
Theorem 3.1 The Flow Cover Inequality
kC
jJ
fkj +
kC
(uk )+(1 yk) d(J) (7)
is valid for CAP(G,d,u).
Aardal [1] proved that Flow Cover inequalities are facet-defining if maxiI{ui} >
andkM
uk > d(J)+urr I. Flow Cover Inequalities generalize the Residual Capacity
Inequalities, introduced by Leung and Magnanti [16] for the special CFLP where all the
facilites have the same capacity u.
The same author introduced the family of the Effective Capacity Inequalities, that
dominate Flow Cover Inequalities. Suppose the bipartite graph G(M N, A) is not
complete and let Jk J be the subset of clients reachable by the facility k M.The effective capacity of the facility k is uk = min{uk, d(Jk)}. Let J N and let
C M be an effective flow-cover for J, i.e. a subset of facilities with the property thatkM
uk d(J) = > 0, maxkC
uk.
Theorem 3.2 The Effective Capacity Inequality
kC
jJk
fkj +
kC
(uk )+(1 yk) d(J) (8)
is valid for CAP(G,d,u).
Aardal provides necessary and sufficient conditions guaranteeing that Effective Ca-
pacity Inequalities are facet-defining for CAP(G,d,u).
5
7/31/2019 Avella 05 - Bcp Cflp
8/27
4 Fixed Charge Network Flow reformulation
Let o be a supernode and let O = {ok : k M} be an additional set of arcs connecting
o to M. Let xkj be the variable representing the capacity installed on the arc kj . With
these additions, it is easy to see that CFLP is a Single Commodity Uncapacitated Fixed
Charge Network Flow problem on the graph Go(o M N, O A), where the amount
of flowjN
dj must be sent from the source node o to the sink nodes N through the
transhipment nodes M. A minor difference with the standard version is that capacities
xij are not forced to be integral.
min
kM
hkyk +
kM
jN
ckjxkj
kM
fok =
jN
dj (9)
jN
fkj fok = 0, k M (10)
kM
fkj = dj, j N (11)
fok ukyk, k M (12)
fkj xkj , k M (13)
yk {0, 1}, k M (14)
fkj 0, k M, j N (15)
xkj 0, k M, j N (16)
Let K M and let J N. The set of arcs (K, J) = {ok O : k K} {kj
A : k M \ K, j J} defines a dicut on Goseparating o and the node J. By Max
Flow-Min Cut theorem it is easy to show that CFLP can be reformulated using the
Mixed Dicut Inequalities introduced in Ortega and Wolsey [19].
Proposition 4.1 LetK M and let J N. The Mixed Dicut Inequality
kK
ukyk +
kM\K
jJ
xkj d(J) (17)
6
7/31/2019 Avella 05 - Bcp Cflp
9/27
is valid for CAP(G,d,u).
Since the capacity xkj is fractional, in any optimal solution we will get xkj = fkj ,
for any value of fkj and it follows that we can project out variables xkj and the Mixed
Dicut Formulation F2 of CFLP is:
min
kM
hkyk +
kM
jN
ckjfkj
kKu
kyk +
kM\K
jJ f
kj jJ d
j, K M, J N (18)
yk {0, 1}, k M (19)
0 fkj dj, k M, j N (20)
5 CFLP inequalities and the Mixed Dicut Polytope
By letting s =
kM\K
jJ
fkj , any Mixed Dicut Inequality (17) turns into a knapsack
inequality with a single continuous variable. Let K M and J N and letkK
ukyk +
s d(J)} be a Mixed Dicut Inequality. Let Y(K, J) = {(y, s) Bn R+ :kK
ukyk +
s d(J)} be the set of incidence vectors of the feasible solutions and let CU T(K, J) =
conv(Y(K, J)) be the Mixed Dicut Polytope. It is easy to prove that CU T(K, J) is
full-dimensional. Studying CU T(K, J) can lead to tighter cutting planes families that
strengthen formulations F1 and F2. In the following we observe that the families of
valid inequalities described in Section 4 are valid for CU T(K, J) for some K M and
J N.
5.1 Variable Upper Bounds
Proposition 5.1 Letk M and letj N. The Variable Upper Bound (5) fkj ukyk
is valid for CU T({k}, {j}).
7
7/31/2019 Avella 05 - Bcp Cflp
10/27
Proof. By adding the equalitykM
fkj = dj to the Variable Upper Bound fkj ukyk,
we get the Mixed Dicut Inequality ukyk + s dj.
5.2 Cover Inequalities
Consider the dicut ({o} : M) = {ok : k M} formed by the arcs leaving the node o
and entering the set M.
Proposition 5.2 The Cover Inequality (6) is valid for CUT(M, N).
Proof. Trivial, since CU T(M, N) = conv{y {0, 1}|M| :kM
ukyk d(N)} is a
knapsack polytope.
5.3 Flow Cover Inequalities
In this subsection we show that the Flow Cover Inequality can be derived by sequential
lifting as a valid inequality for the Mixed Dicut Polytope. The following two lemmas
can be used to down lift a valid inequality for a Mixed Dicut Polytope. Theorem 5.1
shown that such an inequality is a Flow Cover Inequlitiy (7).
Lemma 5.1 The optimal solution of the knapsack problem:
min z =
kS
(uk )+yk + s
s +
kS
ukyk d(J)
kC\(Sh)
uk uh (21)
s 0
yk {0, 1}, k S
is yk = 1 for k S, s = (uh )+. It follows that the optimalsolution value is
z =
kS(uk )+ + (uh )
+.
Proof. Since =kC
uk jJ
dj, we pose d(J)
kC\S
uk = +kS
uk, so we can
write:
8
7/31/2019 Avella 05 - Bcp Cflp
11/27
min z = +
kS
(uk )+yk
s +
kS
ukyk +
kS
uk uh
s 0
yk {0, 1}, k S
Suppose now that yk = 0 in any optimal solution. If we set yk = 1 for k = S, we
must add the yk coefficient (uk ), but at the same time s decreases by uk. The netamount (uk )
+ uk is negative, a contradiction.
Lemma 5.2 Let S C and let s +
kS(uk )+yk
kS(uk )
+ be a valid
inequality for CU T(C, J) {yk = 1, k C\ S}. Let h C\ S. The inequality
s +
kS
(uk )+yk + hyh
kS
(uk )+ +
is valid for CU T(C, J) {yk = 1, k C\ (S h)} if h = (uh )+.
Proof. Let z be the optimal solution of the knapsack problem (21). Using the standard
procedure for down-lifitng, the inequality s+kS
(uk)+yk+hyh
kS(uk)
++
is valid iff = z
kS(uk)+. By lemma 5.1 we have that z =
kS(uk)
+(uh
)+ and the proof is complete.
Now we are able to prove the following theorem.
Theorem 5.1 The Flow Cover Inequality (7) is valid for CUT(C, J)
Proof. The Inequality s 0 is valid for CU T(C, J) {yk = 1, k C}. Applying
iteratively lemma 5.2 to compute lifting coefficients, we have that the inequality
s +
kC
(uk )+yk
kC
(uk )+ (22)
is valid for CU T(C, J). By subtracting the equalitykM
jJ = d(J) to the (22), we
obtain the Flow Cover InequalitykC
jJ
fkj +kC
(uk )+(1 yk) d(J) .
9
7/31/2019 Avella 05 - Bcp Cflp
12/27
5.4 Effective Capacity Inequalities
Let K M be a subset of facilities and suppose that Go(M N, O A) is sparse. Let
Jk N be the subset of clients reachable by the facility k K and let J = kKJk be
the subset of clients reached by all the facilities in K. The set of arcs {ok O : k
C}{kj A : k C\M, j Jk} define a mixed dicut on Go. Let uk = min{uk, d(Jk)}.
As in [1], the Mixed Dicut Inequality defined by K and J can be strengthened as:
kK
ukyk + s
jJ
dj
that is valid for CAP(G,d,u). The Effective Mixed Dicut Polytope is:
ECUT(K, Jk) = conv{yk {0, 1}, k K, s R+ :
kK
ukyk + s d(J)
Studying this polytope we can define new cutting planes families valid for CAP(G,d,u).
Particularly, if C M is an effective flow-cover (section 3.3), using the lifting proce-
dure described in Section (5.3) for the Flow Cover Inequalities, we obtain the Effective
Capacity Inequality
kC
jJk
fkj +
kC
(uk )+(1 yk) d(J) (23)
defined in section (3.3).
6 More families of valid inequalities
Let Ys(K, J) = {(y, s) Y : s = s} be the subset of the incidence vectors of the
feasible solutions of a Mixed Dicut Inequality having the property that s = s. Let
CUTs(K, J) = conv(Y(K, J)).
Another way to generate facets of CU T(K, J) is to set s = s, consider facets of
the underlying knapsack polytope CU Ts(K, J) and reintroduce the continuous variable
s by lifting. This procedure leads to new families of valid inequalities for CUT(K, J)
and, consequently, for CAP(G,u,d). Marchand and Wolsey [17] introduced a lifting
procedure for the case wherekK
uk d(J) and s = 0.
10
7/31/2019 Avella 05 - Bcp Cflp
13/27
Theorem 6.1 (Marchand and Wolsey [17]) LetCU T0(K, J) = conv{(y, s) Y(K, J) :
s = 0} and letkK
kyk 0 be a valid inequality for CU T0(K, J). The inequality
kK
kyk 0 s
(24)
is valid for CU T(K, J) iff mins>0
s0(s)
, where
(s) = min{
kK
kyk :
kK
ukyk d(J) s, y B|K|}
Proof. We will give a geometric proof of the validity of the (24). (s) is a step function
(fig. 1). The inequalitykK
kyk (s) is valid for CU T(K, J) if (s) (s), for each
s R.
Let s be such that maxs>0
0(s)s
= 0(s)
s. Let (s) = 0
s
be the line of minimum
slope intersecting (s) and crossing the points (0, 0) and (s, (s)). It is easy to observe
that (s) (s) and the proof is complete.
Figure 1: The function (s)
The lifting procedure can be generalized by removing the restriction thatkK
uk
d(J).
Let smin = max(0, d(J) kK
uk) be the minimum value of s that guarantees that
the set of the feasible solutions Y(K, J) is nonempty.
11
7/31/2019 Avella 05 - Bcp Cflp
14/27
Theorem 6.2 Lets smin and letkK
kyk s be a valid inequality for the knapsack
polytope CU Ts(K, J).
The inequality
kK
kyk s s smin
(25)
is valid for CU T(K, J) if mins>smin
ssmins(s)
, where
(s) = min{
kK
kyk :
kK
ukyk d(J) s, y B|K|} (26)
Proof. The function (s) is defined for s smin. Let s be such that maxs>smins(s)ssmin =
s(s)
ssmin. Let s
ssmin
be the line of minimum slope intersecting (s) and crossing
the points (smin, (s)) and (s, (s)) (figure 2). It is immediate that (s) s
ssmin
and the proof is complete.
Figure 2: The function (s) in the case
kKuk < d(J)
7 The separation routine
The above results suggest that the facial structure of CU T(K, J) can be exploited to
generate strong cutting planes. We propose a twp-step separation algorithm based
12
7/31/2019 Avella 05 - Bcp Cflp
15/27
on the enumeration of the facets of CU T(K, J). The first step consists of choosing a
Mixed Dicut InequalitykK
ukyk +
kM\K
jJ
xkj d(J), with K suitably small, as a
base inequality. Then for each base inequality we enumerate the feasible solutions of
Y(K, J) and run a facet-enumeration routine to list the facets ofCU T(K, J), returning
violated cutting planes.
An accurate selection of the base inequalities and a fast enumeration procedure of
the feasible solutions are crucial to the success of the separation algorithm.
7.1 Selection of base inequalities
Let (y, f) be the current fractional solution. The procedure to select candidate base
inequalities is inspired by the separation heuristic described in [2] for the Flow Cover
Inequalities and is based on the following observations.
Remark 7.1 A valid inequality for CU T(K, J) can be violated by the (y, f) only if
at least one of the variables yk, k K, has a fractional value.
Remark 7.2 The chances of finding violated a valid inequality for CU T(K, J) in-
crease if s is small (the smaller the s, the larger the r.h.s. of the knapsack inequalitykK
ukyk+ d(J) s).
Remark 7.3 The chances of finding a violated valid inequality for CU T(K, J) increase
if we choose K and J such that the facilities in K serve only the clients in J in the
current fractional solution.
The following heuristic attempts to generate base inequalities according to the re-marks (7.1), (7.2) and (7.3). The selection procedure is iterated for each triple of
facilities K = {k1, k2, k3} M such that there exists at least a k with 0 < ykj < 1.
The main steps of the procedure are summarized below. The facet-enumeration routine
is efficient only ifK is suitably small. Let maxK denote the maximum number of y-
variables in a base inequality used for the facet enumeration. Computational experience
showed us that a good choice is to set maxK = 7.
13
7/31/2019 Avella 05 - Bcp Cflp
16/27
Procedure 7.1 (Selection of the base inequalities)
Initialize K and J
0) LetK = {k1, k2, k3} be a set of facilities with the property that 0 < yk1 < 1.
1) LetJ be defined by all the clients j J such thatkK
fkj 0.01dj
2) Generate the base inequalitykK
ukyk + s d(J).
Enlarge K
3) Letk = arg maxkM\K
jJfkj. Add k to K.
4) Add to J all the clients j M \ J such thatkK
fkj 0.01dj.
5) If |K| maxK,kK
ukyk + s d(J) is a base inequality else STOP.
Adjust J
6) For each j J compute (j) =
kM\K
fkj .
7) Letjmin = arg maxjJ
(j).
8) IfkK
uk < d(J), remove jmin from J.
7) If |K| maxK generate the base inequalitykK
ukyk + s d(J) and go to
step 3), else STOP.
7.2 Enumeration of the feasible solutions satisying a base in-
equality
Let K M, J N and let Y(K, J) denote the set of the feasible solutions satisfying
the Mixed Dicut Inequality:
kK
ukyk + s d(J). (27)
For any partial solution y, let smin(y) = max(0, d(J) kK
ukyk) be the minimum
value of s that makes the solution (y, s) feasible for the (27). We refer to any solution
(y, smin(y)) as a minimal feasible solution of the (27) and we denote by Ysmin(K, J) =
14
7/31/2019 Avella 05 - Bcp Cflp
17/27
{(y, s) Y(K, J) : s = smin} the set defined by the minimal feasible solutions of the
(27). In this section we will prove that the facets of CU T(K, J) are in one-to-one
correspondence with a subset of the facets of conv(Ysmin(K, J)). We observe that the
polytope conv(Ysmin(K, J)) is full-dimensional.
Lemma 7.1 A inequalitykK
kyk + s is valid for CU T(K, J) only if 0.
Proof. LetkK
kyk + s be a valid inequality for CU T(K, J) and let (y, s)
Y(K, J) be a feasible solution satisfying the (27). If < 0, it is always possible to
set s large enough (and the solution remains feasible) such thatkK
kyk + s < , a
contradiction.
The following theorem proves that any facet ofCU T(K, J) is also a facet ofconv(Ysmin(K, J)).
Theorem 7.1 A inequality
kK
kyk + s (28)
is facet-defining for conv(Ysmin(K, J)) if it is facet-defining for CUT(K, J).
Proof. IfkK
kyk + s is valid for CU T(K, J) then > 0. IfkK
kyk + s is
facet-defining for CU T(K, J), there exist |K| +1 linearly independent feasible solutions
satisfying the (28) as an equality (roots).
Let (y, s) be a root of the (28) and suppose that s > smin. Since (y, s) is a root, we
havekK
kyk + s = . But (y, smin) is still a feasible solution and, since 0, it
violates the (28), i.e.kK
kyk + smin < , a contradiction.
It follows that all the |K| + 1 roots are of the form (y, sminy) and belong toYsmin(K, J), so we can conclude that the (28) is facet-defining for conv(Ysmin(K, J)).
Theorem 7.2 Let
kK
kyk + s (29)
be a facet of conv(Ysmin(K, J)). The (29) is facet-defining for CU T(K, J) if and only
if 0.
15
7/31/2019 Avella 05 - Bcp Cflp
18/27
7/31/2019 Avella 05 - Bcp Cflp
19/27
promising initial set of columns. In our case we adopt the lagrangian core selection
strategy presented in [4]. This strategy use the lagrangean reduced costs in order to
select the variables of the core problem.
The branching strategy is to set node variables yu to 1 if facility u V is open, 0
otherwise. The node selection criterion is best-bound. The variable selection criterion
is to choose the most fractional node variable, i.e. the variable whose fractional value
is closest to 0.5.
Finally we use standard reduced cost fixing to reduce the size of the problem.
9 Computational results
In this section we report on the computational experience with the Branch-and-Cut-and-
Price algorithm. We ran the experiments on a Pentium IV 1.7 Ghz Personal Computer,
with 512 Mb RAM and we used Cplex 8.1 as LP solver and the routine Qhull [7],
developed by the Geometric Center of University of Minnesota, as facet-generation
routine. In the selection of base inequalities we found useful to consider only MixedDicut Inequaalites with |K| 9.
The test instances were randomly generated according to Cornuejols, Sridharan and
Thizy ([13]), Aardal ([1], [2]) and Barahona and Chudak ([6]). The generation procedure
is summarized below:
a) Points representing the clients and the facilities are uniformly randomly gener-
ated in a unit square. Transportation costs per unit flow are then computed by
multiplying the euclidean distances by 10.
b) Demands are drawn from U[5, 35] i.e. they are uniformly distributed in the inter-
val [5, 35].
c) Capacities uk are drawn from U[10, 160] and then are scaled by using the capacity
ratio r =
kMuk/d(J). In our experiments we set r = 5, 10, 15, 20.
17
7/31/2019 Avella 05 - Bcp Cflp
20/27
d) Fixed costs are generated according to the formula hk = U[0, 90]+ U[100, 110], to
take into account the economies of scale.
Moreover, we observe that in [13, 1, 2] the ratio r is set to 2, 3, 5, 10. We use larger
values of r because for sizes we deal with, setting r = 2 or r = 3 leads to instances
easily solvable by the lagrangean heuristic [4].
The test instances are organized into 4 groups, each including instances of the same
size. The sizes (|M| |N|) here considered are: 300 300, 500 500, 700 700 and
1000 1000. Each class of instances includes four different sets of problems according
to the ratio r. We used ratio indices r of 5, 10, 15 and 20 respectively.
The results are shown in tables 1-4, whose format is the following. Column Ratio is
the value ofr, UBHeur is the initial upper bound and column U BHeur Time is the time
spent to compute the initial upper bound. Columns LP and LPCuts report respectively
on the value of the LP relaxation and on the value of the LP relaxation after the addition
of cutting planes. Column %Gap shows the % of the gap closed by the cut generation
routine at the root node, i.e. % Gap =(LPCutsLP)/(BU BLP). Columns BLB abd
BU B report respectively on the best lower bound and on the best upper bound yielded
by Branch-and-Cut-and-Price within the time limit. Columns B&C&P and B&C&P
Time report respectively on the number of nodes and on the total computation time
for the Branch-and-Cut-and-Price-procedure.
The time limit for the Branch-and-Cut-and-Price was set to 100000 seconds. All
the instances in the test bed were solved to optimality, with the exceptions of I1000-8,
I1000-11 and I1000-12, where, however, the algorithm yielded a very small gap. We
observe that the cut generation strategy has led in most of the test to a significant
reduction of the gap.
We observe that the reduction of the gap is small for r = 5. This because the LP
lower bound is already very close to the optimal solution, so that it is more difficult to
find violated cutting planes by the LP solution. For these cases the pricing approach
assume a more significant role than cutting plane generation. On the other hand, for
18
7/31/2019 Avella 05 - Bcp Cflp
21/27
higher values of r, also the initial gap increases and our cut generation strategy turned
out to be effective in solving the CFLP instances.
Tables 1-2 report also on lower bound at the root node computed by CPLEX 8.1
solver (CPLEXroot), and the total time necessary to CPLEX to solve the instances
(CPLEXTime). We remark that even if Cplex implements a flow cover separation
procedure, it is not able to appreciably raise the lower bound.
Acknowledgements
The authors wish to thank Antonio Sassano and Sara Mattia for the helpful suggestions.
References
[1] K. AARDAL 1992. On the solution of one and two-level capacitated facility location
problems by the cutting plane approach. Ph.D Thesis Universit Catholique de
Louvain, Lovain-la-Neuve, Belgium.
[2] K. AARDAL 1998. Capacitated Facility Location: Separation Algorithms and
Computational Experience, Mathematical Programming, 81, 149-175.
[3] K. AARDAL, Y. POCHET, L.A. WOLSEY 1995. Capacitated Facility Location:
Valid Inequalities and facets. Mathematics of Operations Research 20, 562-582.
[4] P. AVELLA, M. BOCCIA, A. SFORZA, I. VASILIEV 2004. An effective heuristic
for large-scale Capacitated Plant Location problems, Technical Report, available
on line at http://www.diima.unisa.it/boccia/.
[5] R. ANBIL, F. BARAHONA 2000. The volume algorithm: producing primal so-
lutions with a subgradient method. Mathematical Programming, published online
March 15.
19
7/31/2019 Avella 05 - Bcp Cflp
22/27
[6] F. BARAHONA, F. A. CHUDAK 1999. Near-optimal solution to large scale facility
location problems, internal report IBM research division T. J. Watson Research
Center , RC 21606.
[7] C.B. BARBER, D.P. DOBKIN, H.T. HUHDANPAA 1996. The Quickhull algo-
rithm for convex hulls. ACM Trans. on Mathematical Software, 22(4):469-483,
http://www.qhull.org.
[8] J. E. BEASLEY 1993, Lagrangean Heuristics for Location Problems, EJOR 65,
383-399.
[9] D. BERTSIMAS, J.N. TSITSIKLIS 1997. Introduction to Linear Optimization.
Athena Scientific, Belmont, Massachussetts.
[10] S. CERIA, C. CORDIER, H. MARCHAND, L.A. WOLSEY 2002. Cutting Planes
for Integer Programs with General Integer Variables. Discrete Applied Mathemat-
ics, 123, 397-446.
[11] T. CHRISTOF, G. REINELT 1997. Low-dimensional linear ordering polytopes.
Tech. Rep. Institut fur Angewandte Mathematik, Universitat Heidelberg.
[12] F. A. CHUDAK, D. P. WILLIAMSON 1999. Improved Approximation Algorithms
for Capacitated Facility Location Problems, 7th International IPCO Conference
Proceedings, 99-113.
[13] G. CORNUEJOLS, R. SRIDHARAN, J.M.THIZY 1991. A comparison of heuris-
tics and relaxations for the Capacitated Plant Location Problem. European Journal
of Operational Research, 50, 280-297.
[14] A. KLOSE 2001. A Column Generation Procedure for the Capacitated Facility
Location Problem. EURO XVIII conference on Operational Research, Erasmus
University Rotterdam, July 9-11.
20
7/31/2019 Avella 05 - Bcp Cflp
23/27
[15] M. R. KORUPOLU, C. G. PLAXTON, R. RAJARAMAN 1998. Analysis of a
Local Search Heuristic for Facility Location Problems, DIMACS Technical Report
98-30.
[16] J.M.Y. LEUNG, T.L. MAGNANTI 1989. Valid Inequalities and Facets of the Ca-
pacitated Plant Location Problem. Mathematical Programming, 44, 271-291.
[17] H. MARCHAND, L.A. WOLSEY 1999. The 0-1 knapsack problem with a single
continuous variable. Mathematical Programming, 85, 15-33.
[18] T. L. MAGNANTI, P. MIRCHANDANI, R. VACHANI 1993. The convex hull of
two core capacitated network design problems. Mathematical Programming, 60,
233-250.
[19] F. ORTEGA, L. WOLSEY 2000. A Branch and Cut Algorithm for the Single
Commodity Uncapacitated Fixed Charge Network Flow Problem. Networks 41,
143-158.
21
7/31/2019 Avella 05 - Bcp Cflp
24/27
Name
Ratio
UBHeur
UBHeur
LP
CPLEXroot
LPCuts
%
Gap
BLB
BUB
B&C&P
B&C&P
Tot.Time
CPLEXTime
Ti
me(secs.)
nodes
Time(secs.)
(secs.)
(secs.)
I300-1
5
16350,6
6
13,1
4
16292
16293,0
9
16296,4
9
7,6
5
16350,6
6
16350,6
6
374
432,4
3
445,5
5
1019.2
0
I300-2
5
15948,4
4
30,5
3
15862,2
1
15886.0
6
15894,3
9
37,3
2
15948,4
4
15948,4
4
904
873,7
1
904,4
5
1531,7
0
I300-3
5
15474,8
4
13,7
7
15414,9
5
15401,7
1
15438,7
3
39,7
1
15474,8
4
15474,8
4
248
307,3
6
321,1
3
1168,0
0
I300-4
5
17989,9
7
16,3
5
17926
17927,6
9
17938,3
9
19,3
7
17989,9
7
17989,9
7
534
650,8
6
667,2
1
1367,0
6
I300-5
5
18037,6
1
17,6
1
17962,8
17966,7
3
17982
25,6
7
18037,6
1
18037,6
1
570
850,1
3
867,7
4
1057,8
4
I300-6
10
11255,4
8
5,7
3
11177,5
4
11177,8
4
11209,5
4
43,4
5
11251,1
9
11251,1
9
310
624,0
5
629,7
8
1150,4
1
I300-7
10
11393,2
9
8,6
2
11307,6
1
11308,6
4
11343,4
4
42,2
11392,5
2
11392,5
2
464
657,5
2
660,1
4
1689,5
0
I300-8
10
11377,3
4
7,5
8
11331,0
9
11333,1
8
11347,3
1
35,0
7
11377,3
4
11377,3
4
46
120,5
6
128,1
4
559,3
9
I300-9
10
10980,0
5
8,2
9
10787,8
1
10790,3
5
10830,6
47,4
2
10878,0
5
10878,0
5
198
785,7
7
794,0
6
1437,8
9
I300-1
0
10
11265,1
3
7,4
2
11174,3
3
11183,1
8
11208,8
58,9
8
11232,7
7
11232,7
7
44
152,9
2
160,3
4
558,9
4
I300-1
1
15
10024,4
7
6,6
4
9977,1
4
9980,0
5
10003,4
56,1
1
10023,9
4
10023,9
4
26
90,7
2
97,3
6
268.7
2
I300-1
2
15
9398,1
9
6,6
1
9300,6
6
9304,2
1
9312,0
3
31,6
9336,6
4
9336,64
82
230,2
5
236,8
6
311.0
8
I300-1
3
15
10107,9
5
6,5
3
9980,7
3
9981,7
3
10016,5
0
45,5
4
10058,4
9
10058,4
9
242
157,0
3
202,5
7
699,2
0
I300-1
4
15
9768,7
2
7,5
5
9669,6
4
9670,3
2
9688,5
1
63,5
1
9699,3
5
9699,35
14
331,6
4
339,1
9
481.9
7
I300-1
5
15
9909,3
5,6
6
9788,4
9798,2
1
9823,1
2
64,5
7
9842,1
7
9842,17
26
131,0
6
136,7
2
253,8
8
I300-1
6
20
9331,7
7
4,7
9
9096,0
7
9102,6
5
9145,0
8
78,1
4
9158,7
9
9158,79
16
120,0
5
124,1
2
239,0
9
I300-1
7
20
9227,5
6
5,4
8
9133,8
7
9135,2
1
9148,7
5
39,3
7
9171,6
7
9171,67
52
313,5
2
319
382,8
9
I300-1
8
20
9584,0
7
5,2
5
9533,7
1
9535,8
0
9538,4
9
24,0
4
9553,5
9
9553,59
18
102,1
4
107,3
9
323.8
9
I300-1
9
20
9111,4
5,1
4
9013,6
9016,5
2
9041,7
9
66,7
4
9053,7
1
9053,71
28
221,5
3
226,6
7
302,2
1
I300-2
0
20
9068,4
2
4,9
2
9044,7
5
9044,8
3
9046,1
9
91,1
4
9046,3
3
9046,33
8
9,1
9
14,1
1
78.0
6
Table1:Computationalresultsfor
testinstanceswith300facilitiesan
d300clients
22
7/31/2019 Avella 05 - Bcp Cflp
25/27
Name
Ratio
UBHeur
UBHeur
LP
CPLEXroot
LPCuts
%
Gap
BLB
BUB
B&C&P
B&C&P
Tot.Time
CPLEXTime
Ti
me(secs.)
nodes
Time(secs.)
(secs.)
(secs.)
I500-1
5
26412,4
1
36,6
26374,6
1
26374,8
5
26382,5
2
20,9
26412,4
1
26412,4
1
458
1267,4
2
1304,0
2
7924.8
3
I500-2
5
28144,8
3
109,3
6
28082,0
1
28082,1
9
28106,7
7
51,0
1
28130,7
4
28130,7
4
2144
5106,7
1
5216,8
7
18621,5
5
I500-3
5
27915,1
2
80,1
6
27857,0
5
27857,0
5
27873,7
2
35,1
2
27904,5
1
27904,5
1
1114
2595,6
1
2675,7
7
5277,4
4
I500-4
5
28159,0
3
128,2
3
28093,0
8
28095,7
0
28118,1
2
37,3
8
28159,0
3
28159,0
3
1332
2548,8
9
2677,1
2
9524,7
2
I500-5
5
24702,7
7
136,1
2
24645,6
3
24645,8
6
24673,9
5
49,5
6
24702,7
7
24702,7
7
1872
4715,6
1
4851,7
3
15085,5
9
I500-6
10
15756,8
2
13,7
6
15672,3
6
15674,7
9
15726,2
5
63,8
1
15756,8
2
15756,8
2
128
844,2
7
858,0
3
6426,5
9
I500-7
10
16110,8
22,4
7
16029,0
1
16030,0
9
16076,9
4
59,7
1
16109,2
8
16109,2
8
436
2420,7
7
2443,2
4
8379.3
0
I500-8
10
16041,7
3
24,8
5
15969,9
4
15970,5
7
16011,2
2
57,5
16041,7
3
16041,7
3
458
3375,3
1
3300,1
6
9434,3
3
I500-9
10
16327,7
1
48,9
5
16237,4
7
16238,3
3
16265,1
30,6
1
16327,7
1
16327,7
1
2076
4277,3
4326,2
5
28226,2
8
I500-1
0
10
15815,1
3
19,3
7
15751,9
1
15752,0
2
15780,0
1
44,4
5
15815,1
3
15815,1
3
176
1226,7
8
1246,1
5
4709,1
9
I500-1
1
15
13442,9
1
17,7
6
13406,0
1
13406,2
5
13421,3
3
48,3
1
13437,7
2
13437,7
2
48
243,5
3
261,2
9
1292,3
7
I500-1
2
15
14698,0
3
33,7
1
14610,1
14610,5
2
14651,3
63,4
6
14675,0
2
14675,0
2
152
1018,9
7
1052,6
8
3401,3
9
I500-1
3
15
13667,2
3
12,7
1
13631,3
5
13631,3
8
13640,2
7
25,5
6
13666,2
5
13666,2
5
78
398,5
6
411,2
7
2732,6
4
I500-1
4
15
13595,1
21,7
4
13514,9
3
13516,2
5
13542,5
3
42,4
1
13580,0
1
13580,0
1
130
1486,0
6
1507,8
3909,2
3
I500-1
5
15
13930,6
8
35,6
6
13833,4
2
13834,1
9
13858,2
9
39,2
6
13896,7
6
13896,7
6
104
351,0
6
386,7
2
4954,7
2
I500-1
6
20
12786,2
9
8,5
9
12492,6
8
12493,6
4
12552,6
65,2
7
12584,4
9
12584,4
9
140
921,8
6
930,4
5
2503,0
6
I500-1
7
20
13347,4
17,3
8
13290,2
6
13291,3
1
13323,1
57,4
7
13347,4
13347,4
80
775,6
4
793,0
2
1972,2
3
I500-1
8
20
12831,1
2
14,3
8
12780,1
6
12780,7
5
12810,1
58,7
5
12831,1
2
12831,1
2
66
407,6
1
421,9
9
1241,2
2
I500-1
9
20
13489,6
1
14,4
1
13450,6
3
13451,7
2
13469,2
9
47,8
7
13489,6
1
13489,6
1
62
334,4
7
348,8
8
1635,1
1
I500-2
0
20
12342,2
6
14,7
5
12312,4
6
12311,5
1
12326,9
4
48,5
9
12342,2
6
12342,2
6
24
257,6
6
272,4
1
1267,2
7
Table2:Computationalresultsfor
testinstanceswith500facilitiesan
d500clients
23
7/31/2019 Avella 05 - Bcp Cflp
26/27
Name
Ratio
UBHeur
UBHeur
LP
LPCu
ts
%
Gap
BLB
BUB
B
&C&P
B&C&P
Tot.Time
Time(secs.)
nodes
Time(secs.)
(secs.)
I700-1
5
36908,5
8
162,2
2
36839,9
6
36859,4
9
28,4
6
36905,9
3
36905,9
3
1600
9874,7
4
10036,1
9
I700-2
5
34311,7
1
188,4
4
34250,1
6
34274,8
7
40,1
5
34311,7
1
34311,7
1
3820
14823,7
8
15012,2
2
I700-3
5
34294,6
3
195,1
4
34253,7
3
34267,2
6
33,0
8
34294,6
3
34294,6
3
1036
2748,2
2
2943,3
6
I700-4
5
380
90,9
263,2
3
38029,8
7
38046,5
7
27,3
6
38090,9
38090,9
2400
8703,5
6
8966,7
9
I700-5
5
378
02,1
309,9
9
37741,1
2
37759,6
5
30,3
9
37802,1
37802,1
3112
15369,7
3
15679,7
2
I700-6
10
19927,3
4
50,7
9
19821,9
7
19854,3
8
36,5
4
19910,6
7
19910,6
7
3368
23088,9
4
23139,7
3
I700-7
10
212
97,3
49,7
8
21195,9
3
21233,1
5
36,7
2
21297,3
21297,3
1808
17096,0
6
17145,8
4
I700-8
10
20678,8
7
44,0
9
20592,1
8
20621,6
5
43,4
8
20659,9
6
20659,9
6
410
5495,9
2
5540,0
1
I700-9
10
20990,2
7
86,3
20894,1
9
20920,6
9
30,9
3
20979,8
8
20979,8
8
1638
18050,7
5
18137,0
5
I700-1
0
10
22
060
49,5
1
21960,8
8
22015,4
8
57,7
6
22055,4
1
22055,4
1
1872
27235,6
1
27285,1
2
I700-1
1
15
17164,3
1
22,9
9
17005,2
4
17056,5
6
44,6
6
17120,1
5
17120,1
5
5022
64296,5
3
64319,5
2
I700-1
2
15
18130,4
5
33,0
1
18048,2
18080,8
6
39,7
2
18130,4
2
18130,4
2
262
4459,7
4492,7
1
I700-1
3
15
17239,9
6
53,4
4
17163,1
5
17201,3
2
49,6
9
17239,9
6
17239,9
6
394
3068,0
8
3121,5
2
I700-1
4
15
17337,6
3
32,4
7
17247,1
6
17279,1
4
35,3
5
17337,6
3
17337,6
3
578
10716,7
5
10749,2
2
I700-1
5
15
18145,4
9
44,6
9
18069,7
9
18097,2
7
36,3
18145,4
9
18145,4
9
192
4885,2
5
4929,9
4
I700-1
6
20
16000,0
3
16,0
8
15945,2
8
15988,4
2
78,7
9
16000,0
3
16000,0
3
24
802,9
7
819,0
5
I700-1
7
20
16172,7
4
15,9
1
16132,8
3
16145,9
9
33,8
8
16171,6
7
16171,6
7
54
1292,1
9
1308,1
I700-1
8
20
164
14,8
14,4
16350,5
16384,2
6
52,5
16414,8
16414,8
66
1673,5
9
1687,9
9
I700-1
9
20
16366,7
8
20,3
4
16321,9
1
16346,3
8
54,5
4
16366,7
8
16366,7
8
94
1483,7
4
1504,0
8
I700-2
0
20
15434,2
1
19,1
4
15369,6
6
15404,4
2
53,8
5
15434,2
1
15434,2
1
64
2007,5
2026,6
4
Table3:Computationalresultsfor
testinstanceswith700facilitiesan
d700clients
24
7/31/2019 Avella 05 - Bcp Cflp
27/27
Name
Ratio
UB
Heur
UBHeur
LP
LPCuts
%
Gap
BLB
BUB
B
&C&P
B&C&P
Tot.Time
Time(secs.)
nodes
Time(secs.)
(secs.)
I1000-1
5
49537,2
780,2
9
49459,6
7
49476,1
9
32,9
5
49509,8
1
49509,8
1
7608
60122,6
9
60902,9
8
I1000-2
5
506
92,4
8
1042,1
1
50626,8
8
50641,7
4
24,0
9
50688,5
7
50688,5
7
8042
71738,0
6
72780,1
7
I1000-3
5
472
04,2
4
429,1
9
47153,1
5
47166,6
1
27,2
47202,6
4
47202,6
4
3454
29870,6
4
30299,8
3
I1000-4
5
488
71,0
6
1359,4
2
48807,6
8
48822,7
2
24,7
1
48868,5
4
48868,5
4
5250
42581,9
6
43941,3
8
I1000-5
5
50753,6
594,0
3
50704,3
8
50719,7
6
38,5
6
50743,5
4
50743,5
4
782
7430,6
5
8024,6
8
I1000-6
10
278
43,6
4
403,7
3
27736,3
2777
2,7
41,5
8
27823,8
4
27823,8
4
3214
70700,4
4
71104,1
7
I1000-7
10
272
64,7
7
436,9
1
27162,1
8
27189,6
7
30,5
27252,3
2
27252,3
2
4172
71356,3
8
71793,2
9
I1000-8
10
273
75,3
7
285,4
4
27253,5
3
27289,8
2
29,7
8
27369,0
4
27375,3
7
6386
100000
100285,4
I1000-9
10
268
88,1
2
381,5
7
26755,2
2
26802,0
6
45,9
8
26857,0
9
26857,0
9
4978
71681,7
2
72063,2
9
I1000-1
0
10
272
41,2
6
155
27106,9
5
27140,0
8
41,3
9
27186,9
9
27186,9
9
1564
40634,6
3
40789,6
3
I1000-1
1
15
221
80,3
3
445,8
2
22070,4
22103,3
4
29,9
6
22158,5
2
22180,3
3
4928
100000
100445,8
I1000-1
2
15
221
60,3
9
405,2
6
22054,7
6
22089,2
1
32,6
1
22145,9
6
22160,3
9
5270
100000
100405,3
I1000-1
3
15
226
57,0
9
228,8
6
22552,1
3
22590,9
1
36,9
5
22657,0
9
22657,0
9
1962
80693,0
3
80921,8
9
I1000-1
4
15
223
27,6
2
242,5
8
22241,7
6
22260,6
2
26,8
5
22312,0
1
22312,0
1
2086
51850,2
5
52092,8
3
I1000-1
5
15
22648,5
2
171,6
4
2523,3
6
22558,3
4
32,9
8
22629,4
4
22629,4
4
2914
85618,5
2
85790,1
6
I1000-1
6
20
213
31,8
1
119,0
4
21258,7
7
21279,0
2
27,7
2
21331,8
1
21331,8
1
1000
30657,8
30776,8
4
I1000-1
7
20
211
88,8
9
79,0
9
21153,1
2
21176,0
4
64,0
8
21188,8
9
21188,8
9
72
3403,0
8
3482,1
7
I1000-1
8
20
207
13,4
4
48,1
2
20658,4
2068
2,9
44,5
2
20713,4
3
20713,4
3
106
3222,2
4
3270,3
6
I1000-1
9
20
205
37,4
5
44,1
1
20470,1
1
20504,4
2
50,9
5
20537,4
5
20537,4
5
300
10417,0
9
10461,2
I1000-2
0
20
215
60,8
6
102,8
4
21496,8
9
21512
23,6
2
21560,8
6
21560,8
6
784
18619,6
9
18722,5
3
Table4:Computationalresultsfortestinstanceswith1000facilitiesan
d1000clients