Kernel Search

Kernel search is a purely matheuristic method, which leverages MIP solvers to obtain heuristic, or possibly optimal, solutions of instances encoded as (mixed) integer linear programming problems. It was first presented as a method to solve mixed-integer linear problems defined on binary variables modeling items selection, together with other integer or continuous variables related to the selected items, and later extended also to problems that do not involve a selection stage. The central idea of kernel search is to use some method, for example, the LP-relaxation, to identify a subset (named kernel) of promising decision variables and then to partition the remaining ones into buckets, which are concatenated one at a time to the kernel in order to check whether improving solutions can be found. An example along these lines is proposed in this chapter for the GAP.