An improved lagrangian relaxation method for discrete optimization applications

Lagrangian relaxation has been a powerful methodology to solve discrete and mixed integer optimization problems such as planning, scheduling, coordination, and unit commitment. The subgradient method is frequently used within Lagrangian relaxation to update multipliers, where a subgradient direction is obtained by fully minimizing the relaxed problem. A dual value is a lower bound to the optimal feasible cost, and can be used to evaluate solution quality. Because full minimization of the relaxed problem is time-consuming and even impossible when the problem is complex, surrogate optimization has been developed where a proper direction can be obtained by only approximate optimization of the relaxed problem. However, the lower bound property of the ldquosurrogate dualrdquo is lost and the convergence of the algorithm cannot be guaranteed. This paper presents a new algorithm based on the surrogate Lagrangian relaxation method to resolve the lower bound issue with convergence guaranteed. The key idea is to examine the different behaviors of the algorithm when the optimal dual value is overestimated or underestimated, and to adjust the estimate accordingly. Theoretical proof on the different behaviors and the convergence of the algorithm are provided. Testing results on manufacturing scheduling problems show the effectiveness of the algorithm.