A hybrid primal heuristic for finding feasible solutions to mixed integer programs

作者：Andrade Carlos E^*; Ahmed Shabbir; Nemhauser George L; Shao Yufen

来源：European Journal of Operational Research, 2017, 263(1): 62-71.

DOI：10.1016/j.ejor.2017.05.003

• Integer programming
• Primal heuristics
• Feasibility

We present a new framework for finding feasible solutions to mixed integer programs (MIP). We use the feasibility pump heuristic coupled to a biased random-key genetic algorithm (BRKGA). The feasibility pump heuristic attempts to find a feasible solution to a MIP by first rounding a solution to the linear programming (LP) relaxation to an integer (but not necessarily feasible) solution and then projecting it to a feasible solution to the LP relaxation. The BRKGA is able to build a pool of projected and rounded but not necessarily feasible solutions and to combine them using information from previous projections. This information is also used to fix variables during the process to speed up the solution of the LP relaxations, and to reduce the problem size in enumeration phases. Experimental results show that this approach is able to find feasible solutions for instances where the original feasibility pump or a commercial mixed integer programming solver often fail.

• 出版日期2017-11-16
• 单位AT&T Labs