Primal Heuristics
Laurence A. Wolsey · 2020
We first present different heuristics that can be applied to a variety of combinatorial optimization problems: greedy and local search, followed by tabu search and simulated annealing that allow a solution to escape from a local optimum, as well as genetic algorithms. We then present some of the heuristics, such as feasibility pump, relaxation induced neighborhood search and local branching, that have been introduced into mixed integer programming solvers. These heuristics may require the solution of numerous linear programs or small mixed integer programs within the global branch-and-cut algorithm. Finally we suggest approaches, such as relax-and-fix or large neighborhood search, that the user can adapt to create his own specialized heuristics.