Model selection for learning Branch-and-cut strategies
Mohamed Mustapha Kabbaj, Abdellatif El Afia · 2018
Branch-and-Cut algorithm is an omnipresent algorithm used for solving mixed integer linear problems (MILP). It is proving its efficiency in different fields such as multi commodity location routing [18] and vehicle routing problem [17]. As a matter of fact, it is a result of combining two algorithms that are branch-and-bound with cutting plane. The former creates little by little a tree of nodes by adopting two strategies. These strategies are variable selection strategy and node selection strategy. The latter is cutting plane that tightens bounds and reduces the number of processed nodes. In our previous work, we experienced a methodology of learning branch-and-cut strategies [1] using regression-based support vector machine. That methodology allowed firstly to exploit information from previous executions of Branch-and-Cut algorithm on other instances. Secondly, it used node selection strategy decision information in variable branching choice. And thirdly, it gave good results in term of solving time comparing to standard Branch-and-Cut algorithm. In this work, we will focus on increasing SVM performance by using cross validation coupled with model selection [11].