A Comparison of Optimal Methods for Local Access Uncapacitated Network Design

Annals of Operations Research 106, 263–286, 2001  2002 Kluwer Academic Publishers. Manufactured in The Netherlands.

A Comparison of Optimal Methods for Local Access Uncapacitated Network Design C.D. RANDAZZO and H.P.L. LUNA ∗

Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil

Abstract. We compare some optimal methods addressed to a problem of local access network design. We see this problem arising in telecommunication as a flow extension of the Steiner problem in directed graphs, thus including as particular cases some alternative approaches based on the spanning tree problem. We work with two equivalent flow formulations for the problem, the first referring to a single commodity and the second being a multicommodity flow model. The objective in both cases is the cost minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center) to every demand node. The weak single commodity flow formulation is solved by a branch-and-bound strategy that applies Lagrangian relaxation for computing the bounds. The strong multicommodity flow model is solved by a branch-and-cut algorithm and by Benders decomposition. The use of a linear programming solver to address both the single commodity and the multicommodity models has also been investigated. Our experience suggests that a certain number of these modeling and solution strategies can be applied to the frequently occurring problems where basic optimal solutions to the linear program are automatically integral, so it also solves the combinatorial optimization problem right away. On the other hand, our main conclusion is that a well tailored Benders partitioning approach emerges as a robust method to cope with that fabricated cases where the linear programming relaxation exhibits a gap between the continuous and the integral optimal values. Keywords: network design, Benders decomposition, branch-and-bound, branch-and-cut

1.

Introduction

Network design problems have found wide application in computer networks and telecommunication systems, exploring issues of topological design, routing, dimensioning and splicing cables [2,6,17,45]. The hierarchical organization of the telephone, computer and internet networks plays a major role, since high customer concentration levels enable substantial economies of scale for increasing transmission bandwidth. Cost minimization is the objective of most of these operations research models, the main difference among the models referring to the hierarchical level of network design, typically concerning backbones or local access networks. In this work we have solved the local access uncapacitated network design problem implementing three different approaches: branch-and-bound strategy with Lagrangian relaxation, branch-and-cut strategy and Benders decomposition. Our goal is to compare these three techniques, in particular to verify which of them are able to solve the largest and most difficult problems. ∗ Partially supported by CNPq, CAPES and FINEP/MCT (Grant 76.97.1016.00).

264

RANDAZZO AND LUNA

The local access network design problem consists of linking a supply node to its demand nodes satisfying their demand at minimal total cost. The problem presents heterogeneous terminals, and there are also Steiner or transshipment nodes. Each arc of the network has two associated costs: a variable cost depending on the flow through the arc and a fixed cost associated with the installation of the arc. The arcs have no capacity constraints. This problem can be viewed as a generalization of the Steiner tree problem on a directed graph [38]. In fact, if we neglect variable costs at the arcs we will have basically the Steiner problem, and in this sense we are treating an NP-hard problem, for which some computational strategies have been devised [34–37,39,53]. On the other hand, if we neglect fixed costs at the arcs we will have the single source transshipment problem, which can be solved easily [13]. An illustration of the problem is depicted in figure 1. An alternative class of local access network design problems is related to the minimal spanning tree, where a central node has to be linked to all the remainder nodes in the network at minimal cost. These problems have been explored by authors as Gavish [17–19] and Gouveia [26]. This class of problems includes the capacitated and degree constrained minimal spanning tree problems, and some routing and scheduling problems. In most of these problems all the terminals have identical characteristics, and a single line type can be used for connecting the terminals. When the network has heterogeneous terminals, in the sense that they generate different amounts of traffic, and line costs that are dependent of the line capacities we have the Telepak problem. In [18] Gavish proposes one-flow formulations for these problems and applies Lagrangian relaxation with the subgradient optimization procedure to solve the degree constrained minimal spanning tree problem, also solving the capacitated minimal spanning tree problem by Benders decomposition. In [19] a new formulation of the capacitated minimal spanning tree problem is presented as a zero-one integer programming problem and a combination

Figure 1. The local access network design problem.

COMPARISON OF OPTIMAL METHODS

265

of a subgradient optimization procedure and an augmented Lagrangian-based procedure is used to generate tight lower bounds. The original paper of Rothfarb and Goldstein [51] formulates the Telepak problem as a single commodity flow problem, and Gavish [18] shows that it can also be considered as a capacitated minimal spanning tree problem. Several heuristics have been developed for the problem by Goldstein [24] and Chandy and Russel [7]. Gavish [20] presented a mixed-integer mathematical programming formulation of the problem for a general cost structure. Hochbaum and Segev [32] propose two Lagrangian relaxations for the problem and apply the subgradient optimization algorithm to approximate the best Lagrangian multipliers. A recent extension involves two level networks where the first level is composed of concentrators which are connected by high speed lines (optical fiber) and the second level is related to local access networks where sets of terminals are connected to the concentrators via slower lines (coaxial cables) [27]. In the context of telecommunication systems the local access uncapacitated network design problem corresponds to finding a topology on the urban street network that minimizes the total cost of cables and subterranean piping infrastructure necessary to link a switching center and its subscribers. Each subscriber group has a known demand and it is supposed that the switching center is able to supply all the subscribers’ demand. For each arc, the fixed cost is represented by the subterranean infrastructure and the flow dependent cost is represented by the cables to be installed in each arc. The optimal solution of this problem is a tree with root at the switching center. Local access networks with aerial cables can also be met within this formulation, and the fixed cost in such a case can include pole rents. We have used two different formulations of the problem. The first refers to a single commodity and the second is a multicommodity flow model. The reason for using these two formulations is that each compared algorithm has been conceived on the basis of either one or other formulation. The contribution of the paper is to provide three alternative optimal methods to solve the problem, both comparing the efficiency of the methods and showing the importance of the formulations. We have also verified the possibility of solving both formulations with a commercial package of linear and integer programming. In section 2 the two mathematical programming formulations of the problem will be presented. In section 3, the proposed branch-and-bound strategy will be discussed. Section 4 presents the branch-and-cut algorithm proposed to solve the problem. In section 5 is presented the Benders decomposition method applied to the problem. All the proposed solution methods were implemented and our experimental results are reported in section 6. Section 7 closes this work with final remarks and conclusions. 2.

Formulations of the problem

Consider a directed connected graph G(V , E), where V denotes the set of nodes, and E is a collection of arcs which represents the possible pairs of nodes between which a directed transmission link can be installed. Suppose we have an origin node o (the local

266

RANDAZZO AND LUNA

switching center) that must be linked to a number of |K| demand nodes (offices), each of them with a commodity flow requirement of dk where k ∈ K and K ⊆ V . With appropriate structural and operational costs, the problem is to find a minimal cost arborescence that links the switching center to all the spatially distributed offices. We remark here that all flows originate at the switching center. Define:
1 if a direct transmission link is placed in arc (i, j ), xij = 0 if not; bij : fixed (structural) cost to install a direct transmission link in arc (i, j ); we suppose bij = β dij where dij is the distance (in meters) between i and j , and β is the linkage structural cost per meter. The variables xij and the parameters bij , β and dij will allways have the above interpretations in the two flow formulations that follows. 2.1. Single commodity flow formulation We present here the mathematical formulation of the local access network design problem using a single commodity flow formulation. We use the definitions above and define also: fij : flow passing through arc (i, j ); cij : variable (operational) cost to transmit one unit of flow through arc (i, j ); we suppose cij = γ dij , where γ is the total cost per meter to transfer one unit of flow. The mathematical model, M1, is:  (bij xij + cij fij ) min (i,j )∈E

subject to



foj = fik −

(i,k)∈E



(i,j )∈E

fij




(2)

dk ,

k∈K

(o,j )∈E



(1)



fkj = dk ,

∀k ∈ K,

(3)

(k,j )∈E

fij − 



fj l = 0,

∀j ∈ V − K − {o},

(4)

(j,l)∈E

 dk xij ,

∀(i, j ) ∈ E,

(5)

k∈K

fij  0, ∀(i, j ) ∈ E,  xij  |K|,

(6) (7)

(i,j )∈E

xij ∈ {0, 1},

∀(i, j ) ∈ E.

(8)

COMPARISON OF OPTIMAL METHODS

267

The first term of the objective function (1) gives the total fixed cost of constructing the used arcs, and the second gives the total cost of sending flow through the arcs. Constraint (2) ensures that the supply node capacity is equal to the sum of demands in all demand nodes. Constraints (3) impose the flow requirements in the demand nodes and constraints (4) ensure the flow conservation for the Steiner nodes. Constraints (5) express the fact that the flow through an arc must be zero if this arc is not included in the design. It is desirable to use  the smallest coefficient possible on the right-hand side of this inequality. The value k∈K dk always works, although some edges of certain graphs may permit smaller values to be used (the intent of this inequality is more to raise the value of xij than to limit the value of fij ). Constraints (6) establish that the flow through an arc is not negative and constraint (7) establishes that at least |K| arcs must be selected because an optimal solution is an arborescence connecting the supply node to its demand nodes. Constraints (8) define the binary variables xij . This formulation of the problem could be strengthened by adding a binary variable yj for each Steiner vertex j . In this case, constraint (7) could be replaced by the following:   xij = |K| + yj . (i,j )∈E

j ∈V −K

The use of the y variables enables the addition of costs associated with used Steiner vertices, which would be important in other applications. However, we have chosen to work here with a simpler model which does not use vertex variables. The idea with the single commodity model is to explore the advantages of simplicity and smaller scale, while the next model looks for the advantages of redundancy and theoretical properties. 2.2. Multicommodity flow formulation We make some alternative definitions for the flow variables and cost parameters in order to construct the multicommodity flow formulation: fij k : flow passing through arc (i, j ) and destined to demand node k; cij k : variable (operational) cost to transmit one unit of commodity k through arc (i, j ); we suppose cij k = γ k dij , ∀k ∈ K. This model allows the variable cost to be dependent on both the commodity and the arc, but in accordance with model M1 the variable cost should only be dependent of the arc (i, j ), that is, we will make γ k = γ , ∀k. This assumption will make the comparison among the different methods more uniform. The mathematical model, M2, is:     cij k fij k bij xij + (9) min (i,j )∈E

subject to

 (o,j )∈E

k∈K

foj k = dk

for node o and ∀k ∈ K,

(10)

268

RANDAZZO AND LUNA



fikk = dk ,

(i,k)∈E



(i,j )∈E

fij k −



∀k ∈ K,

(11)

fj lk = 0,

∀j ∈ V − {o} and j = k and ∀k ∈ K, (12)

(j,l)∈E

fij k
dk xij , ∀(i, j ) ∈ E and ∀k ∈ K, fij k  0, ∀(i, j ) ∈ E and ∀k ∈ K, xij ∈ {0, 1}, ∀(i, j ) ∈ E.

(13) (14) (15)

The first term of objective function (9) accounts for the total fixed cost of utilizing the arcs and the second term is associated with the total cost of sending flows of all commodities from the source node to the demand nodes through the arcs. Constraints (10) ensure that the total flow of commodity k that originates from the source node is equal to the demand of node k and constraints (11) impose that the total flow of commodity k arriving at demand node k is equal to its demand, dk . Constraints (12) ensure the flow conservation for each Steiner node. The x and f coupling constraints (13) ensure that no flow is allowed on arc (i, j ) unless the fixed cost bij is paid. The fact that the flow of any commodity through an arc is not negative is guaranteed by constraints (14). Finally, constraints (15) state that the variables xij are binary. It is important to note that the linear relaxation of model M2, that we call here M2Lin, generates a quasi-integral polytope. A quasi-integral polytope is one in which the edges of the convex hull of its integer points are also edges of the polytope itself [31]. This means that there exists a path through extreme integer points that finds the optimal integer solution, if it exists. Another important theoretical property is that, for β = 0 and dk = 1, ∀k ∈ K the model is reduced to the multicommodity flow formulation of the Steiner problem in directed graphs, as presented by Maculan and others [11,23,40,54]. As a result, the strong formulation given by the objective function (9) and constraints (10)–(15) also includes as a particular case the linear programming formulation for the shortest directed spanning tree problem, also introduced by Maculan [44]. All these theoretical properties can help to understand why, in many instances of the general problem, a linear programming relaxation of model M2 can automatically lead to optimal integral solutions.

3.

Branch-and-bound strategy

Branch-and-bound is a well-known methodology similar to a divide-and-conquer strategy for solving NP-hard optimization problems [22]. It divides the original problem into smaller disjoint subproblems, fixing the value of a variable (branch). For each subproblem, an optimistic value for the objective function is a lower bound and a feasible solution is an upper bound for a minimization problem. The lower bound determines either if the division must continue or if the subproblem can be eliminated. When we reach a subproblem in which all variables are integer the value of the objective func-

COMPARISON OF OPTIMAL METHODS

269

tion can be calculated. The optimal value can be determined comparing the value of the objective function of all subproblems in which all variables have integral values. The concept of lower and upper bounds is fundamental for the branch-and-bound algorithm. The lower bounds can be obtained using Lagrangian relaxation [16], that decomposes the original problem into subproblems that can usually be solved in polynomial time. The model M1 has been used as a basis for our branch-and-bound algorithm. We have applied Lagrangian relaxation to this model to generate lower and upper bounds for the problem [48]. 3.1. Getting lower bounds: Lagrangian relaxation Lagrangian relaxation methods decompose the problem into subproblems by eliminating complex constraints and reducing its complexity. It was developed in the 1960s and has been applied to combinatorial optimization since the pioneering work of Held and Karp [29,30] on the traveling salesman problem. Lagrangian relaxation involves [50]: (1) taking an integer (or mixed-integer) programming formulation of the problem; (2) attaching Lagrangian multipliers to some of the constraints in this formulation; the constraint is relaxed by using the Lagrange multiplier to incorporate the constraint into the objective function; (3) solving (exactly) the resulting integer (or mixed-integer) program. The solution value obtained from step 3 gives a lower bound on the optimal solution to the original problem. We can use this lower bound in our branch-and-bound algorithm. This technique has been applied to model M1. The following constraints (5) have been relaxed:   dk xij , ∀(i, j ) ∈ E. fij
k∈K

These coupling constraints were chosen because they are associated with two sets of variables, x and f, separating the problem in two parts. Therefore, it can be considered as a complicating constraint of the problem, and in this sense it is a natural candidate to be relaxed. Moreover, it is possible to easily obtain a feasible solution from the solution of the obtained relaxed problem, as it will be shown later. In [33] a different approach is proposed, where instead the flow conservation constraints (equations (10)–(12)) are relaxed in model M2. As the solution of this relaxed problem does not produce any solution to the problem, other means of generating feasible solutions are needed, and the Benders decomposition method is used for this purpose. Let λ  0 be the set of Lagrangian multipliers associated with the constraints (5). Thus, the new objective function is given by:        cij fij + bij xij + dk xij λij . (16) fij − min (i,j )∈E

(i,j )∈E

(i,j )∈E

k∈K

270

RANDAZZO AND LUNA

The relaxed problem, RPλ , consists of the objective function (16) and the constraints (2)–(4) and (6)–(8) of the original problem M1. It is then possible to decompose the relaxed problem into two polynomial and independent subproblems:  (cij + λij )fij (17) RP1: min (i,j )∈E

subject to the constraints (2)–(4) and (6).      dk λij xij RP2: min bij − (i,j )∈A

(18)

k∈K

subject to the constraints (7) and (8). The subproblem RP1 is a single-source uncapacitated linear minimum-cost network flow problem, because its arcs have no capacity constraint. Therefore, RP1 is an instance of the shortest path problem. The subproblem RP2 is simply a sorting problem and can be solved by inspection. When using Lagrangian relaxation we are interested in the best possible lower bounds. For this, we apply the subgradient optimization algorithm [15]. Let λ∗ be a best set of Lagrangian multipliers, which corresponds to an optimal solution for the dual problem of model M1. The method commonly used to compute the vector λ∗ is based on subgradients since the objective function of the dual problem is not differentiable. The method starts by using an arbitrary vector λ0 and generates a sequence of λk by the following rule: λk+1 = λk + t k s k ,

(19)

where t k is a nonegative scalar called step size and s k is the subgradient vector, given by the errors in satisfying constraints (5). The step size t k is given by: tk = ρ

UB − LB , s k 2

(20)

where: ρ:

scalar in range (0, 2];

UB: upper bound for the problem; LB: lower bound obtained by solving the relaxed problem. When the subgradient optimization algorithm is applied to the root node of the branch-and-bound tree, ρ is initialized to 2 and this value is the same for 30 iterations (maximum number of iterations). When the number of iterations is equal to the maximum, the values of ρ and of the maximum number of iterations are divided by 2 (the maximum number of iterations is divided by 2 only if its value is greater than 10). The termination criteria is ρ < 0.001 or t k  0.00001. For the other nodes of the branchand-bound tree, the value of ρ is fixed to 1 and the subgradient optimization algorithm is repeated for 30 iterations.

COMPARISON OF OPTIMAL METHODS

271

The advantage of the method is related to the low computational effort to generate feasible solutions. The main disadvantage is that there is no guarantee that the lower bounds will increase monotonically. For more details about the method see [15,30]. 3.2. Getting upper bounds We apply a simple and efficient way of getting upper bounds. The flows obtained after solving the relaxed problem RPλ are feasible in the primal problem because they satisfy the demand requirements. Additional work necessary is to compute the cost of these flows using the original costs cij and adding to it the overhead costs bij for each arc (i, j ) that supports flows. 3.3. Choosing the branching variable The strategy of choosing the branching variable is fundamental in the performance of the branch-and-bound algorithm. Clever choices of branching variables coupled with the use of good lower and upper bounds can reduce significantly the number of nodes explicitly searched in the tree. Obviously, this reduces the execution time. The adopted strategy was proposed by [12] and the algorithm is the following: function ChoseArcNoCycling T ←K for ∀(i, j ) fixed to 1 T ← T ∪ i ∪ j; end for for ∀(i, j ) ∈ E if (i, j ) is not fixed and i ∈ T and j ∈ /T return (i, j ); end if end for end function 3.4. Variable fixing The new lower bound that would result from forcing one arc in or out of the solution can be easily estimated from the Lagrangian relaxation. If the lower bound resulting from imposing some condition to the Lagrangian relaxation is above the best upper bound, then the condition in consideration cannot be satisfied in the optimum. This idea was inspired by the variable fixing procedures developed in [10] to solve the p-median problem, with very good results in practice.

272

4.

RANDAZZO AND LUNA

Branch-and-cut algorithm

The branch-and-cut algorithm [28,47] is an exact method that works like the branchand-bound algorithm, but in each node of the branch-and-bound search tree it solves a mixed-integer program by a cutting plane algorithm [25]. The branch-and-cut method that we compare here is the result of a master’s thesis [52]. This algorithm has been tested extensively, and the author has allowed us to test the algorithm to obtain the results that we present in this article. This cutting plane algorithm works with the linear relaxation of the program. In each step of this algorithm, one linear program is solved and if the solution is not integer, some constraints that cut off the current fractional solution are added. These constraints cut a part of the feasible space of the problem and if they do not cut any integer solution, they are called valid cut inequalities. So, a set of linear programs needs to be solved, each of them built from the last solved program and with some added constraints chosen from a known set of constraints that are violated by the current solution. The node is branched when it yields a fractional solution and no constraints are known to be added. A node is a leaf of the branch-and-cut search tree either if it results in an integer solution, or if its solution is infeasible, or if it results in a fractional feasible solution whose value is worse than the best integer solution previously found. This branch-and-cut algorithm is based on model M2. To turn this mixed-integer program into a linear one, we replace the integrality constraints on xij (constraints (15)) by the corresponding linear constraints 0
xij
1,

∀(i, j ) ∈ E.

Constraints (13) are aggregated in the following set of constraints:   fijk
dk xij , ∀(i, j ) ∈ E. k∈K

(21)

(22)

k∈K

In this way, we have the model M3 that is obtained from the model M2 by replacing constraints (13) by constraints (22) and the integrality constraints (15) by constraints (21). The original constraints (13) are used as cut inequalities and are added to the problem as necessary. Initially, the linear program with no constraint of the set (13) is solved. The solution that is found can violate some of these constraints because they are not directly included in the program, since only the aggregated version (22) is considered. Next, the violated constraints of the set (13) are added to the program, and it is solved again. This process is repeated until an integer solution is found or there are no violated constraints to be added. Since violated inequalities are added at each tree node we have a branch-and-cut strategy. 4.1. Choosing the branching variable The chosen variable for branching is the xij with the highest objective function coefficient (bij ). This variable has its value initially fixed to 1 and after to 0. That is, the first

COMPARISON OF OPTIMAL METHODS

273

subproblem deleted from the list of unexplored problems is that where the variable is fixed to the value 1. 5.

Benders decomposition of the problem

Benders partitioning method was published in 1962 [5] and was initially developed to solve mixed integer programming problems. The computational success of the method to solve large scale multicommodity distribution system design models has been confirmed since the pioneering paper of Geoffrion and Graves [21]. Magnanti and Wong [43] proposed a methodology to improve Benders decomposition algorithm performance when applied for solving mixed-integer programs. They introduced a technique for accelerating the algorithm convergence and developed a theory that distinguishes “good” formulations for those problems that have different, but equivalent, possible formulations. In [42] Benders decomposition is applied to solve the uncapacitated network design problem and adapted to be as efficient as possible, then solving problems with undirected arcs. Now we specialize the method for an adequate variant of model M2. 5.1. Problem manipulation A Benders partitioning method essentially relies on a projection problem manipulation, that is then followed by the solution strategies of dualization, outer linearization and relaxation. From the viewpoint of mathematical programming we can conceive a projection of problem M2 onto the space of the topological variables x, thus resulting the following implicit problem to be solved at a superior level:  bij xij + v(x), (23) min x∈X

(ij )∈E

where X = {x | for x fixed there exists a feasible flow f satisfying (10)–(14)} and where v(x) is calculated by the following problem to be solved at an inferior level:   cij k fij k subject to (10)–(13) for x fixed. (24) v(x) = min f
0

(i,j )∈E k∈K

The flow feasibility requirement related to a topological variable x ∈ X implies that the components for which xij = 1 compose an arborescence rooted at the origin o and destined to every demand node k ∈ K. At the inferior level, the right-hand side of the primal problem (24) is dependent on the x values, but the feasible solution set of the corresponding dual problem is always the same for any fixed x. With the use of previously generated extreme points of this constant dual set, it is possible, at the superior level of each Benders iteration, to have a better under-estimation of the operational cost h related to any topology x. The idea is to choose  at each iteration h a solution x that minimizes the sum of the known fixed cost (i,j )∈E bij xij plus the best known under estimation of the operational cost related to the topology x h . The method combines the

274

RANDAZZO AND LUNA

use of dualization, outer linearization and relaxation in such a way to approximate the projected problem (23). We analyse now the subproblem to provide further detail on the choices made. 5.2. Subproblems For a fixed arborescence Ah , associated with the vector x h , the computation of a minimal h be cost flow v(x h ) can be separated in a series of trivial network flow problems. Let Cok the path, from the source node to the demand node k, that has been defined by the master problem of iteration h. We now state in detail the primal-dual pair to be solved for each commodity k ∈ K. 5.2.1. Primal subproblem for commodity k when x = x h  min cij k fijhk (i,j )∈E

subject to



fojh k = dk

(25)

for the root o,

(26)

(o,j )∈E



h fikk = dk ,

(i,k)∈E



fijhk −

(i,j )∈E

−

fijhk

fijhk



(27) fjhlk = 0,

∀j ∈ V − {o} and j = k,

(28)

(j,l)∈E

 −dk xijh ,

 0,

∀(i, j ) ∈ E,

(29)

∀(i, j ) ∈ E.

(30)

The trivial and unique solution of the problem is:
h h h fij k = dk if (i, j ) ∈ Cok ⊆ A , 0 otherwise.

(31)

5.2.2. Dual subproblem for commodity k when x = x h The dual problem associated to the subproblem given by the objective funtion (25) and constraints (26)–(30) is:    h h h h xij αij k (32) max dk pkk − pok − p h ,α h
0

subject to

(i,j )∈E

pjhk

−

h pik

− αijh k
cij k ,

∀(i, j ) ∈ E.

(33)

This dual problem has many feasible solutions in contrast to the primal problem h ⊆ Ah we have that has a unique trivial solution. Since fijhk = dk > 0, ∀(i, j ) ∈ Cok from the complementary slackness condition that: h − αijh k = cij k , pjhk − pik

h ∀(i, j ) ∈ Cok ⊂ Ah ,

(34)

COMPARISON OF OPTIMAL METHODS

275

in such a way that we can construct, associated with the primal solution x h , the following dual feasible solution: h = 0, ∀k ∈ K, for the origin node o, pok h h h pj k = pik + cij k , ∀(i, j ) ∈ Cok ⊂ Ah ,

(35) (36)

h 0 = pik , ∀i ∈ V − V h , pik h αijh k = 0, ∀(i, j ) ∈ Cok ⊂ Ah ,

(37) (38)

h − cij k , αijh k = pjhk − pik

αijh k

= 0,

h ∀(i, j ) ∈ E − Ah such that pjhk − pik > cij k ,

∀(i, j ) ∈ E − A such that h

pjhk

−

h pik


cij k .

(39) (40)

The systematic evaluation of the dual variables with commodity meaningful values is a clue for an efficient implementation. Here the two series of dual variables can be h represents the price of the establishinterpreted as price information. Each variable pik ment of the communication k (k ∈ K) from the origin node o until node i (i ∈ V ) in iteration h (h = 1, . . . , H ). On the other hand, each variable αijh k gives for commodity k the value of an additional unit of capacity at arc (i, j ) ∈ E. The dual variable αijh k evaluates for commodity k the maximal reduction in the operational cost that could be gained with the introduction of arc (i, j ) in the solution. In the case of transportation systems, it can also be understood as a tax to be paid with the use of arc (i, j ) in order to maintain the distribution agents with no positive profit. Remark that the constant dual solution set (33) represents spatial prices for which there is no positive profit for any distribution agent that pays the cost cij k to flow commodity k through arc (i, j ). 5.3. Master problem With the objective of producing a feasible solution from the master problem of the Benders decomposition we added some redundant constraints to the model M2. We will call this extended model M2Bend. These new constraints try to guarantee that the arcs of the solution of the master problem constitute a tree from the origin node o to all the demand nodes k ∈ K. Nevertheless, these constraints are not sufficient to guarantee this. For some problem instances, the solution of the master problem can have cycles and our algorithm treats this special situation properly. The redundant constraints are the following: 

xoj  1 for node o,

(41)

xik = 1,

∀k ∈ K,

(42)

xil  0,

∀l ∈ V − K − o,

(43)

(o,j )∈E



 (l,j )∈E

(i,k)∈E

xlj −



(i,l)∈E

276

RANDAZZO AND LUNA



 (l,j )∈E

xil  

xlj

(l,j )∈E

(i,l)∈E

xij + xj i
1,

1

,

∀l ∈ V − K − {o},

∀(i, j ) ∈ E.

(44) (45)

Constraint (41) establishes that at least one arc leaves the origin node. Constraints (42) establish that only one arc arrives at each demand node. Constraints (43) ensure that the number of arcs leaving a Steiner node is not smaller than the number of arcs arriving at it. Constraints (44) express the fact that if at least one arc leaves node l, then at least one arc enters node l. Constraints (45) avoid the occurrence of cycles involving two arcs. The mathematical model of the master consists of the following objective function:  bij xij + t (46) min (i,j )∈E

subject to the Benders cuts constraints     h h dk pkk − αij k xij , t k∈K

h = 0, 1, 2, . . . , H,

(47)

(i,j )∈E

and also subject to the constraints (41)–(45) and (15). The parameter H + 1 evaluates the number of cuts that can be taken into account at each Benders iteration. For given h and k the correspondent parcel of constraints (47) provides a lower bound on the cost of the flow that leaves the origin node to the demand node k. The variable t that appears in objective function (46) is the best known lower bound on the total operational cost. 5.4. Algorithm The implemented Benders decomposition algorithm is presented below. It is important to remark that this algorithm explores some characteristics of the problem in such a way to efficiently solve a greater number of instances. In practice, we have verified that for most of the problem instances, the linear relaxation of the model M2, that we call M2Lin, can find the optimal integer solution of the original problem. So, we decided to solve initially model M2Lin before applying Benders decomposition method. If the linear relaxation cannot find the optimal integer solution, then the shortest path from the origin node to all the demand nodes and the minimum spanning tree of a reduced graph are computed. These two feasible solutions are used to initialize the dual variables. Next, in each iteration, one master problem and a series of subproblems are solved until the lower and upper bounds are equal. The steps of the algorithm are the following: (1) Solve the linear program M2Lin. If the solution is integer, then stop. The optimal solution of the problem was found. (2) Use Dijkstra’s algorithm to find the shortest path from the origin o to every node of the network. Let E 0 be the arcs of the arborescence that contains the shortest

COMPARISON OF OPTIMAL METHODS

277

paths to all the nodes and let T (V 0 , A0 ) be the correspondent arborescence that links the origin o to all demand nodes k ∈ K (xij0 = 1, ∀(i, j ) ∈ A0 and xij0 = 0, ∀(i, j ) ∈ E − A0 ). Make 0 = 0, ∀k ∈ K, for the origin node o, pok 0 0 pj k = pik + cij k , ∀(i, j ) ∈ E 0 , ∀k ∈ K, through E 0 ,

αij0 k = 0,

∀(i, j ) ∈ E 0 , ∀k ∈ K, through E 0 ,

αij0 k = 0,

∀(i, j ) ∈ E − E 0 .

Compute the cost associated with T (V 0 , A0 ) (the sum of the fixed cost of the arcs in E 0 plus the sum of the variable costs of sending the flow requirement of each demand node k from  the origin to the demand node). This value gives an initial  0 0 , and (x 0 , f 0 ) is an incumbent upper bound, UB = (i,j )∈A0 bij xij + k∈k dk pkk solution. Also, the shortest paths solution provides the minimal total variable cost among all possible arborescences, and thus we can use it to initialize a lower bound, 0 . LB = k∈k dk pkk (3) Use Prim’s algorithm to find a minimal spanning tree in a reduced graph that contains only the origin and the demand nodes k ∈ K. This reduced graph is constructed as proposed by Mehlhorn in [46] using a single shortest-path computation. Let T (V 1 , A1 ) be the associated Steiner arborescence, that is contained in the original graph G(V , E), and that links the origin o to all demand nodes k ∈ K (xij1 = 1, 1 is the set of the arcs in the path ∀(i, j ) ∈ A1 and xij1 = 0, ∀(i, j ) ∈ E − A1 ). Cok 1 from the origin to the demand node k through A . Set the iteration counter h = 1. (4) Compute the values of the dual variables as shown by the equations (35)–(40). A new value for the upper bound is calculated and if this value is less than the current upper bound then the current upper bound is updated. If the lower bound is greater than (or equal to) the upper bound, then stop. Add a new cut to the master problem. (5) Solve the master problem. It provides a lower bound for the problem. If the lower bound is greater than (or equal to) the upper bound, then stop. (6) Solve the subproblem. To solve it, initially verify if the arcs selected in the master problem build an arborescence from the origin to all demand nodes. If yes, set h = h + 1, let T (V h , Ah ) be the arborescence that links the origin o to all demand h be the set of the arcs nodes k ∈ K, contained in the original graph G(V , E), let Cok h in the path from the origin to the demand node k through A , and go to step 3. Else, the solution of the master problem is infeasible in the subproblem in the sense that it generates a cycle in the path from the origin to one or more demand nodes. In this case, the cycles are identified and constraints to avoid them are added to the master problem model and no new upper bound is generated. To identify the cycle in the path from the origin to a demand node, a backward search from the demand node is executed until a node is repeated. Let n be this node. A cycle avoiding constraint is

278

RANDAZZO AND LUNA

generated considering the arcs from the demand node to n in both directions. The sum of the variables xij corresponding to these arcs must not be greater than the number of arcs from the demand node to n (considering only one direction of the arcs and the second time that n is found). After the cycle avoiding constraints are added, the master problem must again be solved, then go to step 5. 6.

Computational results

The tests were executed in a Sun Ultra Enterprise 3000 with two 250 MHz UltraSPARC processors and 512 Mbytes of RAM memory. The operational system is Solaris 2.5.1. The Benders decomposition algorithm was implemented in C++ with CPLEX 5.0 callable library. The branch-and-bound algorithm was implemented in C++ and the branch-and-cut algorithm in C with CPLEX 5.0 callable library. Table 1 shows the dimensions of the networks and of the corresponding mixed integer formulations for the tested problems. The test problems can be divided into three classes: the first class contains problems that are Euclidean graphs randomly generated using a procedure similar to that presented in [1]. This procedure has been used extensively for creating testing instances of the Steiner problem. For all problems of this class, the linear relaxation of the multicommodity flow formulation (model M2) produces the optimal solution of the problem. So, we have created a second class of problems, for which the linear relaxation of M2 does not find an optimal integer solution. The procedure to create these problems has been inspired by the example presented in [33]. In figure 2 we give a small example with the structure used as a basis for the problems of this class. In this figure, each edge represents two directed arcs, one for each direction. For creating a network with k demand nodes, we create n layers, each one with k nodes, and the demand nodes are always in the last layer (the layer of nodes which are more distant from the origin). From the second to the last layer of k nodes, there are arcs from each node of the layer i to all the nodes of the layer i + 1, and all these arcs have the same costs (fixed cost equal to 10 and variable cost equal to the fixed cost divided by the number of demand nodes), with an exception made for the horizontal arcs, that have fixed cost equal to 20 and variable cost equal to the fixed cost. The values 10 and 20 used in the costs are not important, what is important is the relation between them. The third class of problems refers to those obtained from some of Beasley’s graphs [4] for the Steiner problem. We have chosen as the origin node the first demand node of each selected Beasley’s graph, and we have assigned one unit of flow for each of the remainder demand nodes. Table 2 shows the results obtained from the solutions of the problems by CPLEX 5.0. We have solved the problems using both the single commodity (model M1) and the multicommodity (model M2) flow formulations. Remember that for the problems of the classes one and three the linear relaxation of the model M2 provides automatically an integer optimal solution. So, when we solve these classes of problems using model M2 no branch-and-bound node is generated. This fact does not mean that solving the problem by model M2 we will always have the smaller times. Among the

COMPARISON OF OPTIMAL METHODS

279

Table 1 Network dimensions for test problems. Problem number

|V |

|E|

|K|

β/γ

Number of variables in model M1

Number of variables in model M2

Integer

Continuous

Integer

Continuous

36 30 60 60 80 90 100 110 120 130 140 150 170 200 220

36 30 60 60 80 90 100 110 120 130 140 150 170 200 220

36 30 60 60 80 90 100 110 120 130 140 150 170 200 220

108 120 240 180 320 450 600 770 960 1040 1120 1350 1700 2400 2640

CLASS 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

12 16 16 20 25 30 35 40 46 50 55 60 65 70 80

36 30 60 60 80 90 100 110 120 130 140 150 170 200 220

3 4 4 3 4 5 6 7 8 8 8 9 10 12 12

0.1 0.1 0.1 10 10 10 10 10 10 10 10 10 10 10 10

CLASS 2

16 17 18 19 20 21 22 23 24 25

21 31 31 31 36 41 41 49 61 81

112 220 240 240 322 416 440 624 912 1680

4 5 6 10 7 8 10 12 12 20

4 5 6 10 7 8 10 12 12 20

112 220 240 240 322 416 440 624 912 1680

112 220 240 240 322 416 440 624 912 1680

112 220 240 240 322 416 440 624 912 1680

448 1100 1440 2400 2254 3328 4400 7488 10944 33600

CLASS 3

B1 B2 B5 B6 B16

50 50 50 50 100

126 126 200 200 200

8 12 12 24 16

10 10 10 10 10

126 126 200 200 200

126 126 200 200 200

126 126 200 200 200

1008 1512 2400 4800 3200

Figure 2. An example of a network with a nonintegral LP-solution.

280

RANDAZZO AND LUNA

Table 2 Comparison between single commodity and multicommodity flow formulations. Problem size

Single commodity flow formulation LR

CPLEX solution Simplex iterations

Multicommodity flow formulation LR

gap (%)

B&B nodes

Time

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14 P15

17.43 3.83 6.04 19.52 24.21 30.40 37.20 31.23 21.12 21.37 32.68 39.48 29.86 20.52 25.58

3 0 11 12 26 32 27 57 36 56 38 367 146 399 537

25 0 146 131 311 494 392 576 366 791 762 4473 1913 4984 8555

0.22 0.14 0.22 0.23 0.30 0.36 0.33 0.43 0.44 0.57 0.62 2.20 1.15 2.88 4.68

P16 P17 P18 P19 P20 P21 P22 P23 P24 P25

7.14 5.88 6.25 6.83 5.88 5.56 5.56 5.00 1.30 3.57

31 102 110 112 122 257 399 879 3076 2921

453 1902 2403 2859 3147 7379 20080 56938 180195 594134

0.35 1.26 1.56 1.82 2.39 6.09 23.13 97.47 444.03 2814.32

B1 B2 B5 B6 B16

37.54 25.76 35.41 24.98 29.61

31 31 263 809 2514

275 312 2657 8346 39263

0.38 0.33 1.55 4.31 28.75

gap (%) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3.70 4.08 4.92 5.77 4.94 4.85 4.11 4.71 1.18 3.38 0 0 0 0 0

CPLEX solution B&B nodes

Simplex iterations

Time

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

31 0 153 114 162 300 252 554 668 432 1282 721 805 5381 3248

0.19 0.21 0.26 0.24 0.38 0.39 0.50 0.84 1.29 0.94 2.56 1.20 1.72 19.60 15.76

8 321 130 18 350 464 178 264 812 *

782 18280 19944 7980 90015 197274 105055 395588 2249835 *

0.86 45.35 59.79 41.11 452.17 1472.40 969.57 7073.76 63729.27 *

0 0 0 0 0

177 639 1672 7057 19773

0.66 1.25 4.55 65.61 341.02

20 problems of classes 1 and 3 there were 19 instances for which it was faster to solve the problem by model M1, instead of solving it by model M2. Only for problem P1 it was faster to solve the problem using model M2. For the problems of the class two, the linear relaxation of the model M2 does not give an integer optimal solution. For all problems of this class, the solution using model M1 was more efficient than using model M2. When the problem was modeled using model M2, the solution of problem P25 could not be found in 24 hours, but using model M1 the solution was found in 46.91 minutes. The number of branch-and-bound nodes generated when using the model M2 was smaller than that obtained when using the model M1 for 25 problems, but the di-

COMPARISON OF OPTIMAL METHODS

281

mension of the problem solved in each branch-and-bound node with model M2 is greater than that with model M1. For this reason, the times obtained with the model M2 were greater than those obtained with the model M1 for almost all problems. In general, we can say that the use of a commercial package of linear programming can be considered for solving the local access network design problem, but we cannot say a priori if it is better to use the package with a single or a multicommodity flow formulation of the problem. Table 3 reports the results obtained with the solution of the problems by the three implemented methods. The execution time of the tests marked with * was greater than 24 hours and the corresponding results are not available. The iteration number of the Table 3 Comparison among Benders decomposition, branch-and-bound and branch-and-cut methods. Problem size

Benders decomposition

Branch-and-bound

Initial Iterations Time (s) Initial GAP GAP

Branch-and-cut

Nodes

Time (s)

Added constraints

LPs

B&B Time (s) nodes

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 P14 P15

– – – – – – – – – – – – – – –

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0.0 0.0 0.0 0.0 0.1 0.1 0.1 0.3 0.3 0.3 1.0 0.5 1.0 10.7 7.3

47.9 27.5 44.9 42.8 55.8 63.4 70.5 63.5 54.0 57.1 66.6 68.6 56.6 51.4 66.4

29 3 211 17 677 4587 37105 * 24235 * * * * * *

0.6 0.1 16.4 1.0 81.5 1191.1 7947.8 * 8841.4 * * * * * *

4 5 8 5 18 58 46 89 73 86 88 186 137 292 340

3 2 2 2 4 9 4 8 3 9 5 7 8 12 5

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0.0 0.0 0.0 0.0 0.1 0.2 0.2 0.4 0.3 0.6 0.6 1.4 1.3 4.8 5.3

P16 P17 P18 P19 P20 P21 P22 P23 P24 P25

3.4 2.3 5.9 1.2 5.6 1.4 0.0 0.0 1.3 0.0

4 5 1 86 2 9 1 1 1 1

0.6 3.5 2.6 57.3 17.0 43.2 32.0 137.4 294.6 25815.9

41.2 36.8 41.2 23.5 44.4 43.4 47.5 54.9 16.7 71.4

129639 * * * * * * * * *

34712.1 * * * * * * * * *

169 450 637 1090 1008 1512 2061 3558 * *

54 128 220 830 348 506 1017 1754 * *

12 338 154 18 222 302 178 262 * *

1.4 48.4 59.5 82.2 286.0 1024.8 1848.1 5095.8 * *

B1 B2 B5 B6 B16

– – – – –

0 0 0 0 0

0.2 0.5 4.8 59.6 391.2

68.5 52.6 62.6 72.1 64.5

12344 * * * *

55 102 168 307 369

10 6 15 15 13

0 0 0 0 0

0.7 0.8 3.1 9.6 39.0

7939.36 * * * *

282

RANDAZZO AND LUNA

Benders decomposition method corresponds to the number of master problems solved. The node number is the number of nodes of the branch-and-bound tree of the branchand-bound method itself and of the branch-and-cut method. The column named Added Constraints corresponds to the number of added constraints to the model M3 before the branch-and-cut algorithm generates the branch-and-bound tree. When we compare Benders decomposition and branch-and-bound methods we should remark the initial gaps1 of the two methods. In all the test problems, the initial gap of Benders decomposition method is much smaller than that of branch-and-bound. The Lagrangian relaxation applied to the model M1 produces poor lower bounds, independently of the behavior of the linear relaxation. On the other hand, in twenty of the thirty problems, the first lower bound of the Benders decomposition was equal to the value of the optimal solution of the problem. We can conclude from table 3 that this implementation of the branch-and-bound algorithm is not competitive with the other two methods. It was able to solve only the smaller problems. The efficiency of branch-and-bound method depends on the quality of the bounds and on the development of good variable fixing strategies. The lower bounds generated by Lagrangian relaxation are not good, but this decomposition strategy can be used as a heuristic since it has found an optimal solution at the root node of the branch-and-bound tree for ten of the thirty problems. In some cases, the optimal solution is obtained with few expansions, but many expansions are necessary to confirm the optimality of the solution. Analyzing the results presented in table 3, we note that the Benders decomposition algorithm has presented the best results, since in 18 problems its execution time was smaller than those of the other two methods and in 6 problems its execution time was equal to the execution time of the branch-and-cut method. As the presented implementation of the branch-and-bound method is always worse than the other two methods, we will concentrate our attention only in the Benders decomposition and branch-and-cut methods. The Benders decomposition method was better than the branch-and-cut in 6 problems of the class 1 (the two methods have presented the same execution time for 6 problems of this class), presented the smallest times for all problems of the class 2 and for 2 of the problems of class 3. The branch-and-cut algorithm was not able to solve the problems P24 and P25, but has presented the best times for 3 problems of the class 3. As all problems of the class 3 are solved by the linear relaxation of the model M2, the branch-and-cut algorithm took advantage of this fact since the number of coupling constraints added was 11.5%, at maximum, of the total number of coupling constraints and the number of linear programs solved was small, 15, at maximum. In this way, to solve this set of linear programs with a subset of the set of constraints (13) was more efficient than to solve the complete model M3 with the entire set of coupling constraints. Comparing the solution by the Benders decomposition method with the use of CPLEX, we note that Benders decomposition algorithm was faster for 15 of the 30 problems. So, we cannot conclude which option is the best. For the largest problems of 1 GAP = (upper bound − lower bound)/upper bound.

COMPARISON OF OPTIMAL METHODS

283

class 2, we note that Benders decomposition is more efficient, but for the problems of class 3, the solution using CPLEX with the model M1 is the fastest. For the problems of class 1, the best option is to solve by Benders decomposition since it was faster for 12 of 15 problems. 7.

Conclusions

We have presented two different flow formulations for the uncapacitated local access network design problem, the first referring to a single commodity and the second being a multicommodity flow model. We have compared three exact methods to solve the problem: Benders decomposition, branch-and-cut and a branch-and-bound algorithm. We have also confirmed the possibility of exactly solving such problems with standard linear programming packages, and for this purpose the use of the weak single commodity flow formulation is a surprisingly good alternative. Yet the computational experiments have been quite limited, our experience suggests that a certain number of these modeling and solution strategies can be applied to the frequently occurring problems where the linear relaxation of the strong formulation provides automatically integral solutions. But our conclusion is that Benders decomposition emerges as the unique method that is sufficiently robust to cope with the fabricated cases where the linear programming relaxation has fractional optimal solutions. Although the branch-and-cut method could reach the best results for some instances, we note that only the Benders decomposition method was able to solve all problems within the available time, and could also solve faster 18 of the 30 tested problems. Our preliminary results indicate that a combination of these two methods could be efficient for the whole set of these problems. The best way to merge these two methods is an open problem. Another question for investigation is the generation of approximate solutions by heuristics with the objective of adding cuts to the Benders master problem in a preprocessing phase (in the current implementation our preprocessing phase only includes the solution of a shortest path problem and a minimal spanning tree problem). These new cuts might reduce the total number of Benders cycles, but the necessary time to solve each master problem might be increased since the master problem would have more constraints. The tradeoff between these two aspects should be better evaluated. The branch-and-cut algorithm may perhaps be improved by applying the same strategy of choosing the branching variable of the branch-and-bound algorithm. Experiences with the branch-and-bound algorithm have showed that this strategy contributes for a better behavior of the algorithm and it is possible that it could improve the performance of the branch-and-cut algorithm too. tested. Our branch-and-bound algorithm was not competitive with the other two methods. It needs better bounds and better variable fixing strategies. Perhaps we might improve the subproblem RP2 using the ideas of facets, valid inequalities [8,9,49] and cut inequalities [3]. The exploration of algorithms developed for the Steiner problem can also lead to better bounds for the local access network design problem. An example is the development of additional variable fixing strategies that eliminate arcs and/or nodes from the original problem in a preprocessing

284

RANDAZZO AND LUNA

stage, similar to those tests presented in [14,41]. Yet our implementation has not been competitive, we remember that the combined use of a Lagrangian heuristic and branchand-bound cannot be ruled out for this class of problems, as it has been shown by the successful implementation of Holmberg and Hellstrand [33]. Lagrangian relaxation has reached good results when applied to multicommodity flow formulations of the Steiner tree problem in graphs [39], mainly for the instances in which the linear relaxation of the proposed model finds the optimal integer solution of the problem. In summary, again, apart from such practical instances, the Benders method remains as the most robust to cope with gap situations.

References [1] Y.P. Aneja, An integer linear programming approach to Steiner problem in graphs, Networks 10 (1980) 167–178. [2] A. Balakrishnan and K. Altinkemer, Using a hop-constrained model to generate alternative communication network design, ORSA Journal on Computing 4 (1992) 192–205. [3] F. Barahona, Network design using cut inequalities, Technical Report P.O. 218, IBM T.J. Watson Research Center, New York (1995). [4] J.E. Beasley, An sst-based algorithm for the Steiner problem in graphs, Networks 19 (1989) 1–16. [5] J.F. Benders, Partitioning procedures for solving mixed integer variables programming problems, Numerische Mathematik 4 (1962) 238–252. [6] R.R. Boorstyn and H. Frank, Large-scale network topological optimization, IEEE Transactions on Communications COM-25 (1977) 29–47. [7] M. Chandy and K.M. Rusell, The design of multipoint linkages in a teleprocessing tree network, IEEE Transactions on Communications COM-21 (1972) 1062–1066. [8] D.C. Cho, E.L. Johnson, M. Padberg and M.R. Rao, On the uncapacitated plant location problem, I: Valid inequalities and facets, Mathematics of Operations Research 8 (1983) 579–589. [9] D.C. Cho, M. Padberg and M.R. Rao, On the uncapacitated plant location problem, II: Facets and lifting theorems, Mathematics of Operations Research 8 (1983) 590–612. [10] N. Christofides and J.E. Beasley, A tree search algorithm for p-median problem, European Journal of Operational Research 10 (1982) 196–204. [11] A. Claus and N. Maculan, Une nouvelle formulation du probème de Steiner sur un graphe, Technical Report 280, Centre de Recherche sur les Transports, Université de Montréal, Canada (1983). [12] F.R.B. Cruz, J. MacGregor Smith and G.R. Mateus, Solving to optimality the uncapacitated fixedcharge network flow problem, Computers Operations Research 25 (1998) 67–81. [13] G. Dantzig, Linear Programming and Extensions (Princeton University Press, 1962). [14] C.W. Duin and A. Volgenant, Reduction tests for the Steiner problem in graphs, Networks 19 (1989) 549–567. [15] M.L. Fisher, The Lagrangian relaxation method for solving integer programming problems, Management Science 27 (1981) 1–18. [16] M.L. Fisher, An application oriented guide to Lagrangian relaxation, Interfaces 15 (1985) 10–21. [17] B. Gavish, Topological design of centralized computer networks – formulations and algorithms, Networks 12 (1982) 355–377. [18] B. Gavish, Formulations and algorithms for the capacitated minimal directed tree, Journal of the ACM 30 (1983) 118–132. [19] B. Gavish, Augmented Lagrangian based algorithms for centralized network design, IEEE Transactions on Communications COM-33 (1985) 1247–1257.

COMPARISON OF OPTIMAL METHODS

285

[20] B. Gavish, Topological design of telecommunication networks – Local access design methods, Annals of Operations Research 33 (1991) 17–71. [21] A.M. Geoffrion and G.W. Graves, Multicomodity distribution system design by Benders decomposition, Management Science 20 (1974) 822–844. [22] A.M. Geoffrion and R.E. Marsten, Integer programming algorithms: A framework and state-of-the-art survey, Management Science 18(9) (1972) 465–491. [23] M.X. Goemans and Y. Myung, A catalog of Steiner tree formulations, Networks 23 (1993) 19–28. [24] M.C. Goldstein, Design of long-distance telecommunication networks – the Telepak problem, IEEE Transactions on Circuit Theory CT-20 (1973) 186–192. [25] R.E. Gomory, Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical Society 64 (1958) 275–278. [26] L. Gouveia, A comparison of directed formulations for the capacitated minimal spanning tree problem, Telecommunication Systems 1 (1993) 51–76. [27] L. Gouveia and E. Janssen, Designing reliable tree networks with two cable technologies, European Journal of Operational Research 105 (1998) 552–568. [28] M. Grötschel, M. Jünger and G. Reinelt, A cutting plane algorithm for the linear ordering problem, Operations Research 32 (1984) 1195–1220. [29] M. Held and R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138–1162. [30] M. Held and R.M. Karp, The traveling salesman problem and minimum spanning trees, Part II, Mathematical Programming 1 (1971) 6–25. [31] J. Hellstrand, T. Larsson and A. Migdalas, A characterization of the uncapacitated network design polytope, Operations Research Letters 12 (1992) 159–163. [32] D.S. Hochbaum and A. Segev, Analysis of a flow problem with fixed charges, Networks 19 (1989) 291–312. [33] K. Holmberg and J. Hellstrand, Solving the uncapacitated network design problem by a Lagrangian heuristic and branch-and-bound, Operations Research 46 (1998) 247–259. [34] F.K. Hwang and D.S. Richards, Steiner tree problems, Networks 22 (1992) 55–89. [35] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem (North-Holland, 1992). [36] T. Koch and A. Martin, Solving Steiner tree problems in graphs to optimality, Networks 32 (1998) 207–232. [37] A. Lucena and J.E. Beasley, A branch and cut algorithm for the Steiner problem in graphs, Networks 31 (1998) 39–59. [38] H.P.L. Luna, N. Ziviani and R.M.B. Cabral, The telephonic switching centre network problem: Formalization and computational experience, Discrete Applied Mathematics 18 (1987) 199–210. [39] N. Maculan, The Steiner problem in graphs, Annals of Discrete Mathematics 31 (1987) 185–212. [40] N. Maculan, D. Arpin and S. Nguyen, Le problème de Steiner sur un graphe orienté: Formulations et relaxations, Matemática Aplicada e Computacional 7 (1988) 109–118. [41] N. Maculan, P. Souza and A.C. Vejar, An approach for the Steiner problem in directed graphs, Annals of Operations Research 33 (1991) 471–480. [42] T.L. Magnanti, P. Mirchandani and R.T. Wong, Tailoring Benders decomposition for uncapacitated network design, Mathematical Programming Study 26 (1986) 112–154. [43] T.L. Magnanti and R.T. Wong, Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria, Operations Research 29(3) (1981) 464–483. [44] G.R. Mateus, Algoritmo Exato e Heurísticas para o Problema de Localização, Ph.D. thesis, COPPE/UFRJ, COPPE/UFRJ, Rio de Janeiro, RJ (1986). [45] G.R. Mateus, H.P.L. Luna and A.B. Sirihal, Heuristics for distribution network design in telecommunication, Journal of Heuristics 6 (2000) 131–148. [46] K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters 27 (1988) 125–128.

286

RANDAZZO AND LUNA

[47] M.W. Padberg and G. Rinaldi, Optimization of a 532-city symmetric travelling salesman polytope by branch and cut, Operations Research Letters 6 (1987) 1–7. [48] C.D. Randazzo, Algoritmo branch-and-bound paralelo para o problema de planejamento de redes de acesso local, Master’s thesis, Department of Computer Science, Federal University of Minas Gerais, Belo Horizonte, Brazil (1997). [49] R.L. Rardin and L.A. Wolsey, Valid inequalities and projecting the multicommodity extended formulation for uncapacitated fixed charge network flow problems, European Journal of Operational Research 71 (1993) 95–109. [50] C.R. Reeves, Modern Heuristic Techniques for Combinatorial Problems (Blackwell, Londres, UK, 1993). [51] B. Rothfarb and M.C. Goldstein, The one-terminal Telepak problem, Operations Research 19 (1971) 156–169. [52] A.G. Santos, Algoritmos baseados em planos de corte para o problema de planejamento de redes de acesso, Master’s thesis, Department of Computer Science, Federal University of Minas Gerais, Belo Horizonte, Brazil (1998). [53] P. Winter, Steiner problem in networks, Networks 17 (1987) 129–167. [54] R.T. Wong, A dual ascent algorithm for the steiner problem in directed graphs, Mathematical Programming 28 (1984) 271–287.