Supervised learning in Branch-and-cut strategies
Abdellatif El Afia, Mohamed Mustapha Kabbaj · 2017
Branch-and-Cut is a powerful algorithm used for solving MILP problems. It involves two main sub-algorithms: branch-and-bound and cutting plane. On the one hand, the branch-and-bound algorithm comprises two strategies that are node selection strategy and branching strategy. These two strategies in literature don't exploit information of each other, and variable branching strategy try to find compromise between minimizing the number of processed nodes and minimizing solving time. On the other hand, cutting plane algorithm allow tightening bounds and reducing the number of processing nodes. Whereas the learning literature has been focused in dealing with just one strategy on the same time, we design a two-in-one strategy of branch-and-bound algorithm regarding the fact that are intuitively dependent. In this perspective, we apply the well-known Support Vector Machine (SVM) algorithm to the well-known set of problems MIPLIB to learn the mentioned strategy that can be used to speed up the basic branch-and-bound algorithm. We use also cutting plane to speed up the algorithm.