×

Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem. (English) Zbl 1207.05201

Summary: Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP), for example Beasley and Christofides [J. E. Beasley and N. Christofides, Networks 19, No. 4, 379 – 394 (1989; Zbl 0673.90085)], calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and edges. However, for each node and edge, a Lagrangean dual problem exists whose solution may differ from the relaxation of the full problem. Thus, using one Lagrange multiplier does not offer the best possible network reduction. Furthermore, eliminating nodes and edges from the network may change the Lagrangean dual solutions in the remaining reduced network, warranting an iterative solution and reduction procedure. We develop a method for solving the related Lagrangean dual problems for each edge simultaneously which is iterated with eliminating nodes and edges. We demonstrate the effectiveness of our method computationally: we test it against several others and show that it both reduces solve time and the number of intractable problems encountered. We use a modified version of W. M. Carlyle and R. K. Wood’s [38th Annual ORSNZ Conference, Hamilton, New Zealand, November (2003)] enumeration algorithm in the gap closing stage. We also make improvements to this algorithm and test them computationally.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
90B10 Deterministic network models in operations research

Citations:

Zbl 0673.90085

Software:

CNOP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aneja, Shortest chain subject to side constraints, Networks 13 pp 295– (1983) · Zbl 0516.90028
[2] Barnhart, Flight string models for aircraft fleeting and routing, Transport Sci 32 pp 208– (1998) · Zbl 0987.90504
[3] Beasley, An algorithm for the resource constrained shortest path problem, Networks 19 pp 379– (1989) · Zbl 0673.90085
[4] Bellman, On a routing problem, Q Appl Math 16 pp 87– (1958) · Zbl 0081.14403
[5] D. Blokh and G. Gutin, An approximation algorithm for combinatorial optimization problems with two parameters, University of Southern Denmark (January 1995). · Zbl 0863.90118
[6] W.M. Carlyle and R.K. Wood, Lagrangian relaxation and enumeration for solving constrained shortest-path problems, 38th Ann ORSNZ Conf, Hamilton, New Zealand, University of Waikato, November 2003. · Zbl 1180.90346
[7] Desrochers, A generalized permanent labelling algorithm for the shortest path problem with time windows, INFOR 26 pp 191– (1988) · Zbl 0652.90097
[8] Dijkstra, A note on two problems in connexion with graphs, Numer Math 1 pp 269– (1959) · Zbl 0092.16002
[9] Dumitrescu, Improved preprocessing, labelling and scaling algorithms for the weight-constrained shortest path problem, Networks 43 pp 135– (2003) · Zbl 1031.68144
[10] A. Fahlen, Missile routing for a stand-off missile, Master’s thesis, Linköping University, Linköping, Sweden, November, 2000.
[11] Ford, Flows in networks (1962)
[12] Garey, Computers and intractability; a guide to the theory of NP-completeness (1990)
[13] Guo, Search space reduction in QoS routing, Comput Networks 41 pp 73– (2003) · Zbl 1056.68029
[14] Handler, A dual algorithm for the constrained shortest path problem, Networks 10 pp 293– (1980)
[15] Hart, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans Syst Sci Cybernetics SSC4 (2) pp 100– (1968)
[16] Jüttner, On resource constrained optimization problems, 4th Japanese-Hungarian Symp Discrete Math Applications (2005)
[17] Jüittner 2 (2001)
[18] Kelley, The cutting-plane method for solving convex programs, J-SIAM 8 pp 703– (1960) · Zbl 0098.12104
[19] Kuipers, Performance evaluation of constraint-based path selection algorithms, IEEE Network 18 pp 16– (2004)
[20] K. Mehlhorn and M. Ziegelmann, CNOP: a package for constrained network optimization. In Proceedings 3rd International Workshop on Algorithm Engineering and Experiments (ALENEX 01) (2001), 17-30. · Zbl 1010.68718
[21] R. Murphey, S. Uryasev, and M. Zabarankin, Trajectory optimization in a threat environment, Research report, University of Florida, July 2003.
[22] Nemhauser, Integer and combinatorial optimization (1988) · doi:10.1002/9781118627372
[23] Salama, A distributed algorithm for delay-constrained unicast routing, INFOCOM 1 pp 84– (1997) · doi:10.1109/INFCOM.1997.635117
[24] R. Widyono, The design and evaluation of routing algorithms for real-time channels, Technical report, University of California at Berkeley, June 1994.
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.