This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Larsson, T. Articles by Patriksson, M. Search for Related Content

Global Optimality Conditions for Discrete and Nonconvex Optimization—With Applications to Lagrangian Heuristics and Column Generation

Department of Mathematics, Linköping University, SE-581 83 Linköping, Sweden
Department of Mathematics, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden
tolar{at}mai.liu.se
mipat{at}math.chalmers.se

The well-known and established global optimality conditions based on the Lagrangian formulation of an optimization problem are consistent if and only if the duality gap is zero. We develop a set of global optimality conditions that are structurally similar but are consistent for any size of the duality gap. This system characterizes a primal–dual optimal solution by means of primal and dual feasibility, primal Lagrangian -optimality, and, in the presence of inequality constraints, a relaxed complementarity condition analogously called -complementarity. The total size + of those two perturbations equals the size of the duality gap at an optimal solution. Further, the characterization is equivalent to a near-saddle point condition which generalizes the classic saddle point characterization of a primal–dual optimal solution in convex programming. The system developed can be used to explain, to a large degree, when and why Lagrangian heuristics for discrete optimization are successful in reaching near-optimal solutions. Further, experiments on a set-covering problem illustrate how the new optimality conditions can be utilized as a foundation for the construction of new Lagrangian heuristics. Finally, we outline possible uses of the optimality conditions in column generation algorithms and in the construction of core problems.

Subject classifications: programming; integer; theory; global optimality conditions; programming; integer; algorithms; Lagrangian heuristics; column generation algorithms; core problems.
History: Received April 2003; revision received April 2004; accepted February 2005.