Simultaneous Solution of Lagrangean Dual Problems Interleaved with Preprocessing for the Weight Constrained Shortest Path Problem

Abstract

Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP), for example Beasley and Christofides (Beasley and Christofides, Networks 19(1989), 379-394), 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..