A meta-heuristic extension of the Lagrangian heuristic framework

Lagrangian heuristics for discrete optimization work by modifying Lagrangian relaxed solutions into feasible solutions to an original problem. They are designed to identify feasible, and hopefully also near-optimal, solutions and have proven to be highly successful in many applications. Based on a primal-dual global optimality condition for non-convex optimization problems, we develop a meta-heuristic extension of the Lagrangian heuristic framework. The optimality condition characterizes (near-)optimal solutions in terms of near-optimality and near-complementarity measures for Lagrangian relaxed solutions. The meta-heuristic extension amounts to constructing a weighted combination of these measures, thus creating a parametric auxiliary objective function, which is a close relative to a Lagrangian function, and embedding a Lagrangian heuristic in a search procedure in the space of the weight parameters. We illustrate and make a first assessment of this meta-heuristic extension by applying it to the generalized assignment and set covering problems. Our computational experience show that the meta-heuristic extension of a standard Lagrangian heuristic can significantly improve upon solution quality.