COMBINING (INTEGER) LINEAR PROGRAMMING TECHNIQUES AND METAHEURISTICS FOR COMBINATORIAL OPTIMIZATION

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.