Is the any package or for solving a MIP with branch and bound that gives the user the developed constraints during the solution procedure?

I have a two-stage stochastic optimization model with binary and continuous variables in the first and the second stages.

To solve this I employ a benders decomposition technique. In this technique I need to get the dual of the second stage to generate cutting planes.

To get the dual of the second stage problem I want to relax the original MIP problem, solve the relaxed problem and obtain the solution. If the obtained solution is fractional I need to generate constraints such as x =>1 or x<=0. This is very similar to the classic branch and bound method. Since the second stage model is LP I can get the dual which is what I need.

Is there a package or whatever somewhere that performs the branch and bound algorithm with continuous relaxation of MIP and provide the user with the generated cuts so I can use them to drive the problem dual?

Thanks!

1 Like

Maybe Bonobo.jl can do that?

1 Like

You’ll likely have to code this manually.

See here for a tutorial on Benders: Benders decomposition · JuMP

It’d be a little over-kill, but you could also try GitHub - odow/SDDP.jl: Stochastic Dual Dynamic Programming in Julia, which can solve two-stage problems with mixed binary and continuous variables.

2 Likes