Improved cut generation algorithms for the acceleration of Logic-Based Benders Decomposition

Abstract

Logic-based Benders' decomposition (LBBD) is a solution method that integrates mixed-integer programming (MIP) and constraint programming (CP). LBBD solution scheme is a finite iterative algorithm, the central element of which are Benders' cuts. It is crucial for the convergence of the algorithm to strengthen the generated Benders' cuts. This thesis aims to improve cut generation algorithms for the acceleration of LBBD.

The cut generation algorithms are the steps of the LBBD solution scheme that can include cut-strengthening techniques and subproblem separation. As the initial step, this thesis provides an extensive computational evaluation of cut-strengthening techniques in LBBD. The evaluation also includes subproblem separation and its influence on the effectiveness cut-strengthening techniques and the overall acceleration of LBBD. The computational experiments solve cumulative facility scheduling, single-facility scheduling, and vehicle routing problems, which are representative of LBBD problems and are routinely solved with benchmark datasets available. The results of this study indicate that cut-strengthening techniques can benefit from variable sorting. Another observation from this study is that cut-strengthening techniques and subproblem separation can be used interchangeably. Three heuristics based on variable sorting are proposed to improve efficiency of cut-strengthening techniques. The main features of the proposed heuristics are simplicity and no additional computational cost. The computational results show that improved cut-strengthening techniques lead to reduction in overall solution time of the LBBD solution scheme. A novel way of separating the subproblem is developed in this thesis. The subproblem separation is based on the connected components algorithm and can be applied to subproblems that do not separate naturally. The computational results solving vehicle routing problem with local congestion show that substantial acceleration is achieved by subproblem separation.

This thesis shows that improvements to cut generation algorithm can significantly accelerate LBBD. The proposed improvements can be implemented as a part of general LBBD framework.