Lagrangian Relaxation and Enumeration for Solving Constrained Shortest-Path Problems
Loading...
Authors
Carlyle, W. Matthew
Royset, Johannes O.
Wood, R. Kevin
Subjects
Advisors
Date of Issue
2007-03-15
Date
2007-03-15
Publisher
Language
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...
Type
Paper
Description
Networks, 52, pp. 256-270.
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Carlyle, W.M., Royset, J.O. and Wood, R.K., 2008, "Lagrangian Relaxation and Enumeration for Solving Constrained Shortest-Path Problems,"Networks, 52, pp. 256-270.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.