Kernel Search: A Heuristic Framework for MILP Problems with Binary Variables Enrico Angelelli 1, Renata Mansini 2, and M. Grazia Speranza 1 1 Department of Quantitative Methods, University of Brescia, Italy 2 Department of Electronics for Automation, University of Brescia, Italy Abstract. We propose a heuristic framework, called Kernel Search, to solve mixed integer linear programming (MILP) formulations of combinatorial problems. The method is based on the identification of a restricted set of promising items (kernel) and on the exact solution of the MILP problem on this set. The continuous relaxation of the problem solved on the complete set of available items is used to identify the initial kernel and a sequence of integer problems are then solved to identify further items to insert into the kernel. We analyze the behavior of several heuristic algorithms as implementations of the Kernel Search framework for the solution of two combinatorial problems, a portfolio optimization problem and the multi-dimensional knapsack problem. The proposed heuristics are very effective and quite efficient. The Kernel Search has the advantage of being general and thus easily applicable to a variety of combinatorial problems.