2
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for your comment. $\endgroup$
    – XXia
    Jan 31 at 6:26
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for your comment. $\endgroup$
    – XXia
    Jan 31 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.