Introducing Automatically Derived Subproblem Relaxations in a Logic-Based Benders Decomposition Solver
摘要
Logic-based Benders decomposition (LBBD) effectively combines mixed integer programming and constraint programming to solve difficult optimisation problems. While the decomposition exploits different solution and modelling paradigms, the separation destroys problem information connecting master and subproblem decisions. Alongside cut generation, a standard way of re-introducing this connection is through the addition of valid inequalities in the master problem. These inequalities typically constitute subproblem relaxations and they are usually problem specific and derived by hand. This paper proposes a general approach for deriving valid inequalities and demonstrates how they can be applied to cumulative and disjunctive constraints. In an effort to develop a general purpose LBBD solver, the general derivation of valid inequalities have been implemented as part of a new cumulative constraint handler for SCIP and the effectiveness is evaluated on two variants of scheduling problems. The computational experiments show the potential of applying these general valid inequalities to the master problem.