A Trust Region Target Value Method for Optimizing Nondifferentiable Lagrangian Duals of Linear Programs

In this paper, we design a new variable target value procedure, the trust region target value (TRTV) method, for optimizing nondifferentiable Lagrangian dual formulations of large-scale, ill-conditioned linear programming problems. Such problems typically arise in the context of Lagrangian relaxation approaches and branch-and-bound/cut algorithms for solving linear mixed-integer programs. Subgradient optimization strategies are well-suited for this purpose and are popularly used, particularly in Lagrangian relaxation contexts, because of their simplicity in computation and mild memory requirements. However, they lack robustness and can often stall while yet remote from optimality. With this motivation, we design our proposed TRTV method to retain simplicity in computations, be theoretically convergent, as well as yield an effective and robust performance in practice. Furthermore, we augment this approach with dual refinement and primal recovery procedures based on outer-linearization and trust region strategies to further improve the accuracy of the resulting solutions and to derive primal solutions as well. Our computational study reveals a highly competitive performance of the proposed TRTV algorithm among several implemented nondifferentiable optimization procedures. Moreover, the dual refinement and primal recovery procedures help further reduce the optimality gap and promote attaining a relatively greater degree of primal feasibility as compared with several alternative ergodic primal recovery schemes. Also, the proposed method displays significantly lesser computational requirement than that of a commercial linear programming solver CPLEX. Copyright Springer-Verlag 2006