A parametric programming methodology to solve the Lagrangean dual for network problems with multiple side-constraints

Many practical problems can be formulated as a network problem with linear side-constraints. Problems of this class would be easy to solve if the side-constraints were not present, and so the technique of Lagrangean relaxation is often applied as part of the solution strategy. A Lagrangean relaxation of a problem provides a lower bound (for a minimization problem) on the optimal value of the objective function of the original problem. The objective of this paper is the exploration of the relationship between Lagrangean relaxation and parametric programming, and the presentation of a procedure that is based on parametric programming for solving the Lagrangean relaxation problem. This procedure may also be integrated with the popular subgradient method in order to provide an efficient and effective solution strategy for the Lagrangean relaxation problem.