‘Binarize and Project’ to generate cuts for general mixed-integer programs

We consider mixed-integer linear programs with arbitrary bounded integer variables. We first describe a cutting plane approach based on the reformulation of integer variables into binary variables and describe a practical algorithm to compute these cuts for the original problem. We use the term ‘Binarize and Project’ to highlight the similarity to the lift-and-project idea of lifting the problem to a higher dimensional space to generate cutting planes which are then projected back onto the original space. Indeed, the interest of this approach lies in taking advantage of cutting plane approaches efficient for mixed-binary problems while keeping the problem in its non-binary form for improving the efficiency of the branch-and-bound procedure. We then propose a new strengthened reformulation into binary variables that answers some concerns and limitations raised earlier, by ensuring that only one application of the lift-and-project convexification procedure to the binary reformulation of the problem is required to obtain a strengthening of the original problem. Finally, the method is implemented inside the COIN optimization library and a preliminary experimentation is performed on problems from the MIPLIB library. The computational results confirm that the use of the proposed binary reformulation and cutting plane generation procedure leads to an improved integrality gap reduction albeit with an increased computing time.