Benders Decomposition in Scip

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.