Exact solution of the centralized network design problem on directed graphs. (English) Zbl 1068.90105
Summary: We present a novel exact solution method for the centralized network design problem on directed graphs. The problem is modeled as the well-known graph theoretic problem: the capacitated directed spanning tree problem. We propose a Lagrangian relaxation where the subproblem is a directed spanning tree with a degree constraint on the root. The master problem has an exponential number of constraints and variables. To solve it, we present a cut-and-column generation algorithm based on analytic centers. The latter solves a restricted master problem using a primal analytic center cutting plane method and strengthens the bound by generating columns that correspond to violated primal constraints. The Lagrangian bound is embedded within branch-and-bound leading to an interior point branch-and-price algorithm with cut generation. We use a dual interior point method to warm start the solution of the restricted master problem both after adding columns and after branching. We present numerical results indicating that the proposed approach outperforms the literature on the directed case.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90B10 | Deterministic network models in operations research |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
Keywords:
capacitated spanning trees; branch-and-price; cut and column generation; analytic center cutting plane method; Lagrangian relaxationReferences:
| [1] | New neighborhood search structures for the capacitated minimum spanning tree problem, Research Report 99-2 ( 1999), University of Florida, Department of Industrial and Systems Engineering. |
| [2] | Amberg, Combinator Optimizat. Theory Prac 1 pp 9– (1996) |
| [3] | Bellmore, Operat Res 19 pp 278– (1971) |
| [4] | Chandy, Networks 3 pp 173– (1973) |
| [5] | Elhedhli, Math Program 100 pp 267– (2004) |
| [6] | Fischetti, Operat Res 37 pp 319– (1989) |
| [7] | Fischetti, Operat Res 42 pp 846– (1994) |
| [8] | Fast lower bounds for the capacitated minimum spanning tree problem, Technical Report TR-99-05 ( 1999), Dipartimento di Informatica, University of Pisa, Pisa, Italy. |
| [9] | Gavish, Networks 12 pp 355– (1982) |
| [10] | Gavish, Assoc Comput Machinery 30 pp 118– (1983) · Zbl 0504.90052 · doi:10.1145/322358.322367 |
| [11] | Gavish, IEEE Trans Commun 33 pp 1247– (1985) |
| [12] | Gouveia, Operat Res 43 pp 130– (1995) |
| [13] | Gouveia, Ann Operat Res 86 pp 271– (1999) |
| [14] | Gouveia, Networks 35 pp 1– (2000) |
| [15] | Goffin, Manage Sci 38 pp 284– (1992) |
| [16] | Convex nondifferentiable optimization: A survey focussed on the analytic center cutting plane method, Technical Report 99.02 ( 1999), HEC/Logilab, Geneva, Switzerland. |
| [17] | Hall, INFORMS J Comput 8 pp 219– (1996) |
| [18] | Laporte, Networks 16 pp 33– (1986) |
| [19] | Malik, Networks 23 pp 525– (1993) |
| [20] | Papadimitriou, Networks 8 pp 217– (1978) |
| [21] | Tarjan, Networks 7 pp 25– (1977) |
| [22] | Toth, Ann Operat Res 61 pp 121– (1995) |
| [23] | Interior point algorithms: Theory and analysis, John Wiley, New York, 1997. · doi:10.1002/9781118032701 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
