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

Torbjörn Larsson () and Michael Patriksson ()
Additional contact information
Torbjörn Larsson: Department of Mathematics, Linköping University, SE-581 83 Linköping, Sweden
Michael Patriksson: Department of Mathematics, Chalmers University of Technology, SE-412 96 Gothenburg, Sweden

Operations Research, 2006, vol. 54, issue 3, 436-453

Abstract: 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 (epsilon)-optimality, and, in the presence of inequality constraints, a relaxed complementarity condition analogously called (delta)-complementarity. The total size (epsilon) + (delta) 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.

Keywords: programming; integer; theory; global optimality conditions; programming; integer; algorithms; Lagrangian heuristics; column generation algorithms; core problems (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1060.0292 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:54:y:2006:i:3:p:436-453

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().