# benders decomposition master problem scale large

I am dealing with a benders decomposition problem, in which there are 100 sub-problems that need to be solved. During each iteration, 100 new optimal cuts will be added to the master problem. I would like to ask, as the number of iterations increases, There are a very large number of constraints in the master problem, which increases the solution time. Is there any way to deal with such a master problem?

There are two possible directions that worth trying:

• Avoiding repetitively solving the master problem: Instead of solving the master problem from the scratch each time cuts are added, you can use the callback function provided by the modern solvers to search on a single branch-and-bound tree. A blog by @prubin, and code using callback for traveling sales man problem (TSP), can be useful.

• Reducing the number of cuts in the master problem: When each of your subproblem corresponds to a scenario in stochastic programming, the 100 cuts can be aggregated by summing up the left hand sides and right hands sides, forming a single cut. Though the number of cut in each iteration is reduced from 100 to one, the master problem become weaker (poor lower bound). A trade-off is needed between the multi-cut and the single-cut implementation.

So, for instance, if I had $$N$$ subproblems and at generation $$t$$ got a new cut from subproblem $$N-k,$$ at generation $$t+1$$ I would solve subproblems $$N-k+1, N-k+2, \dots, N, 1, 2, 3, \dots$$ until I got a new cut.