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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, E-ISSN 1526-5463, 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
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-36281DOI: 10.1287/opre.1060.0292Local ID: 30845OAI: oai:DiVA.org:liu-36281DiVA: diva2:257129
Available from: 2009-10-10 Created: 2009-10-10 Last updated: 2017-12-13

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Larsson, Torbjörn

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 337 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf