[Scip] Using Benders Decomposition

[Stefan Heinz]

Hi Steve,

If you want to implement a classical bender decomposition, that means, solve 
the master to optimality, check the slaves, and create a cut if necessary, 
then none of the classical plugins are suitable for that. The reason is, that 
if SCIP reaches the state of optimal solution found, it is not possible to 
create a cut/constraint and restart SCIP out of a classical plugin.

To realize a classical bender decomposition with SCIP you have to play around 
with the SCIP concept of original and transformed problem. SCIP always copies 
the original problem in the beginning into so called transformed problem. 
During the solving process only the transformed problem is changed. That 
means, the original problem stays the same. If the problem is solved to 
optimality you can grep the solution check the solution and if a subproblem is 
violated you generate a constraint which you add to the original problem. 
Therefore, you have the free the transformed problem first before you can add 
the constraint to the original problem. After adding the constraint you repeat 
to solving process.

There are two ways you can realize it with SCIP. You can use SCIP as callable 
library or you implement a (none classical) plugin a SCIP dialog. 

http://scip.zib.de/doc/html/DIALOG.html

The advantage of SCIP dialog is that you can use the interactive Shell of 
SCIP. This gives you the possibilities to easily play around with your 
instances. That means, changing parameters, setting limits, and so on.

Currently, we have no example included in the SCIP release which features 
bender decomposition. Sorry for that. We are planning to change that with the 
next release.

If you are more interested in so-called branch-and-check approach, then things 
change a lot. For such an approach you should implement a constraint handler. 
If you need more information for that, just let us know.

Best Stefan

> Hello everyone,
> 
> I would like to use Benders decomposition for my problem to implement
> delayed constraint generation. I was wondering what would be the best
> type of plugin to use for the benders subproblem. Would it operate best
> as a separator plugin or should I implement the subproblem in a
> constraint handler?
> 
> Thanks for your help,
> 
> Steve