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

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.

About the subject

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.