The Lshaped method is a decomposition
method that is useful for solving problems that have the form
of a master problem and several subproblems represented by
the side model. The complete problem with both the master and
subproblems
may be very large and beyond the capabilities of the available
Excel solver. The Lshaped method is a process that solves
a sequence of much smaller problems.
The
combined
solution
converges in a finite number of iterations to the optimum.
Because the number of required iterations may be large, we
can terminate the process when the lower and upper bound values
differ by a specified minimum tolerance. We have implemented
the Lshaped method in the Jensen LP/IP Solver. This page describes
the application of the method while the next
page discusses
the theory.
We illustrate the method with the small problem used to introduce
the side model for stochastic programming.
The Master problem is below. The Jensen LP/IP addin is identified
as the solver. A larger illustration is the Capacity problem
in the stochastic programming section.
There are 16 scenarios for the stochastic programming
model represented on the side model. An important restriction
to this method is that all subproblems be linear programs.
This
makes
nonlinear
or
integer
forms inapplicable. Also the subproblems must have feasible
solutions for every feasible solution for the linking variables.
It is always possible to create models for which this is true,
but the method will terminate if a subproblem happens
not to have a feasible solution for some solution for the linking
variables encountered during the solution process.
Clicking the Solve button at the top
of the page (not the one in the side model form) presents
the LShaped algorithm dialog.
The fields at the top of the form are parameters
for the method that will become meaningful as the example
progresses. The buttons at the bottom indicate how much of
the solution process is displayed. The Solution Only button
solves the problem and then eliminates all intermediate information
from the worksheet except a Lower Bound (or Upper
Bound) cell just below the objective value. The LConstraints button
shows the extra constraints added to the
master problem by the method. The Algorithm Steps button
stops the algorithm at each step of the process so the student
can review
the current
status and perhaps terminate the algorithm.
The Subproblem Hot Start checkbox solves
the series of subproblems more rapidly by solving each subproblem
(after the first) starting with the optimum basis
for the previous subproblem. Except for very small problems,
this
results
in
faster computation
times. We allow the option to be unchecked in case the hotstart
is not effective. Solving the problem with the options above
results in the solution
below.
