Heuristics based on mathematical programming

This paper provides a survey of heuristics that make use of mathematical programming models and methods. The first class of methods covered break down a problem into a sequence of subproblems where each subproblem is modeled as a mathematical program and solved optimally. The second class of methods are improvement algorithms that solve a mathematical program to generate an improved solution from a known feasible solution. This class of techniques is also referred to as large-scale neighborhood search. The third class of methods considered employ a mathematical programming algorithm, most notably branch-and-bound, to generate an approximate solution to the problem of interest. Finally, we consider methods that solve a relaxation to the original problem of interest as a first step in generating a good feasible solution.