[SCIP] implementation of a benders decomposition

[Marc Pfetsch]

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