A Stochastic Kernel Search Algorithm for Solving Hard Integer Linear Programming Problems
Jeremy North
Murray State University
Jeremy W. North, Assistant Professor of Logistics at Murray State University, received his Ph.D. in Logistics and Supply Chain Management from the University of Missouri – St. Louis (2014). His research interests include mathematical modeling and algorithmic development for the solution of largescale integer programming problems, primarily in the field of logistics. Areas of application are in the topics of facility location and vehicle routing.
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... [ 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 subroutine 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.
Authors

Jeremy North
(Murray State University)

Robert Nauss
(University of MissouriSt. Louis)
Topic Area
Topics: Supply Chain Management, Logistics, POM, & TQM
Session
SC2 » Goal Programming/Heuristic Solution Improvement/Kernel Search Algorithm (15:00  Thursday, 23rd February, Ashley)
Paper
SEDSI_2017_Abstract.pdf
Presentation Files
The presenter has not uploaded any presentation files.