Reinforcement Learning for (Mixed) Integer Programming: Smart Feasibility Pump

Mixed integer programming (MIP) is a general optimization technique with various real-world applications. Finding feasible solutions for MIP problems is critical because many successful heuristics rely on a known initial feasible solution. However, it is in general NP-hard. In this work, we propose a deep reinforcement learning (DRL) model that efficiently finds a feasible solution for a general type of MIPs. In particular, we develop a smart feasibility pump (SFP) method empowered by DRL, inspired by Feasibility Pump (FP), a popular heuristic for searching feasible MIP solutions. Numerical experiments on various problem instances show that SFP significantly outperforms the classic FP in terms of the number of steps required to reach the first feasible solution. We consider two different structures for the policy network. The classic perception (MLP) and a novel convolution neural network (CNN) structure. The CNN captures the hidden information of the constraint matrix of the MIP problem and relieves the burden of calculating the projection of the current solution as the input at each time step. This highlights the representational power of the CNN structure.