The search for optimal Lagrange multipliers

Abstract

Lagrangean constramt relaxation methods are a widely used approximation technique for NP-hard discrete optimization problems. The computational complexity of the Lagrangean relaxation technique is examined in this paper. It is shown that the optimization of Langrangean multipliers is polynomial-time equivalent to optimization of the Lagrangean subproblems. The main technique used to derive this result is the ellipsoid method for optimizing linear functlons over convex bodies.

Consequences, both theoretical and computational, of this result are developed. A direct polynomial-time reduction of integer knapsack to integer group knapsack is shown to follow via an elementary treatment of (a Lagrangean dual-based) super group embeddmg of the knapsack problem. The computational message of the paper is that multiplier search using the ellipsoid method is an attractive alternative to first-order subgradient methods. With this perspective, some preliminary computational experiments on Lagrangean relaxation of the travelling salesman problem were conducted and the results are reported.