Article | Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society | Global Optimality Conditions for Discrete and Nonconvex Optimization; With Applications to Lagrangian Heuristics and Column Generation

Title:
Global Optimality Conditions for Discrete and Nonconvex Optimization; With Applications to Lagrangian Heuristics and Column Generation
Author:
Torbjörn Larsson: Link√∂ping University, Sweden Michael Patriksson: Chalmers University of Technology, Sweden
Download:
Full text (pdf)
Year:
2004
Conference:
Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society
Issue:
014
Article no.:
021
No. of pages:
1
Publication type:
Abstract
Published:
2004-12-28
Series:
Linköping Electronic Conference Proceedings
ISSN (print):
1650-3686
ISSN (online):
1650-3740
Publisher:
Linköping University Electronic Press; Linköpings universitet


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.

Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Author:
Torbjörn Larsson, Michael Patriksson
Title:
Global Optimality Conditions for Discrete and Nonconvex Optimization; With Applications to Lagrangian Heuristics and Column Generation
References:
No references available

Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Author:
Torbjörn Larsson, Michael Patriksson
Title:
Global Optimality Conditions for Discrete and Nonconvex Optimization; With Applications to Lagrangian Heuristics and Column Generation
Note: the following are taken directly from CrossRef
Citations:
No citations available at the moment