[SCIP] implementation of a benders decomposition

[Alexandre Dupont-Bouillard]

Hi Marc and Steve,

Thanks a lot for your answers and to the ones of Marco Lübbecke.
With your help, I found a set of valid constraints weaker in the
compact formulation than the decomposed one, explaining why the
two methods yield different optimals. With this in mind, I now have
two models that have the same optimal value.

My objective function has coefficients among {0.65,0.2,0.1,0.05},
Is it possible that the difference you notice between my Benders plugin
and the default plugin is also due to that? In general if possible
should it be preferred to have integer valuated coefficients?
The compact model is in the third Python file of the GitHub.

Thanks for sharing your experience and advices on branching in 
subproblems.
I will still try to implement an exact method based on Benders
decomposition as I find it exiting !

Thanks again,
Best regards,
Alexandre


Le 2024-10-10 06:08, Stephen J. Maher a écrit :
> 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
>  >
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip