Heuristics for 0-1 Mixed-Integer Programming

Arne Løkketangen

ABSTRACT

Most combinatorial optimization problems of general interest can be modeled as 0-1 mixed-integer programming problems, and as is shown in this handbook, there are multitudes of ways to try to solve them. This article describes ideas and solution methods, mainly based on the metaheuristics of tabu and scatter search that have been tried with good results. The notion of chunking is used as a basis for a statistically based distance measure that can be used for diversification purposes for these kinds of problems. Specialized, domain specific heuristics and general branch-and-bound techniques are not treated here, and neither are general mixed-integer programming problems.