Stochastic Regression L-Method L-Theory

 Mathematical Programming L-Shaped Theory

This page provides a mathematical development of the L-shaped method. Examples are included in other pages of this section and the section on stochastic programming.

The L-shaped method is applied to a model of the form below. Later we specialize the discussion to the case where the subproblem is actually a collection of independent submodels represented by our side-model form. We present the Master Problem and Subproblem in matrix format below. Except for the term , the master problem is a linear program in x and z. The subproblem is also a linear program with variables y. It is affected by z though it's right-hand-side matrix. It can be shown that the function is a piecewise-linear-convex function. In the following we assume that the subproblem is a linear program when z is fixed. Thus, we do not consider subproblems with integer variables or nonlinear terms. We also restrict attention problems for which a feasible solution to the subproblem exists for every feasible solution to the master problem. Although this is certainly not a characteristic of all models, it is always possible to add variables similar to the artificial variables of LP that assure this characteristic. Although this development assumes that subproblem variables are unbounded from above, the algorithm implemented by the add-in allows simple upper bounds. The implemented algorithm allows maximization as well as minimization of the objective.

Bounds

The L-shaped method does not solve these problems simultaneously, but as a series of approximating problems which determine lower and upper bounds on the optimum objective value for the master problem. When the bounds are equal, the optimum is obtained. We also allow the method to terminate when the bounds are sufficiently close.

An upper bound for the Master Problem objective is obtained by solving the subproblem for feasible x and z. The value of is the optimum subproblem objective for the specified z. The upper bound is the value of the Master Problem objective. Note that every feasible value of x and z provides an upper bound to the optimal objective value. We call the solution that provides the lowest upper bound at some stage of the process. The I subscript signifies that the solution is the incumbent solution.

To develop the lower bound we consider the dual of the subproblem. We obtain the Dual Model by the usual rules of linear programming. Note that the dual variables are unrestricted.

Since at least one of the optimum solutions to a linear program lies at an extreme point, the dual problem can be restated as an enumeration problem over all extreme points. In the model below each extreme point is associated with a vector of dual variables. There are L extreme points. is the value of the dual objective and it depends on z.

The master problem can now be rewritten with a single new variable, , and a large number of constraints, one for each extreme point of the subproblem dual.

Of course this reformulation is not very helpful, because for any practical problem the number of dual extreme points is very large. When some smaller number of extreme points is included in the master problem model, the result is a relaxation of the original master problem. Then the solution to the relaxed master problem provides an lower bound to the optimum objective.

We use the lower and upper bounds in the iterative L-shaped method described below.

Optimality Cut

During the algorithm we solve the subproblem for a fixed value of z. z determines the right-hand-side of the subproblem constraints. We obtain the primal and dual solutions as well as the optimum objective value. These are used to provide a new constraint for the relaxed master problem as shown below. We use the alternative formulation of the cut.

L-Shaped Method

In this method, the relaxed master problem is solved to find feasible values of x, z and . This provides a lower bound as above. Using the values of z obtained we solve the subproblem. The solution provides an upper bound and also an extreme point of the subproblem. We add the associated cut to the relaxed master. The process continues until the lower and upper bounds are equal or sufficiently close together.

Step 0.

Solve the master problem with not included. The solution provides the initial upper bound.

Step 1

With the solution z from the master problem, solve the subproblem. If the solution to the master and the optimum solution to the subproblem, provides a better upper bound, replace the bound and the incumbent solution. The solution to the subproblem provides a new optimality cut.

Step 2

Add the optimality cut to the master problem and solve it. The value of the objective provides a better lower bound.

Step 3

If the difference between upper and lower bounds is less than some tolerance the stop.

If the difference is zero, the optimum has been found. If it is not zero, then report the incumbent solution.

If the bounds are not within the specified tolerance return to step 1 for another iteration.

Independent Subproblems

The L-shaped method is most effective if the submodel consists of a number of independent subproblems. This is the type of model provided by our side-model construction. The term in the objective of the master problem is the weighted sum of objective values, one for each subproblem. The individual subproblems each have a dual. They are independent except they all are affected by z and they all have the same constraint matrix W. Note that our notation has the dual variables and parameter matrices subscripted with the subproblem number.

Optimality cuts at each step are computed by combining the dual variables from the subproblems. The subproblem variables are shown with two subscripts, the first for the subproblem and the second for the iteration number for the L-shaped method. In the expressions below the variables are at their optimum values. The alternative RHS expression is valid when the subproblem variables have simple upper bounds.

Modifications for the Side Model

The side-model construction has several features and limitations not considered above. The Jensen LP/IP add-in modifies the method to accommodate side models constructed by the Math Programming add-in.

One useful feature is the inclusion of simple upper bounds for the subproblem variables. The development does not strictly hold with simple upper bounds unless they are explicitly included as constraints. The method uses the alternative RHS computation that does not explicitly mention the subproblem constraint set.

The side-model allows only limited variation of the linking variable constraint coefficients. The model uses a fixed matrix T multiplied by diagonal matrices that may vary by subproblem. Although this is limiting, a number of interesting cases can be handled as illustrated by the examples in this section and in the section on stochastic programming.

Objective functions may be maximized as well as minimized. The optimality cuts change direction.

Although the side-model allows nonlinear objective functions and integer variables, these features are not allowed for the L-shaped method. Integer variables violate the condition for the convexity of . Although nonlinear objective functions may be convex, the Jensen LP/IP Solver cannot optimize nonlinear functions. The master problem can include integer variables, but the solution time for the branch and bound method may increase because of the added burden of solving the side model.

An important limitation is that the side models must be feasible for every z encountered by the method. This can only be guaranteed if the subproblems are feasible for every feasible solution of the master problem. One can always express subproblems in a way that satisfies this condition. The add-in stops whenever an infeasible subproblem solution is encountered. Infeasibility of the master problem will be discovered at the first step of the process. Optimality cuts cannot make the master problem infeasible.

For practical problems, the subproblems of a side model often have the same or similar optimal solutions with respect to the set of basic variables. After the first subproblem, the add-in includes a hot-start procedure that uses the basis obtained in the previous subproblem as the initial basis in the simplex method. When the basis is infeasible, a phase 1 procedure returns the solution to feasibility. For most problems this method reduces considerably the total number of simplex iterations required. At this time, the add-in does not use an advanced start method for the master problem.

The add-in has a feature that allows optimality constraints to be dropped after they become no longer binding to the master problem. Although this makes the master problem easier to solve, the lower bound may not decrease at each iteration and the method may not terminate.

Although limited, the provision of side models and the L-shaped method increases markedly the capability of the add-ins for math programming. A problem with a small master problem and many small subproblems may have thousands of variables and constraints when solved as a single combined problem. The problem would be far outside the capabilities of the free Excel Solver and the Jensen add-ins. When solved sequentially with the L-shaped method such problems are approachable with the Jensen LP/IP Solver.

Operations Research Models and Methods
Internet
by Paul A. Jensen