Combinatorial Optimization Using (Integer) Linear Programming and Metaheuristics

Abstract

There are a number of different strategies available for dealing with difficult optimization problems. Two particularly successful methodologies for dealing with combinatorial challenges are mathematical programming techniques, which include (integer) linear programming-based methods and metaheuristic approaches. These two organisations were created by different communities that were more or less isolated from one another. Building hybrids of mathematical programming techniques and metaheuristics has just recently gained widespread attention from academics, who have recognised the many advantages and enormous possibilities of doing so. When it comes down to it, many issues may be dealt with significantly more successfully by using synergy between these different methodologies than by using "pure" classical algorithms. How mathematical programming methods and metaheuristics should be coupled to get these benefits is the central question. In the last several years, a slew of new procedures have been introduced. In this chapter, after providing a brief introduction to the basics of integer linear programming, we review well-known solutions for such combinations and divide them into ten different methodological groups.