Global optimality conditions for discrete and nonconvex optimization - With applications to Lagrangian heuristics and column generation
成果类型：
Article
署名作者：
Larsson, Torbjorn; Patriksson, Michael
署名单位：
Linkoping University; Chalmers University of Technology
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1060.0292
发表日期：
2006
页码：
436-453
关键词：
摘要：
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.