Global optimality conditions for discrete and nonconvex
optimization---With applications to Lagrangian heuristics and column
generation

Torbjörn Larsson
Division of Optimization
Department of Mathematics
Linköping Institute of Technology
S-581 83 Linköping
Sweden

Michael Patriksson
Department of Mathematics
Chalmers University of Technology
S-412 96 Göteborg
Sweden

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
  which are structurally similar but which 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,
  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.

KEY WORDS: 

  Global optimality conditions; nonconvex optimization; 
  integer programming; Lagrangian relaxation; Lagrangian heuristics; set
  covering problem; column generation; core problems.