Search: id:"swepub:oai:DiVA.org:liu-36281" >
Global optimality c...
Global optimality conditions for discrete and nonconvex optimization-with applications to Lagrangian heuristics and column generation
-
- Larsson, Torbjörn, 1957- (author)
- Linköpings universitet,Tekniska högskolan,Optimeringslära
-
- Patriksson, Michael (author)
- Matematiska vetenskaper Chalmers tekniska högskola
-
(creator_code:org_t)
- Institute for Operations Research and the Management Sciences (INFORMS), 2006
- 2006
- English.
-
In: Operations Research. - : Institute for Operations Research and the Management Sciences (INFORMS). - 0030-364X .- 1526-5463. ; 54:3, s. 436-453
- Related links:
-
https://urn.kb.se/re...
-
show more...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Keyword
- MATHEMATICS
- MATEMATIK
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database