liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Global optimality conditions for discrete and nonconvex optimization-with applications to Lagrangian heuristics and column generation
Linköping University, The Institute of Technology. Linköping University, Department of Mathematics, Optimization .ORCID iD: 0000-0003-2094-7376
Matematiska vetenskaper Chalmers tekniska högskola.
2006 (English)In: Operations Research, ISSN 0030-364X, Vol. 54, no 3, 436-453 p.Article in journal (Refereed) Published
Abstract [en]

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. © 2006 INFORMS.

Place, publisher, year, edition, pages
2006. Vol. 54, no 3, 436-453 p.
National Category
URN: urn:nbn:se:liu:diva-36281DOI: 10.1287/opre.1060.0292Local ID: 30845OAI: diva2:257129
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2013-08-30

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Larsson, Torbjörn
By organisation
The Institute of TechnologyOptimization
In the same journal
Operations Research

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 321 hits
ReferencesLink to record
Permanent link

Direct link