Return to Index
Operations Research Models and Methods
Computation Section
Subunit Mathematical Programming
 L-Shaped Method

The L-shaped 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 L-shaped 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 L-shaped 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 add-in 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 L-Shaped 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 L-Constraints 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 hot-start is not effective. Solving the problem with the options above results in the solution below.

  The master problem solution variables are in row 8 and the subproblem solution variables are in columns N and O. The L-shaped method does not guarantee an optimum solution. In the original dialog there is a tolerance percentage (in this case (0.001%). The program computes lower and upper bounds to the optimum solution and stops when difference between these bounds is less than this tolerance (relative to the largest absolute value of the lower or upper bounds). The solution presented is the best solution obtained during the process and its objective value is a lower bound to the optimum. The upper bound provides a measure of quality for the solution presented. In this case the upper bound and lower bounds are equal, so the solution is optimum. For a minimization problem the lower and upper bounds have reversed purposes.


Optimality Cuts


By selecting the L-Constraints option on the dialog, we see the additions to the master model during the performance of the L-shaped method.

The method consists of several iterations. Except for the last, each iteration adds a new constraint to the master problem that restricts the set of feasible values for the linking variables, in this case z1 and z2. They are called Optimality Cuts because they cut-off solutions that cannot be optimal. As the iterations progress the upper and lower bounds grow together. When their difference is smaller than the specified tolerance, the process stops and presents the best feasible solution found. For the present example the best is also the optimum.

The constraints are added from the bottom up. Thus the constraint labeled Opt1 was the first, and the constraint labeled Opt5 was the last.

As new optimality cuts are added, old cuts may become loose. Although there is no guarantee that cuts that become loose at one iteration will not be binding for a later iteration, it is common practice to limit the total number of cuts included in the model simultaneously. The dialog allows a separate input for this purpose. When the number of simultaneous cuts is fewer than the total number of cuts, it is possible that the method will take more iterations or even fail to converge. On the other hand, with fewer simultaneous cuts the LP model for the master problem will have fewer constraints and be easier to solve.

The method may be restarted with new parameters by clicking the Restart Algorithm checkbox.


Algorithm Steps


For the student or teacher interested in the steps of the algorithm, we provide the Algorithm Steps button.

At each iteration a dialog is presented at the top of the worksheet with the current upper and lower bounds. The master problem on the worksheet can be seen behind the dialog. The constraint at the bottom of the model is the optimality constraint determined by the solution to the subproblem. The constraint is violated. In the second step the solution must satisfy the new constraint. The figures below show the five steps required for the example.


  Clicking the Step button on the final dialog will result in the optimum solution shown at the beginning of this discussion. At any iteration, clicking the Finish button terminates the step-wise display and finishes the problem. The Quit button exits the program so the student can review an intermediate.


Clear without Solving

  This option clears the extra constraints and the Theta variable from the model display. This option will be useful if additional constraints or variables are to be added to the model with the Change button or the solution method is changed to the Excel Solver.

Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved