View the model
Download the model

Benders decomposition applied to (BendersX.lng) multi-product\location inventory stocking.
The problem:
Stage 0: Decide how much to buy\make\stock, Y(i), at\of various origins or stock points, i.
Stage 1: a)Random demands, DEM(s,j), occurs under scenario s, at various demand points\products,j.
b)We then choose most profitable amount to ship, X(s,i,j) under scenario s from supply point i to demand point j. Any unsatisfied demand is lost, i.e., no sale;
! Benders decomposition is a solution method that may work well when the problem has the following 2 level structure:
Master level consists of "complicating\linking" variables.
Some of these variables may be integer variables.
Subproblem level has the features:
a)if the master variables are fixed, the subproblem(s) are very easy to solve, e.g. separate into independent problems.
b) subproblem is a continuous convex problem, e.g., an LP, so that dual prices are available for giving optimistic linear bounds on how the subproblem objective value will change as master variables are changed.
The general iteration is:
While( solution is not good enough:
1) Solve master alone except for cuts from bounding subproblem.
2) Fix master variables and solve subproblem, given the values of master variables,
3) Based on dual prices from subproblem, add cut(s) to master to better describe how subproblem objective is affected by master level decisions. )
! The essential, oversimplified, nature of each cut, based on the point YF is: SubproblemProfit <= SubproblemProfitAt(YF) + (Y-YF)*RateOfChangeOfProfitAt(YF), or BNDSUB <+ SubproblemProfitAt(YF) + (Y-YF)*DualPriceAt(YF), i.e., we create a linear tangent at point YF of the subproblem profit function;