I think I understand your situation very well.
e.g. Maybe you’re tackling a capacity expansion problem in power systems so the subproblems are very large-scale LPs.
This situation is not strange. If I encounter this sort of tough case, I would check the logging of this subproblem solving to ascertain whether Gurobi’s barrier algorithm is functioning properly. It happens occasionally that Gurobi hints me to tune a parameter BarHomogeneous. And since Gurobi will automatically run crossover upon Barrier finishes, you may want to ban Crossover to see if you can make the subproblem runtime shorter.
If you use Benders decomposition w.r.t multiple scenarios, the gap reduction at the global level would proceed well even if you gets stuck at one or two tough subproblems, particularly when the total number of scenarios is large (say, 1e4, 1e5 or larger).
One problem you’ll have to consider seriously is:
- Will the Benders cut I added to the master problem be valid? When will it be valid?
You are solving a 2SSP with Min sense. The 2nd stage problem is Min sense, and the 1st-stage decision occurs at the RHS of the constraints of the 2nd-stage problem. If I were you, I’ll explicitly write out the LP dual of the 2nd-stage subproblem so the dual problem is a Maximization. And I solve this dual LP with Gurobi.
Now I claim:
- If Gurobi finds a primal-feasible solution for the (Max-sense) dual LP, then the Benders cut constructed at this solution will be valid.
It’s meaningful that in this circumstance you have an opportunity to generate a valid Benders cut even if Gurobi fails to solve that (Max-sense) LP to optimality.
In general, your question here is highly related to difficulties a programmer would meet in reality. Feel free to share the context as it will help elevate our understanding of the real-world challenges.