.png){kind=icon}
Return
Kernel pump
.png){kind=icon}
OA
AI
DOI：10.1007/s12532-026-00333-2.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Feasibility Pump (FP) is a well-studied mixed integer linear programming primal heuristic that sequentially guides fractional solutions into integer feasibility by minimizing their distance to given target integer points, while preserving the linear constraints of the original problem. Due to its effectiveness and simplicity, FP has been embedded in most commercial solvers, and several variants of the basic method have been proposed, aiming at improving its convergence and the quality of the solutions obtained. This work introduces Kernel Pump (KP), a novel FP speed-up technique that relies on the intuition that not all binary variables are active (i.e., set to one) in a feasible solution, and can, thus, be sub-divided in a kernel search fashion. Precisely, KP identifies a subset of promising binary variables (the kernel) and distributes the rest into buckets ranked by their likelihood of composing a feasible/optimal solution. FP sub-problems are then solved iteratively, focusing on the current kernel and progressively adding variables from the buckets whenever necessary. Extensive computational experiments on benchmark instances from MIPLIB 2017, as well as two additional problems from the literature of vehicle routing and scheduling, reveal a considerable boost in success rate, also decreasing running times for the majority of instances tested. Notably, aside from outperforming FP, the new method was able to find feasible solutions in cases where CPLEX failed within an hour of search. To our knowledge, this is also the first study to introduce a decomposition approach within the FP framework.
Keywords:
Mixed integer linear programming
Primal heuristics
Feasibility pump
Kernel search
Journal
IF:
3.6
Papers:
202
Citations:
1.9K
Organization
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSaveShareSaveShareSave
View more