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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Introducing Automatically Derived Subproblem Relaxations in a Logic-Based Benders Decomposition Solver

  • Sachin Rajendran,
  • Stephen Maher,
  • Elina Rönnberg

摘要

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.