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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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
callbackfunction provided by the modern solvers to search on a single branch-and-bound tree. A blog by @prubin, and code usingcallbackfor 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.
$\begingroup$
$\endgroup$
1
Disclaimer: I've never actually done this myself. I would be tempted to list the subproblems in a circular queue. At each iteration, I would start solving subproblems with the next subproblem after the last one solved at the previous iteration, and continue solving only until a cut was generated or all subproblems had been solved. If all subproblems were solved without a new cut, I would declare victory. Otherwise, I would add the first new cut encountered, update the master solution, and repeat.
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.
The reason I would try this is that solving all subproblems at each iteration and add all cuts found might result in the addition of cuts made redundant by other cuts. The one-at-a-time approach is guaranteed to work but not guaranteed to be faster than conventional Benders. It's just a gamble.
