“Binarize and Project” to generate cuts for general mixed-integer programs
Keywords:Binary reformulation, Cutting planes generation, Lift-and-project
AbstractWe consider mixed-integer linear programs with arbitrary bounded integer variables. We ﬁrst 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 efﬁcient for mixed-binary problems while keeping the problem in its non-binary form for improving the efﬁciency of the branch-and-bound procedure. We then propose a new strengthened reformulation into binary variables that answers some concerns and limitations raised in , by ensuring that only one application of the lift-and-project convexiﬁcation 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 conﬁrm 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. Key words: Binary reformulation, Cutting planes generation, Lift-and-project.
How to Cite
Roy, J.-S. (2007). “Binarize and Project” to generate cuts for general mixed-integer programs. Algorithmic Operations Research, 2(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/2733