Files:DescriptionFile size FormatBrowse
Fulltext0.01 MBPDF (requires Acrobat Reader)Previous | Next
  
Authors:Torbjörn Larsson: Linköping University, Sweden
Michael Patriksson: Chalmers University of Technology, Sweden
Publication title:Global Optimality Conditions for Discrete and Nonconvex Optimization, With Applications to Lagrangian Heuristics and Column Generation
Conference:Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Publication type: Abstract
Issue:014
Article No.:021
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 epsilonoptimality, and, in the presence of inequality constraints, delta-complementarity, that is, a relaxed complementarity condition. The total size epsilon + delta of those two perturbations equals the size of the duality gap at an optimal solution. The characterization is further 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 Lagrangian heuristics. Finally, we outline possible uses of the optimality conditions in column generation algorithms and in the construction of core problems, and illustrate our findings on instances of the generalized assignment problem.
Language:English
Year:2004
No. of pages:1
Series:Linköping Electronic Conference Proceedings
ISSN (print):1650-3686
ISSN (online):1650-3740
File:http://www.ep.liu.se/ecp/014/021/ecp014021.pdf
Available:2004-12-28
Publisher:Linköping University Electronic Press, Linköpings universitet

REFERENCE TO THIS PAGE
Torbjörn Larsson, Michael Patriksson (2004). Global Optimality Conditions for Discrete and Nonconvex Optimization, With Applications to Lagrangian Heuristics and Column Generation, Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society http://www.ep.liu.se/ecp_article/index.en.aspx?issue=014;article=021 (accessed 8/22/2014)