A Stochastic Kernel Search Algorithm for Solving Hard Integer Linear Programming Problems

Kernel search is a heuristic framework for solving integer linear programming problems. The procedure involves fixing a subset of binary variables to be either 0 or 1 and solving the resulting reduced problem using... [ view full abstract ]

Kernel search is a heuristic framework for solving integer linear programming problems. The procedure involves fixing a subset of binary variables to be either 0 or 1 and solving the resulting reduced problem using optimization. This process is repeated until a specified stopping criterion is met or (under the control of a branch and bound algorithm) optimality conditions are met. We consider hard integer linear programming problems in this work exclusively, with “hard” being defined as a problem that cannot be solved to optimality with proprietary optimal search codes like CPLEX or GUROBI within one hour of search time.

Historically, there have been two approaches to the Kernel search procedure. The first, referred to as “general kernel search”, works by identifying sets of binary variables to fix at 1 in the initialization phase and then proceeding to solve each resulting optimization problem. The amount of variable sets to fix and subsequent optimization problems to solve is controlled by a parameter set at runtime. “Iterative kernel search” is the second approach, which involves repeatedly updating the set of variables to fix and then solving the resulting reduced problem optimally in an iterative manner. The procedure ends when no new variables are identified to be fixed.

In this work, we operate within the iterative kernel search framework by implementing a stochastic search procedure to identify the set of binary variables to fix. This stochastic sub-routine is guided by a parameter establishing the cardinality of the set of variables to fix, and a probability of inclusion parameter for each variable. If the set of binary variables are given by (N), and the size of the set of variables to set is |K|, the resulting reduced problem will involve |N| - |K| otherwise unrestricted binary variables. These stochastic search parameters are updated at each iteration of the algorithm based upon objective performance, the optimality gap of the reduced problem after a parameter set limit of search time, and the reduced cost values (or pseudo costs) of each variable from the LP relaxation of the original problem. Computational results are given on benchmark data sets of the capacitated facility location problem and the generalized assignment problem.