I was thinking of how to implement Benders decomposition in AMPL in the way Paul Rubin calls “modern approach” in his great blog post, Benders Decomposition Then and Now. And experimenting with smpswriter, a program I recently wrote to convert deterministic equivalent problems written in AMPL into stochastic programming (SP) problems in SMPS, I realized that it can already be done and this is what this post is about.

As it often happens in mathematics, one thing is a special case of another or we can somehow reduce the problem to another one we know solution for. There is even a joke about it:

a mathematician and an engineer arrive in the kitchen to make tea; both fill a pot with water, put the pot on the stove and boil water – a trivial problem. The next day, they go to make tea again, but find that the pot is already full of water. The engineer will put the pot on the stove; the mathematician will throw out the water – “reducing the problem to a previously solved problem”.

With this in mind, we can think of deterministic mixed-integer programming as a special case of stochastic mixed-integer programming. Not sure if it is of much use because stochastic programming problems are generally more difficult to solve. However it allows to see that the modern Benders decomposition is in fact a variant of the integer L-shaped method.

So with the help of smpswriter, one can use any SP solver implementing the integer L-shaped method, and FortSP is one such solver, to apply modern Benders decomposition to MIP problems. Now I’ll show how it can be done using as an example a location-transportation problem for which there is an implementation of old-school Benders decomposition.

Here is the implementation of the original Benders decomposition in AMPL:

- trnloc1.mod - model
- trnloc.dat - data
- trnloc1.run - script

Let’s measure how fast it is:

To apply the integer L-shaped method I took the original location-transportation
problem (trnloc.mod) without
Benders, added a dummy scenario set `SCEN`

and marked variables
that should belong to a subproblem with `suffix stage 2`

.
I also modified the objective and constraints introducing scenario indexing where
necessary. So this has become a deterministic equivalent of an SP problem with
a single scenario:

With these changes it is possible to use smpswriter to convert the problem to SMPS and pass it to FortSP which can be done in a few lines of AMPL code:

Let’s run this script and measure time:

~~And fortunately for my case~~ as expected, the modern Benders
decomposition is much faster in this example. Of course this is a very small
problem and the overheads in the implementation of the original Benders
decomposition will be smaller relative to the solution time in large
problems. But I think it is as good illustration.

Here are the files I used to test the modern Benders decomposition:

- trnloc-scenario.mod - model
- trnloc.dat - data (the same as before)
- trnloc-modern-benders.ampl - script

Apart from performance benefits this approach requires much less modifications to the original problem compared to the implementation of Benders in AMPL itself. In fact the model trnloc-scenario.mod can be used without Benders with any solver in which case stage suffixes are simply ignored. It can be improved even more by making scenario set optional. Then the only modification to the model would be to partition your variables into master and subproblem using the stage suffix.

comments powered by Disqus