The side-model construction
has several features and limitations not considered above.
Jensen LP/IP add-in modifies the method to
accommodate side models constructed by the Math Programming
useful feature is the inclusion of simple upper bounds
for the subproblem
not strictly hold with simple upper bounds unless they
are explicitly included as constraints. The method uses the
RHS computation that does not explicitly mention the subproblem
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
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
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.
add-in has a feature that allows optimality constraints
to be dropped after they become no longer binding to the
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
with the L-shaped method such problems are approachable
with the Jensen LP/IP Solver.