Résumés
Abstract
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 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 in [9], 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.
Keywords:
- Binary reformulation,
- Cutting planes generation,
- Lift-and-project
Veuillez télécharger l’article en PDF pour le lire.
Télécharger