[SCIP] implementation of a benders decomposition

[Stephen J. Maher]

Hi Alexandre,

Marc, is correct that the same approaches should yeild the same objective value. However, with Benders' decomposition there is a tolerance used when comparing the subproblem objective value against the auxiliary variable value, which is set to 1e-04 by default. So there could be a small difference in the objective values compared to the compact formulation.

I had a look at your code and made a small change to use the default Benders plugin. This is done by calling `partialModel.initBendersDefault(<dictionary of subproblems>)`. I was able to use the subproblem creation method you have in ambulanceBenders.  What is interesting here is that there is an objective difference between using your Benders' plugin and using the default Benders' plugin. The values are -2.45534383624243 and -2.45531738121597 respectively. This could be just due to the tolerances again.

It would be good if you could share the compact formulation and the objective values. Just so we can see where the issue lies.

It looks like your master problem has integer variables, which makes it difficult to apply Benders' decomposition in this context. If your master variables were only binary, then you can just use the default cuts, since these are capable of handling MIP subproblems. If you have variables other than binary variables in the master problem, this is not handled by default.

It is possible to branch on the subproblem variables, especially since you have a custom Benders plugin. You would need to write your own branching rule that is added to the master problem. Then in this branching rule, you can select either master or subproblem variables for branching. Then you can pass the subproblem branching decisions to you Benders plugin and apply them in the solve callback. This requires some bookkeeping to ensure that you apply all ancestor branches at each node in the tree. My experience with this is that branching on the subproblem variables is not very effective. But it could be useful in your setting.

Regards,

Steve


 ---- On Thu, 10 Oct 2024 11:11:41 +0100  Marc Pfetsch  wrote --- 
 > 
 > 
 > Hi Alexandre,
 > 
 > from you description, the two approaches should yield the same answer. 
 > Unfortunately, I cannot give a good explanation of why this is not the case.
 > 
 > Can you set up an example with a single block and check whether the 
 > problem already occurs there?
 > 
 > Moreover, I noticed that you turned off presolving. Is there a deeper 
 > reason for this?
 > 
 > I don't know enough about the Benders framework to answer your question 
 > about branching.
 > 
 > Best
 > 
 > Marc
 > 
 > 
 > On 07/10/2024 05:50, Alexandre Dupont-Bouillard wrote:
 > > Dear SCIP community,
 > > 
 > > I modelized a problem as an ILP having a block diagonal structure and I 
 > > am trying to solve it
 > > using a benders decomposition. I am collaborating with someone who 
 > > implemented other algorithms in Python which makes it mandatory for me 
 > > to use Pyscipopt. I implemented the compact model using Pyscipopt.
 > > 
 > > I know that integrality constraints are mandatory inside these 
 > > subproblems but the first step would be to implement that model relaxing 
 > > the integrality constraints of the subproblems.
 > > 
 > > I tried to use the example given in bendersflp.py and adapt it to my 
 > > case. The obtained program runs until convergence but does not give the 
 > > same optimal value as the compact model with a relaxation of the 
 > > integrality constraints of the variables associated with subproblems.
 > > 
 > > For one week, I have been looking for differences in both model sets of 
 > > linear constraints and cannot find any difference. Is there any reason 
 > > for that phenomenon to appear besides a mistake in the code?
 > > 
 > > Also, I would like to know the best way to implement the full branching 
 > > process and deal with the integrality constraints of the subproblems 
 > > using SCIP. Is it necessary to implement a dedicated branching process?
 > > 
 > > 
 > > The code can be found in that repository if needed: 
 > > https://github.com/alexandredupontbouillard/ambulance
 > > 
 > > Thanks a lot for your attention
 > > Alexandre Dupont-Bouillard
 > > _______________________________________________
 > > Scip mailing list
 > > Scip at zib.de
 > > https://listserv.zib.de/mailman/listinfo/scip
 > _______________________________________________
 > Scip mailing list
 > Scip at zib.de
 > https://listserv.zib.de/mailman/listinfo/scip
 >