The sidemodel construction
has several features and limitations not considered above.
The
Jensen LP/IP addin modifies the method to
accommodate side models constructed by the Math Programming
addin.
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 sidemodel 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 sidemodel allows nonlinear objective
functions and integer variables, these features are not allowed
for the Lshaped 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 addin 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 addin includes a hotstart 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 addin does not use an advanced
start method for the master problem. The
addin 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 Lshaped method increases markedly the capability
of the addins 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 addins. When solved
sequentially
with the Lshaped method such problems are approachable
with the Jensen LP/IP Solver.
