An application-oriented guide for designing Lagrangean dual ascent algorithms

Lagrangean relaxation is an effective method for providing bounds in integer programming. An efficient solution of the Lagrangean dual often requires a specialized algorithm that must be tailored for each application model. Lagrangean dual ascent is a generic name that describes a broad class of algorithms. Lagrangean dual ascent is often preferred to subgradient optimization in solving a Lagrangean dual since an ascent procedure guarantees monotonic bound improvement. Also, if embedded within a branch and bound scheme, Lagrangean dual ascent may adjust only a few multipliers at each node, thus conserving computer storage and enhancing processing efficiency. This paper describes a framework to construct a Lagrangean dual ascent procedure and adapts it for the generalized assignment problem and the constrained arborescence problem.