Lagrangian Relaxation and Enumeration for Solving Constrained Shortest-Path Problems

Abstract

The constrained shortest-path problem (CSPP) generalizes the standard shortest-path problem by adding one or math path-weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian function, identifies a feasible soltuion, and then closes any optimality gap by enumerating near shortest paths, measured with respect to the Lagrangianized length. "Near-shortest" implies e-optimal, with varying e that equals the current optimality gap. The algorithm exploits a new path-enumeration method, aggregate constraints, preprocessing to eliminate eduges that cannot form part of an optimal solution, "reprocessing" that reapplies reprocessing steps as improved solutions are found and, when needed, a "phase-I procedure" to identify a feasible solution before searching for an optimal one...