Computational Optimization and Applications, 32, 215–230, 2005 2005 Springer Science + Business Media, Inc. Manufactured in The Netherlands.
A Branch-and-Cut Algorithm for the Median-Path Problem PASQUALE AVELLA
[email protected] RCOST—Research Center on Software Technology, Universit´a del Sannio, C.so Garibaldi 107, 82100 Benevento, Italy MAURIZIO BOCCIA
[email protected] CRMPA—Centro di Ricerca in Matematica Pura e Applicata, Universit`a di Salerno, Via Ponte Don Melillo, 84084 Fisciano (SA), Italy ANTONIO SFORZA
[email protected] Dipartimento di Informatica e Sistemistica, Universit´a degli Studi di Napoli “Federico II”, Via Claudio 21, 80125 Napoli, Italy IGOR VASIL’EV
[email protected] CRMPA—Centro di Ricerca in Matematica Pura e Applicata, Universit`a di Salerno, Via Ponte Don Melillo, 84084 Fisciano (SA), Italy; Institute of System Dynamics and Control Theory, Siberian Branch of Russian Academy of Sciences, Lermontov Srt., 134, 664033 Irkutsk, Russia Received June 4, 2003; Revised June 25, 2004; Accepted October 18, 2004
Abstract. The Median-Path problem consists of locating a st-path on a network, minimizing a function of two parameters: accessibility to the path and total cost of the path. Applications of this problem can be found in transportation planning, water resource management and fluid transportation. A problem formulation based on Subtour and Variable Upper Bound (VUB) inequalities was proposed in the seminal paper by (Current, Revelle and Cohon, 1989). In this paper we introduce a tighter formulation, based on a new family of valid inequalities, named Lifted Subtour inequalities, that are proved to be facet-defining. For the class of Lifted Subtour inequalities we propose a polynomial separation algorithm. Then we introduce more families of valid inequalities derived by investigating the relation to the Asymmetric Traveling Salesman Problem (ATSP) polytope and to the Stable Set polytope. These results are used to develop a Branch-and-Cut algorithm that enables us to solve to optimality small and medium size instances in less than 2 hours of CPU time on a workstation. Keywords:
1.
Path-Location, Median-Path, Branch-and-Cut
Introduction
Network location problems occur when one or more facilities have to be located on a network. They can be classified according to the form of the facilities, so a distinction is made between point location problems, where the facilities are to be located either in nodes or in points of the network, and path-location problems, where the facilities are path-shaped. For a complete survey on path-location problems we refer the reader to Labb`e et al. [12].
216
AVELLA ET AL.
The Median-Path problem consists of locating a path between a source node and a sink node, which minimizes a function of two parameters: the accessibility to the path and the cost of the path. Accessibility is expressed by the “distance” of the path [7], defined as the sum of the distances from the path to all the nodes not belonging to it. The cost of the path is given by the sum of the costs of the arcs belonging to the path. The Median-Path problem can therefore be defined as a bi-criterion problem, with two conflicting objective functions (the cost of the path must be increased to reduce the distance of the path and vice-versa). It can be also defined as a single criterion problem. For example, the objective can be to minimize the cost of the path with the upper bound of path distance and viceversa. The complexity of the Median-Path problem on general networks is analyzed in Richey [19] and in Hakimi et al. [11]. The problem is NP-hard on general graphs and polynomial on trees and series-parallel graphs [14–16, 20]. For the Median-Path problem on a general network [8] suggested a bi-objective model. This model is based on Subtour and Variable Upper Bound (VUB) inequalities. They developed a heuristic algorithm using a k-shortest path algorithm. Recently [13] have proposed a Branch-and-Cut algorithm for a closely related problem, the Median Cycle problem. The Median-Path problem also has common properties with a number of other network problems, for example, the Asymmetric Traveling Salesman problem [4], the Cycle problem of a directed graph [5], the p-Median problem [2]. Applications of the Median-Path problem arise in the design of lines (bus, underground) in a mass transportation system, where we assume that the path represents the facility and that the users demanding to reach the path are located in the nodes. The cost of the path will express the cost of setting up the facility, while the distance of the path will measure the total distance the users have to cover to reach the path. Similar applications arise in water resource management and fluid transportation. The problem can be extended to consider an origin/destination flow demand matrix [6] and with p paths instead of one. In this paper we introduce a tighter formulation for the problem, based on a new family of valid inequalities and we study the connection with some related problems. Then we propose a Branch-and-Cut algorithm and report on computational results. The remainder of the paper is organized as follows. In Section 2 we present the problem and the basic formulation [8]. In Section 3 we analyze the basic polyhedral properties of the Median-Path polytope MP(G), we introduce the family of the Lifted Subtour Inequalities and we investigate the relation to the Asymmetric Traveling Salesman Problem (ATSP) polytope and to the Stable Set polytope. In Section 4 we outline the Branch-and-Cut algorithm and, finally, in Section 5 we report on computational results.
2.
Problem definition
Let G(V, A) be a complete directed graph with two cost functions defined on the arcs: h : A → IR+ , representing the construction cost, and d : A → IR+ , representing the distance (or travel time) the users have to cover to reach the facility.
BRANCH-AND-CUT ALGORITHM FOR THE MEDIAN-PATH PROBLEM
217
Let P be a path on G and let V(P) and A(P) denote, respectively, the node set and the arc set of P. Let h(P) =
h uv
uv∈A(P)
be the cost of path P. Let w : V → IR+ be weights associated to the nodes of V , expressing the demand of the users located in v. For each arc uv ∈ A, let cuv = wv d(u, v) be the weighted distance between the nodes u and v. The weighted distance c(P, v) between the path P and the node v ∈ V is defined as min{cuv |u ∈ V(P)}. Let γ (P) =
c(P, v)
v∈V \V(P)
denote the sum of (weighted) distances of P from every node of V \V(P). Let s and t be two nodes of V . Let Pst be a st-path between the source node s and the sink node t. Let Pst denote the family of all the st-paths on G. The Median-Path problem consists of determining a path Pst ∈ Pst minimizing the sum h(Pst ) + γ (Pst ). In applications, h(Pst ) is the cost of setting up a facility located on the path Pst , being γ (Pst ) the aggregate user cost to reach the facility Pst . We introduce a directed weighted bi-graph, having the same set of nodes as G and two parallel arcs for each ordered pair of nodes (u, v): a primary arc, denoted by uv, with cost h uv and a secondary arc, denoted by u v, with cost cuv = wv d(u, v) (figure 1). We denote ˜ with A and A˜ the set of primary arcs and the set of secondary this bi-graph by G(V, A ∪ A), arcs, respectively. On the bi-graph G, a feasible solution of the Median-Path problem is an arborescence ˜ rooted at node s, spanning all the nodes of V and having the L(V, F), F ⊆ (A ∪ A), following two additional properties: (i) the set (F ∩ A) of the primary arcs in L induces a path from the node s to the node t; (ii) for each secondary arc u v belonging to F, neither primary nor secondary arcs of F can leave the node v.
Figure 1.
Primary and secondary arcs.
218
Figure 2.
AVELLA ET AL.
MP-arborescence.
We refer to L as a Median-Path arborescence or MP-arborescence for short (see figure 2). The Median-Path problem can be now defined as the problem of finding a minimum cost MP-arborescence in G. Let us introduce some notations to be used in the following. Let S and T be two disjoint subsets of V . We denote by S | T and by S |T , respectively, the set of primary arcs and the set of secondary arcs having tail in S and head in T . For the sake of clarity we denote ¯ = V \W , δ − (W ) = W ¯ |W , δ + (W ) = W |W ¯ , δ˜ − (W ) = W ¯ ˜|W and δ˜ + (W ) = W ˜|W ¯ , for W some W ⊆ V . For the sake of simplicity we will write δ − (v) = δ − ({v}), δ + (v) = δ + ({v}), δ − (v) = δ − ({v}), δ + (v) = δ + ({v}). Let n = |V | and let V\st denote the set V \{s, t}. For the Median-Path problem, the following natural formulation was proposed in [8]. It will be referred to as the CRC formulation. Binary and xuv are associated with variables xuv the primary and secondary arcs. Let x(I ) = e∈I xe , x( I˜ ) = e∈ I˜ xe for any I ⊂ A and ˜ The CRC formulation is let I˜ ⊂ A. min h uv xuv + cuv xuv uv∈A
u v∈ A˜
+
x(δ (s)) = 1 x(δ − (t)) = 1 −
(1) (2) +
x(δ (v)) − x(δ (v)) = 0, v ∈ V\st x(δ − (v)) + x(δ˜ − (v)) = 1, v ∈ V\st xuv ≤ x(δ − (u)), u v ∈ A˜
(5)
x(W |W ) ≤ |W | − 1,
(6)
W ⊆ V\st , |W | ≥ 2
(3) (4)
xuv ∈ {0, 1}, uv ∈ A xuv ≥ 0, u v ∈ A˜ Constraints (1), (2) and (3) enforce the primary arcs of L to induce a path from the node s to the node t. Constraints (4) ensure the condition that each node of the set V\st has exactly one arc entering. Constraints (5) are “variable upper bound” constraints (VUB). They impose that any user located at the node v can reach the facility at the node u only if the node u belongs to the path. Constraints (6) are the well known Subtour inequalities. We will assume that the root node s does not have entering arcs and that he sink node t does not have leaving primary arcs and entering secondary arcs.
BRANCH-AND-CUT ALGORITHM FOR THE MEDIAN-PATH PROBLEM
3. 3.1.
219
Polyhedral properties of MP(G) Basic properties
Let MP(G) denote the convex hull of the feasible solutions of formulation (1)–(6). We refer to MP(G) as the Median Path polytope. In this subsection we analyze some basic properties of MP(G). Theorem 3.1. The dimension of MP(G) is 2(n − 2)2 − 1 if |V | ≥ 4.
Proof: It can be easily checked that the rank of equality subsystem of MP(G) is 2(n − 1). ˜ = (n − 2)2 + (n − 1)2 , dim(MP(G)) ≤ 2(n − 2)2 − 1. It follows that, since |A| + | A| Any Hamiltonian st-path on the primary arcs, spanning all the node of V , is a MParborescence. If we shrink nodes s and t, any directed tour corresponds to the Hamiltonian st-path spanning all the node of V . It is known [10] that (n −2)2 −n +2 linearly independent tours exist. If we split nodes s and t back, these tours become Hamiltonian st-paths whose incidence vectors are linearly independent. Let u be a node of V\st and let R\u be a st-path, spanning all the nodes of V except u. Let A(Ru ) be the arc set of R\u . The set A(R\u ) ∪ { v u} is a MP-arborescence for all v ∈ V \{u}, u ∈ V\st . So, we have (n − 1)(n − 2) distinct MP\st -arborescences whose incidence vectors are linearly independent. Therefore, dim(MP(G)) ≥ 2(n −2)2 −1 and the proof is complete.
Looking at formulation (1)–(6), we can conclude that the upper bound inequalities xuv ≤ 1 ∀uv ∈ A, xuv ≤ 1 ∀ u v ∈ A˜ do not define facets. However, the nonnegativity constraints do. Proposition 3.1. MP(G) if n ≥ 6.
Let uv ∈ A\{st}. The nonnegativity bound xuv ≥ 0 is facet-defining for
Proof: Let us consider some uv ∈ A. As soon as the nonnegativity constraints are facetdefining for the ATS polytope, it is immediate that (n − 2)2 − n + 1 Hamiltonian st-paths exist whose incidence vectors are linearly independent and they satisfy xuv = 0. Let z be a node of V\st and let R\z be a st-path, spanning all the nodes of V except z and not containing arc uv. Let A(Rz ) be the arcset of R\z . We have A(Rz ) ∩ {uv} = ∅. The set of arcs A(R\z ) ∪ { pz} is a MP-arborescence for all p ∈ V \{z}, z ∈ V\st . So, we have other (n − 1)(n − 2) distinct MP\st -arborescences whose incidence vectors are linearly independent and they satisfy xuv = 0. Proposition 3.2. MP(G) if n ≥ 3.
˜ The nonnegativity bound xuv ≥ 0 is facet-defining for Let u v ∈ A.
220
AVELLA ET AL.
Figure 3.
Support of a lifted subtour inequality.
Proof: The proof is trivial if n = 3. Let n ≥ 4. In Theorem 3.1 we build 2(n − 1)2 linearly independent feasible solutions and exactly one of them satisfies xuv ≥ 0 ∀ u v ∈ A˜ at strict inequality. The proof is complete.
3.2.
Lifted Subtour inequalities
¯ = Here we introduce a new class of rank inequalities valid for MP(G). Let W ⊆ V\st , W V \ W and h ∈ W . We call Lifted Subtour inequality (figure 3) any inequality of the form ¯ x(W |W ) + x(W |W ) + x(W |W\h ) ≤ |W | − 1,
h ∈ W, W ⊆ V\st .
(7)
Inequalities (7) contain all the primary and secondary arcs having both their endpoints ¯ and entering each node of in W , plus all the “external” secondary arcs leaving the set W − − W\h . If we add constraints x(δ (v)) + x(δ (v)) = 1 for all v ∈ W , the Lifted Subtour inequalities (7) become ¯ |W ) + x(W ¯ x(W |h) ≥ 1,
h ∈ W, W ⊆ V\st .
(8)
Theorem 3.2. The Lifted Subtour inequalities (7) is valid for MP(G). It is facet-defining if n ≥ 6 and 2 ≤ |W | ≤ n − 3. Proof: Any MP-arborescence contains a path on primary and secondary arcs from the root node s to node h. It ensures the validity of the Lifted Subtour inequalities in form (8).
BRANCH-AND-CUT ALGORITHM FOR THE MEDIAN-PATH PROBLEM
221
Let n ≥ 6, 2 ≤ |W | ≤ n − 3, h ∈ W . We construct three families of feasible solutions and they form a matrix
C11
C = C21 C31
C12
C13
C21
C23
C31
C33
by the following way. 1. By reduction to the ATSP as in Theorem 3.1, we can conclude that 2(n − 2)2 − n + 1 Hamiltonian st-paths exist whose incidence vectors are linearly independent and they satisfy the Lifted Subtour inequality at equality. These vectors form rows of C11 , C12 , C13 . The columns of C11 , C21 , C31 correspond to the variables of primary arcs. Therefore, rank(C11 ) = 2(n − 2)2 − n + 1, C12 = 0 and C13 = 0. 2. Let u ∈ V\st and let R\u be a st-path, spanning all the nodes of V except u and let ¯ |W )| = 1. The set of arcs A(R\u ) ∪ { |A(R\u ) ∩ (W v u} is a MP-arborescence and ∩ ¯ (A(R\u ) ∪ { v u}) ∩ (W |h) = ∅ for all v ∈ V \ {u}, u ∈ V\st \{h}, and (A(R\u ) ∪ {vh}) ¯ (W |h) = ∅ for all v ∈ W\h . These vectors form rows of C21 , C22 , C23 . The columns of C21 , C22 , C23 correspond to the variables of corresponding secondary arcs ( v u ∈ A˜ for ˜ all v ∈ V \{u}, u ∈ V\st \{h} and vh ∈ A for all v ∈ W\h ). Therefore, C22 is an unitary matrix and C23 = 0. ¯ . We have A(R\W ) ∩ (W ¯ |W ) = ∅. 3. Let R\W be a st-path, spanning all the nodes of W for ¯ The set of arcs A(R\W ) ∩ (v |W ) is a MP-arborescence and (v |W ) ∩ (W |h) = {vh} ¯ all v ∈ W . These vectors form rows of C31 , C32 , C33 . The columns of C13 , C23 , C33 ∈ A˜ for all v ∈ W ¯ ). correspond to the variables of corresponding secondary arcs (vh We have that C33 is a unitary matrix. Summarizing we can conclude that rank(C) = 2(n − 2)2 − 1 and the proof is complete. We observe that inequalities (7) strengthen the CRC formulation since they dominate both the inequalities (5) and (6) of the CRC formulation. 3.3.
Lifting of ATSP polytope facets
Lifted Subtour Inequalites can be obtained by a valid inequality of the Asymmetric Traveling Salesman Problem (ATSP) by sequential lifting. Here we outline a general approach to yield valid inequalities from MP(G) from valid inequalities for the Asymmetric Traveling Salesman Polytope ATSP(G). ˜ Polytope PH corresponds to the polytope Let PH = M P(G) ∩ {xuv = 0 : u v ∈ A}. of Hamiltonian st-path problem. If we shrink nodes s and t, we get the complete directed graph of n − 1 nodes. Each tour on this graph uniquely corresponds to the Hamiltonian st-path. So, we can identify one-to-one mapping between facets of these polytopes.
222
AVELLA ET AL.
Without loss of generality, we pose s = 1, t = n. Let A\1n = A\(δ + (1) ∪ δ − (n)), G n−1 (Vn−1 , An−1 ) be a complete directed graph of n − 1 nodes, ATSP(G n−1 ) be the ATSP polytope on graph G n−1 . The following theorem proves that, given a facet-defining inequality for PH , sequential lifting of secondary arcs provides a facet-defining valid inequality for MP(G). Proposition 3.3. Inequality (G n−1 ) if and only if n−1
a1u x1u +
u=2
n−1
au1 xun +
u=2
uv∈An−1
auv yuv ≤ a0 is valid (facet-defining) for ATSP
auv xuv ≤ a0
uv∈A\1n
is valid (facet-defining) for PH . We point the reader to [4] for the study of the facial structure of ATSP(G). 3.4.
Valid inequalities from Stable Set polytope
Let ˜ STAB(G) = x ∈ {0, 1}|A|+| A| : xuv + x(δ˜ − (v)) ≤ 1
(9)
be the Set Packing polytope defined on a conflict graph where the arc set A˜ are nodes. There is an edge between two nodes of G if and only if there is a constraint in (9) where both the corresponding variables appear. Polytope STAB(G) was studied in Avella and Sassano [1] and Avella et al. [2]. It is obvious that STAB(G) is a relaxation of MP(G). For STAB(G), several families of valid inequalities have been studied. We list two families which are specific to this particular stable set problem. Avella and Sassano (2001) introduced W 2 inequalities which are facet-defining for STAB(G). Let W be a subset of V\st such that 3 ≤ |W | ≤ n − 2. Let H ⊂ (W |W ) be a set of arcs with the property that |H ∩ δ˜ + (w)| = 1, for each w ∈ W . Let W0 = {w ∈ W : H ∩ δ˜ − (w) = ∅}. The following W 2 is valid and facet-defining for STAB(G) x((W |W ) \ H ) + x((V \ W ) |W0 ) ≤ |W | − 2.
(10)
Avella et al. (2003) introduced Cycle inequalities. Let W ⊆ V\st and let C be a bi-directed cycle in (W |W ). The following Cycle inequality is valid for STAB(G)
x(C) ≤
|W |2 . 3
(11)
BRANCH-AND-CUT ALGORITHM FOR THE MEDIAN-PATH PROBLEM
4.
223
The Branch-and-Cut algorithm
Here we outline a Branch-and-Cut (B&C) algorithm to solve the Median-Path problem to optimality. We found useful to extend the formulation by adding auxiliary node variables z v , v ∈ V . The variable z v is 0 if the node v belongs to the st-path, 1 otherwise. With these new variables, the formulation of the problem becomes: min
h uv xuv +
cuv xuv
u v∈ A˜
uv∈A
x(δ + (s)) = 1 x(δ − (t)) = 1 x(δ − (v)) − x(δ + (v)) = 0, x(δ˜ − (v)) = z v , v ∈ V\st
(12) (13) v ∈ V\st
(14) (15)
−
x(δ (v)) + z v = 1, v ∈ V\st z v + x(W\h x(W |W ) + |h) ≤ |W | − 1,
(16) W ⊆ V\st , h ∈ W
(17)
v∈W\h
xuv ∈ {0, 1}, uv ∈ A xuv ≥ 0, u v ∈ A˜ z v ≥ 0,
v∈V
We adopt a solution strategy that attempts the problem size. It consists of four stages: 1. Solution of the LP relaxation. A lower bound LB and reduced costs are computed. 2. Core heuristic. The purpose of this stage is to find a good upper bound UB. We choose a value η and consider the core problem containing only “promising” variables, i.e. variables whose reduced cost is less then a given threshold η. We run the B&C algorithm over the core to obtain an upper bound UB. To generate feasible solutions we use the plunging heuristic described in Section 4.2. We set parameters of LP solver to find more feasible solutions and limit computational time. If UB − LB ≤ η and time limit is not reached, the final solution is optimal and we stop the computation, otherwise we go to the next stage. 3. Separation of ∗ -Cover inequalities. ∗ -Cover inequalities have been introduced in Avella and Sassano [1] Avella et al. [2]. They have a non-standard nature, as they can cut-off feasible solutions. 4. Finding optimal solution. We form a new, “optimal”, core formed by all the variables whose reduced costs are less than UB − LB. In this stage, we run the B&C algorithm over this core without the plunging heuristic. In the B&C algorithm, the branching rule consists of setting either to 0 or to 1 the primary arc variables xuv , i.e. we impose that the arc uv must (or must not) belong to the st-path.
224
AVELLA ET AL.
The skeleton of the B&C procedure is provided by the ILOG CPLEX Callable Library 8.0. This library provides functionalities for managing a global tree search and allows the user to add and delete cutting planes. The cutting planes are held in a cutpool and a set of routines are provided for manipulating the cut pool. The user can write his own cut manager routines and get the library to call these routines during the Branch-and-Bound search. It also provides a flexible set of parameters to manage the B&C algorithm. Node selection has been performed by a best-bound strategy, while the branching variable selection criterion is strong branching. In the next subsections we will describe the main routines we embedded into the B&C algorithm: a logical reduction test, a primal heuristic, separation of ∗ -Cover inequalities and the separation of Lifted Subtour inequalities.
4.1.
A logical reduction test
Reduction tests based on logical implications are very useful in reducing the size of large scale instances [3]. A simple reduction test for the Median-Path problem is based on the following proposition: Proposition 4.1. Let u, v and w be three nodes of V . If the node u belongs to the st-path (i.e. z u = 0) and cwv > cuv , then the arc wv cannot belong to any optimal solution of the Median-Path problem (figure 4).
We use this result in any node on the B&C tree when some variable xup is set to 1. Thus, z u , z p are set to 0 and we can set xwv = 0 ∀w : cwv > cuv and x wv = 0 ∀w, v : cwv > c pv . Such a test allows us to reduce computation time by 10% on average.
Figure 4.
The arc wv is deleted.
BRANCH-AND-CUT ALGORITHM FOR THE MEDIAN-PATH PROBLEM
4.2.
225
LP-based heuristic
To generate feasible solutions we have implemented a LP-based plunging heuristic. Let > 0 be a tolerance parameter. At any node of the B&B tree where the variables associated to nodes are near to integrality, i.e. z u < ∨ z u > 1 − , we constitute a candidate set for the path V1 = {v ∈ V : z u < }. Using Floyd’s algorithm [9], the shortest path P from node s to t in the graph G(V1 , A) is found. If such a path exists, its arcs form the solution for the primary arcs and we allocate every other node to the nearest node in the path to complete the feasible solution with the secondary arcs. 4.3.
∗
-Cover inequalities
∗
-Cover inequalities have been introduced in Avella and Sassano [1] and have been used in Avella et al. [2]. These inequalities have a non-standard nature, as they can cut-off feasible solutions. Let S and T be two disjoint subsets of primary arcs and let r (S) be the rank of S (i.e. x(S) ≤ r (S) for all feasible x). We set x(S) = r (S) and x(T ) = 0. If the new lower bound is worse or equal to the current upper bound UB, then we add the inequality x(S) − x(T ) ≤ r (S) − 1,
(18)
which belongs to the family of the ∗ -Cover inequalities introduced in [1]. The separation procedure is the following: given the fractional solution x¯ , let A F = {i j ∈ A : x¯ i j > 0} and let A0 = A\A F = {i j ∈ A : x¯ i j = 0}. We choose a set S ⊆ A F with the maximum cardinality such that x¯ (S) > r (S) − 1, a set T ⊆ A0 . We set x(S) = r (S) and re-optimize. If the new lower bound is now greater than or equal to UB we have identified a violated inequality (18), otherwise, we enlarge T with a subset of the arcs of A0 \ T and iterate. We stop when either the new lower bound becomes greater or equal than UB or T = A0 . The set T is initialized as T = ∅ and the initial set S is chosen by the greedy way according the fractional weights. 4.4.
Separation of Lifted Subtour inequalities
Given a polyhedron P, a point x¯ ∈ P and a family L of valid inequalities for P, a separation problem consists of finding a valid inequality belonging to L which “cuts off” x¯ . In this section we describe the separation algorithm for Lifted Subtour inequalities. It consists of three steps. Given a fractional solution x¯ , the first step consists of identifying by enumeration all the violated Lifted Subtour inequalities with |W | = 2 and |W | = 3. The second is a preprocessing step. We refer to any node v ∈ V such that x¯ (δ˜ − (v)) = 1 as a 1-node. Let v ∈ V be a 1-node and let W be the node set of any Lifted Subtour inequalities. The Lifted Subtour Inequality defined by the set W is violated if the Lifted Subtour inequality defined by the node set W \v is violated.
226
AVELLA ET AL.
Figure 5.
ˆ ˆ Graph G(V ∪ Vˆ \st , A ∪ A).
It follows that, when searching for violated Lifted Subtour Inequalities, we can remove from the graph all the secondary arcs entering a 1-node. The third and final step is the exact separation algorithm. ˆ ∪ Vˆ \st , A ∪ A), ˆ by the following operations We transform the graph G into the graph G(V (see figure 5): (a) the set of nodes V\st is copied into the set Vˆ \st . We denote by vˆ the copy of the node v ∈ V\st into the set Vˆ \st ; (b) each secondary arc u v ∈ A˜ is re-directed as u vˆ , with vˆ ∈ Vˆ \st . We denote this set of ˆ arcs as A. ˆ ˆ inequality (8) looks like a Cut inequality (see figure 6) On the graph G(V ∪ Vˆ \st , A ∪ A) ¯ |W ) + x(W ¯ | x(W h) ≥ 1,
. W ⊂ V\st , h∈W
It follows that the separation problem for Lifted Subtour inequalities has turned into the problem of determining a minimum capacity cut among all the minimum capacity cuts between s and each node hˆ ∈ Vˆ \st , that is a directed multicut problem.
Figure 6.
Set of arcs of cut inequality.
BRANCH-AND-CUT ALGORITHM FOR THE MEDIAN-PATH PROBLEM
227
By max flow-min cut theorem the value of the minimum multicut is equal to the minimum of the maximum flows which can be sent from s to each of the sink nodes. It follows that the separation problem can be solved iterating a max-flow algorithm for each pair of nodes ˆ with hˆ ∈ Vˆ \st . (s, h), 5.
Computational results
We tested our Branch-and-Cut algorithm on 26 networks from the TSPLIB and on 20 networks from the OR-Library ( p-median instances). All the experiments ran on a Compaq EVO W4000 Personal Computer (Pentium IV-1.8 GHz processor, 1 GB RAM). For every instance, we used the the original costs of the network as costs of primary arcs. The cost associated with any secondary arc uv is the length of the shortest path between nodes u and v according to the costs of the primary arcs. For the sake of simplicity, we assume wv = 1, for each v ∈ V . For the TSPLIB instances all the distances are rounded to the nearest integer. In our computational experience it was crucial to keep the total number of nonzero coefficients as small as possible in order to reduce memory occupation. For this purpose, we implemented a simple but effective cut selection criterion, which consisted of adding to the cut pool only the “most violated” Lifted Subtour inequalities, i.e. those inequalities whose violation exceeds a given threshold δ. In our experience setting δ = 0.5 was a good compromise between speed and quality of the lower bound. In addition to the Lifted Subtour inequalities, we tested the W 2, Lifted Cycle and Lifted Odd-Hole inequalities with their separation procedures described in Avella et al. [2]. The parameter in the plunging heuristic was set to 0.1. The best results for the core heuristic have been yielded by setting a time limit of one hour and η = 0.005 LB, i.e. we 0.995 assume that the integrality gap is around 0.5%. The results are reported in Table 1 for OR-Library instances and in Table 2 for the TSPLIB instances. In each table we use the following notation: N ame is the problem name, n is the number of network nodes. The other columns are related to the number of primary and secondary arcs in the heuristic core (heur ), in the optimal core (opt) and the total number in the network (total). Columns LB, UB and Z ∗ , report respectively on the value of LP-relaxation, on the upper bound from the core heuristic and on the integer optimal value. In the next two columns (#B&C nodes) we report on the number of nodes of the enumeration tree in the core heuristic (heur) and number of B&C nodes over the optimal core (opt). Finally, we report on computation time for each component of proposed approach. The integrality gaps of OR-Library instances are less than 0.5% in all but three instances ( pmed02, pmed05, pmed12) for which the core heuristic has produced optimal values. For the considered TSPLIB instances the integrality gap is usually more than 0.5% and the fourth stage of our approach is essential. The core heuristic has found the optimal value for all but four of them (kr oD100, pr 124, pr 136, pr 152). Only once the time limit has been exceeded (ch150). pmed12, pr 144 and kr oB150 turned out to be the hardest instances and we use ∗ -Cover inequalities to increase the lower bound. Table 3 shows the role of ∗ -Cover inequalities in
430
440
862
803
767
1200
200
200
200
200
300
300
300
300
300
400
400
400
400
400
pmed07
pmed08
pmed09
pmed10
pmed11
pmed12
pmed13
pmed14
pmed15
pmed16
pmed17
pmed18
pmed19
pmed20
165
1263
1226
1294
1242
761
808
372
413
419
100
200
pmed06
160
154
158
165
Heur
pmed05
100
100
pmed04
pmed02
pmed03
100
100
pmed01
n
—
—
—
—
—
—
—
—
811
—
—
—
—
—
—
182
—
—
165
—
Opt
3161
3166
3164
3178
3177
1775
1780
1779
1779
1789
790
791
797
791
793
197
199
199
196
200
Total
# Primary arcs
20542
23206
25714
26376
32851
10645
8065
11216
8509
13103
2784
2763
2722
2818
2111
493
397
545
490
454
Heur
—
—
—
—
—
—
—
—
9275
—
—
—
—
—
—
952
—
—
728
—
Opt
159201
159201
159201
159201
159201
89401
89401
89401
89401
89401
39601
39601
39601
39601
39601
9801
9801
9801
9801
9801
Total
# Secondary arcs
Computational results for the instances of ORLibrary.
Name
Table 1.
4333
4215
4592
4224
4299
4282
4373
4395
4273
4454
3342
4289
4419
4169
3999
3504
4091
3843
3789
3963
LB
4339
4219
4599
4233
4311
4298
4387
4409
4296
4468
3343
4293
4432
4181
4003
3539
4103
3854
3820
3966
UB
4339
4219
4599
4233
4311
4298
4387
4409
4296
4468
3343
4293
4432
4181
4003
3539
4103
3854
3820
3966
Z∗
Objective function value
214
37
119
168
407
159
211
64
457
635
2
6
16
51
9
32
8
2
55
8
Heur
—
—
—
—
—
—
—
—
302
—
—
—
—
—
—
20
—
—
13
—
Opt
# B&C nodes
168
44
45
137
40
17
16
12
105
63
8
4
3
8
5
3
1
1
1
3
lp
2039
261
838
1598
2786
461
617
249
1810
2437
5
4
24
60
18
11
2
1
12
3
Heur
8
—
—
—
—
—
—
—
—
1623
—
—
—
—
—
—
—
—
12
—
Opt
Time (seconds)
2207
305
883
1735
2826
478
633
261
3538
2500
13
8
27
68
23
22
3
2
25
6
Total
228 AVELLA ET AL.
n
48 51 52 76 99 100 100 100 100 100 100 101 105 107 124 127 130 136 144 150 150
152 159 195 198 200
att48 eil51 berlin52 eil76 rat99 kroA100 kroB100 kroC100 kroD100 kroE100 rd100 eil101 lin105 pr107 pr124 bier127 ch130 pr136 pr144 ch150 kroB150
pr152 u159 rat195 d198 kroB200
1383 1242 1720 2602 1793
191 155 232 285 477 579 613 565 562 539 623 541 820 679 759 1315 943 806 1326 1114 1204
Heur
15192 1988 – 3353 2595
886 – 234 – – 1700 891 – 1851 1033 962 – 879 – 4475 1852 1895 9700 14061 2386 2994
Opt
22952 25122 37830 39006 39800
2256 2550 2652 5700 9702 9900 9900 9900 9900 9900 9900 10100 10920 11342 15252 16002 16770 18360 20592 22350 22350
Total
# Primary arcs
750 835 1383 1874 1120
113 110 149 237 333 312 314 315 313 316 349 372 387 361 398 834 504 640 669 690 692
Heur
7680 1396 – 2433 1755
756 – 153 – – 1207 512 – 1456 720 586 – 428 – 3207 1202 1161 6849 9505 1646 2145
Opt
22801 24964 37636 38809 39601
2209 2500 2601 5625 9604 9801 9801 9801 9801 9801 9801 10000 10816 11236 15129 15876 16641 18225 20449 22201 22201
Total
# Secondary arcs
Computational results for the instances of TSPLIB.
Name
Table 2.
57913 40204 2230 12297 27159
29443 391 6798 483 1144 19580 20361 19457 19737 20214 7423 574 13701 37035 53959 105402 5607 91560 50870 6155 23860
LB
63552 40567 2233 12377 27371
30970 391 6834 483 1148 20028 20556 19511 20239 20485 7498 574 13780 37035 56232 106200 5676 93942 55541 6228 24232
UB
63451 40567 2233 12377 27371
30970 391 6834 483 1148 20028 20556 19511 20155 20485 7498 574 13780 37035 55753 106200 5676 93464 55541 6228 24232
Z∗
Objective function value
5 2253 446 252 980
0 2 46 0 81 162 0 89 72 19 241 0 345 3 180 258 156 25 3404 10105 5609
Heur
224 897 – 621 227
62 – 36 – – 449 12 – 262 13 16 – 162 – 196 17 10 306 7312 1249 7810
Opt
# B&C nodes
77 72 43 2275 221
1 1 1 1 4 17 6 16 10 2 18 6 39 27 27 41 47 12 40 77 113
lp
1 1297 380 563 1789
1 0 5 0 54 62 3 46 106 18 180 0 52 8 119 190 71 90 796 3600 2788
Heur
238 295 – 621 157
12 – 4 – – 91 9 – 61 12 13 – 12 – 119 24 11 700 1239 421 3080
Opt
Time (seconds)
316 1664 423 3459 2167
14 1 10 1 58 170 18 62 177 32 211 6 103 35 265 255 129 802 2075 4098 5981
Total
BRANCH-AND-CUT ALGORITHM FOR THE MEDIAN-PATH PROBLEM
229
230 Table 3.
AVELLA ET AL. Computational results of ∗ -Cover inequalities. With ∗ -Cover Name
LB
Without ∗ -Cover
# B&C nodes
Time
LB
# B&C nodes
Time
pmed12
4278
302
1623
4273
523
1705
pr144
51321
7312
1239
50870
10333
1533
kroB150
23902
7810
3080
23860
12041
3405
the solution of the optimal core. Where Name is the problem name, LB is the lower bound, #B&C nodes is the number of B&C nodes, Time is the solution time. References 1. P. Avella and A. Sassano, “On the p-median polytope,” Mathematical Programming, vol. 89, pp. 395–411, 2001. 2. P. Avella, A. Sassano, and I. Vasil’ev, “Computational study of large-scale p-Median problems,” Technical Report 08-03, DIS – University of Rome “La Sapienza,” 2003. 3. P. Avella and A. Sforza , “Logical reduction tests for the p-Median problem,” Annals of Operations Research, vol. 86, pp. 105–115, 1999. 4. E. Balas and M. Fischetti, “A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets,” Mathematical Programming, vol. 58, pp. 325–352, 1993. 5. E. Balas and M. Oosten, “On the Cycle polytope of a directed graph,” Networks, vol. 36, no. 1, pp. 34–46, 2001. 6. G. Bruno, G. Ghiani, and G. Improta, “A multi-modal approach to the location of a rapid transit line,” European Journal of Operational Research, vol. 104, pp. 321–332, 1998. 7. F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, 1990. 8. J.R. Current, C.S. Revelle, and C.S. Cohon, “The Median Shortest Path Problem: A multiobjective approach to analyze cost vs. accessibility in the design of transportation networks,” Transportation Science, vol. 21, pp. 188–197, 1989. 9. R.W. Floyd, “Algorithm 97: Shortest path,” Comm. ACM, vol. 5, 1962. 10. M. Grotschel and M.W. Padberg, “Polyhedral theory,” in The Traveling Salesman Problem, Lenstra, Lawrel and Shmoys, Rinnooy Kan (Eds.), Wiley & Sons, 1985. 11. S.L. Hakimi, E.F. Schmeichel, and M. Labb´e, “On locating path- or tree-shaped facilities on networks,” Networks, vol. 23, pp. 543–555, 1993. 12. M. Labb´e, G. Laporte, and I. Rodriguez Martin, “Path, tree cycle location,” in Fleet Management and Logistics, T.G. Crainic and G. Laporte (Eds.), Kluwer, 1998. 13. M. Labb´e, G. Laporte, I. Rodriguez Martin, and J.J. Salazar, “The median cycle problem,” Technical Report ULB-SMG-01, 2001. 14. E. Minieka, “The optimal location of a path or tree in a tree network,” Networks, vol. 15, pp. 309–321, 1985. 15. E. Minieka and N.H. Patel, “On finding the core of a tree with a specified length,” Journal of Algorithms, vol. 4, pp. 345–352, 1983. 16. C.A. Morgan and P.J. Slater, “A linear algorithm for a core of a tree,” Journal of Algorithms, vol. 1, pp. 247–258, 1980. 17. M.W. Padberg, “A note on zero-one programming,” Operations Research, vol. 23, pp. 833–837, 1975. 18. M. Queyranne and Y. Wang, “Hamiltonian path and symmetric traveling salesman polytopes,” Mathematical Programming, vol. 58, pp. 89–110, 1993. 19. M.B. Richey, “Optimal location of a path or tree on a network with cycles,” Networks, vol. 20, pp. 391–407, 1990. 20. P.J. Slater, “Locating central paths in a graph,” Transportation Science, vol. 16, pp. 1–18, 1982.
