Ai*x uri + lD uri for i = 1 to m lcj + lDlcj
xj ucj + lD ucj for j = 1 to nThere are situations in which you might want to know more than the optimal solution to an LP problem. You might want to know how changes in the costs, row bounds, or column bounds of the problem might affect an optimal solution. These questions can be answered using sensitivity analysis and parametrics.
The following subsections describe how to use EKKSOBJ and EKKSBND to determine the sensitivity of the optimal basis to changes in an individual cost or an individual bound respectively; and also how to use EKKSPAR to investigate the consequences of simultaneously varying several costs and bounds over specified intervals.
This section describes the objective function sensitivity analyzer EKKSOBJ. The calling sequence, and notes on using EKKSOBJ, can be found in the description of the EKKSOBJ subroutine.
Notes:
EKKSOBJ determines how large a change is required in the objective function coefficients (costs) to cause the optimum to occur with a different basis. Each objective function coefficient is analyzed, unless the column selection list limits its processing to a specified set of variables. The selection lists can be set using EKKSEL if you are selecting by name, or by setting the selection list vectors directly in dspace using index control variables Nsellistcol and Nsellistrow. Note that EKKNAME can be used to create names before calling EKKSEL.
For each applicable variable, EKKSOBJ finds:
For each finite case above, EKKSOBJ finds:
See "Sample FORTRAN Program EXSENS1" and "Sample FORTRAN Program EXSENS2" for examples.
EKKSOBJ does not print this information. The information created by EKKSOBJ is printed by any subsequent calls to EKKPRTS because EKKSOBJ sets integer control variable Iprintsens to do so. This can be prevented by resetting Iprintsens. The information can also be obtained directly from dspace by using the index control variables.
Following is a list of control variables related to EKKSOBJ. For complete information on all control variables see Appendix C. "Control Variables".
Description: The sensitivity information printing bit mask. For
information on bit masks, see "Control Variable Bit Masks".
Description: The Fortran index into dspace created by EKKSOBJ
for the first element of the array of cost upper limits.
Description: The Fortran index into dspace created by EKKSOBJ
for the first element of the array of cost lower limits.
Description: The Fortran index into dspace created by EKKSOBJ for
the first element of ranges of the objective function values corresponding
to the upper limits on cost coefficients indexed by Nsobjupc.
Description: The Fortran index into dspace created by EKKSOBJ for
the first element of ranges of the objective function values corresponding
to the lower limits on cost coefficients indexed by Nsobjdnc.
Description: The Fortran index into mspace created by EKKSOBJ for
the first element of the array of entering rows or columns corresponding
to the increased cost coefficients indexed by Nsobjupc.
Description: The Fortran index into mspace created by EKKSOBJ for
the first element of the array of entering rows or columns corresponding
to the decreased cost coefficients indexed by Nsobjdnc.
Description: The Fortran index into mspace created by
EKKSOBJ for thefirst element of the array of leaving rows or columns corresponding
to the increased cost coefficients indexed by Nsobjupc.
Description: The Fortran index into mspace created by EKKSOBJ
for the first element of the array of leaving rows or columns
corresponding to the decreased cost coefficients indexed by Nsobjdnc.
This section describes the bound sensitivity analyzer EKKSBND. Its calling sequence, and notes on using EKKSBND, can be found in the description of the EKKSBND subroutine.
Notes:
EKKSBND shows what changes are required in the row and column bounds to cause the optimum to occur with a different basis.
As with EKKSOBJ, you can use selection lists to limit EKKSBND's processing to specified rows (bounds) or columns (variables). The selection lists can be set using EKKSEL if you are selecting by name, or by setting the selection list vectors directly in dspace using index control variables Nsellistcol and Nsellistrow. Note that EKKNAME can be used to create names before calling EKKSEL.
EKKSBND finds the following for each of the selected variables:
See "Sample FORTRAN Program EXSENS1" and "Sample FORTRAN Program EXSENS2".
EKKSBND does not print this information. The information created by EKKSBND will be printed by any subsequent calls to EKKPRTS because EKKSBND sets integer control variable Iprintsens to do so. This can be prevented by resetting Iprintsens. The information can also be obtained directly from dspace by using the index control variables.
Following is a list of control variables related to EKKSBBND For complete information on all control variables, see Appendix C. "Control Variables".
Description: The sensitivity information printing bit mask. for
information on bit masks, see "Control Variable Bit Masks".
Description: The Fortran index into dspace created by
EKKSBND for the first element of the upper limits on column bounds.
Description: The Fortran index into dspace created by
EKKSBND for the first element of the lower limits on column bounds.
Description: The Fortran index into dspace created by
EKKSBND for the first element of the ranges of objective function
values corresponding to the upper limits on column bounds indexed
by Nsbndcupb.
Description: The Fortran index into dspace created by EKKSBND for the
first element of ranges of the objective function values corresponding
to the lower limits on column bounds indexed by Nsbndcdnb.
Description: The Fortran index into mspace created by EKKSBND for the
first element of the array of entering rows or columns corresponding
to the upper limits on column bounds indexed by Nsbndcupb.
Description: The Fortran index into mspace created by EKKSBND for the
first element of the array of entering rows or columns corresponding
to the lower limits on column bounds indexed by Nsbndcdnb.
Description: The Fortran index into mspace created by EKKSBND for the
first element of the array of leaving rows or columns corresponding
to the upper limits on column bounds indexed by Nsbndcupb.
Description: The Fortran index into mspace created by EKKSBND for the
first element of the array of leaving rows or columns corresponding
to the lower limits on column bounds indexed by Nsbndcdnb.
Description: The Fortran index into dspace created by EKKSBND for the
first element of the upper limits on row bounds.
Description: The Fortran index into dspace created by EKKSBND for the
first element of the lower limits on row bounds.
Description: The Fortran index into dspace created by EKKSBND for the
first element of the ranges of the objective function
values corresponding to the upper limits on row
Description: The Fortran index into dspace created by EKKSBND for the
first element of ranges of the objective function values
corresponding to the lower limits on row bounds.
Description: The Fortran index into mspace created by EKKSBND for
the first element of the array of entering rows or columns
corresponding to the upper limits on row bounds indexed
by Nsbndrupb.
Description: The Fortran index into mspace created by EKKSBND for
the first element of the array of entering rows or columns
corresponding to the lower limits on row bounds indexed
by Nsbndrdnb.
Description: The Fortran index into mspace created by EKKSBND for the
first element of the array of leaving rows or columns corresponding
to the upper limits on row bounds indexed by Nsbndrupb.
Description: The Fortran index into mspace created by EKKSBND for the
first element of the array of leaving rows or columns corresponding
to the lower limits on row bounds indexed by Nsbndrdnb.
The Optimization Library includeds a parametric solver that shows how the objective value and optimal solution change as the bounds and objective function coefficients are changed across a range of values: In contrast to sensitivity analysis, where each item is examined to see how changing it alone would affect the results, in parametric analysis all these data may be changed at once. The calling sequence, and notes on using EKKSPAR, can be found in the description of the EKKSPAR subroutine.
You indicate how much each of the items listed above should be changed by supplying five vectors using either EKKPMDL or EKKMPS. These vectors, listed below, specify how much to add to each of the bounds and costs.
|
Note: |
If you want to read in the parametric delta vectors from an MPS file, you must set the character control variables Cchangeobj, Cchangerhs, Cchangerange, and Cchangebounds to the appropriate names in the MPS file before calling EKKMPS. |
We show how to solve the following problem:
minimize
( c + l Dc ) T x
subject to: lri + lD lri Ai*x uri + lD uri for i = 1 to m
lcj + lDlcj xj ucj + lD ucj for j = 1 to n
as l changes from its initial value to its limiting value (l lim) by its increment value(Dl).
where:
|
Note: |
l , llim, Dl are given by the values of the real control variables Rslambda, Rslambdalim, and Rslambdadelta, respectively. |
Some solution information is printed out at each increment point and at each point where the basis changes. Also, EKKITRU is called by EKKSPAR at these increment points and basis change points.
See "Sample FORTRAN Program EXPARA1" and "Sample FORTRAN Program EXPARA2".
Following is a list of control variables related to EKKSPAR. Note that in addition to these control variables, all the control variables discussed in the section "Simplex (EKKSSLV)" are also applicable, because EKKSPAR may call EKKSSLV to solve the linear programming problem.
For complete information on all the integer and real control variables, refer to Appendix C. "Control Variables". Also, the contents of arrays pointed to by index control variables may change during execution. For information about these control variables, refer to "EKKNGET - Request Current Start Indices of OSL Information".
|
Note: |
maxint refers to the maximum allowable integer value on your platform, and maxreal refers to the maximum allowable real value on your platform. |
Description: The value of the EKKSPAR parameter l..
Description: The limiting value for the EKKSPAR parameter l..
Description: The incrementing value for the EKKSPAR parameter l.
Description: The Fortran index into dspace for the parametric cost
(objective) change vector created for EKKSPAR.
Description: The Fortran index into dspace for the row lower bounds
parametric change vector created for EKKSPAR.
Description: The Fortran index into dspace for the row upper bounds
parametric change vector created for EKKSPAR.
Description: The Fortran index into dspace for the column lower bounds
parametric change vector created for EKKSPAR.
Description: The Fortran index into dspace for the column upper bounds
parametric change vector created for EKKSPAR.
Description: The name of the cost (objective) change row in the
MPS file to be used by EKKSPAR. EKKMPS will look for this row
in the ROWS section of the input stream.
Description: The name of the RHS change in the MPS file to be used
by EKKSPAR. EKKMPS will look for this entry in the RHS section.
Description: The name of the range change in the MPS file to be
used by EKKSPAR. EKKMPS will look for this entry in the RANGES
section of the input stream.
Description: The name of the bounds change in the MPS file to
be used by EKKSPAR. EKKMPS will look for this entry in the
BOUNDS section of the input stream.
This section describes the infeasibility analasis subroutine EKKNFES. Its calling sequence, and notes on using EKKNFES, can be found in the description of the EKKNFES subroutine.
A linear programming problem is infeasible, if there is no solution that satifies all the constraints of the problem. It is often a time consuming and frustrating task to determine which of the constraints are mutually incompatible, and thus why the problem is infeasible. OSL includes an infeasibility analysis checking subroutine, named EKKNFES, to assist with this task. This subroutine has four possible modes of operation, determined by the value of the third parameter (called "mask") in its calling sequence. This parameter, as its name implies, is a bit mask, and the possible modes of operation are not mutually exclusive.
If mode one is "on," EKKNFES will print out the names of rows and columns whose activities violate one of their bounds. The OSL output subroutine, EKKPRTS can do this too, but the information is included with a lot of other information. (Note that if the problem has been presolved, the row's may have been shuffled, and hence the row names may be unavailable.)
If mode two is "on," EKKNFES will identify a subset of the initial infeasibilities with the property that if all the initial infeasibilities but one from among these are removed (by relaxing the corresponding constraints), then the problem will still be infeasible.
If mode three is "on," EKKNFES will try to identify a subset of the entire set of constraints with the property that if any one of these constraints is relaxed, then the resulting problem has significantly (at least 50%) fewer infeasibilities.
If mode four is "on," EKKNFES will attempt to identify an irreducible infeasible subset of constraints with the property that if all the constraints of the problem except the members of the IIS are relaxed, the resulting problem will still be infeasible, but if then any single member of the IIS is also relaxed, the resulting problem will become feasible. The algorithm employed to identify an IIS is based on the work of John Chinneck.
The possible values of the "mask" parameter are 0 - 15. The correspondence between values of "mask" and the possible modes of operation, just described, is as follows:
The default mode of output for EKKNFES is to put results out as OSL output messages to stdout. In processing modes 1 - 3, this is the only possibility. In mode 4, one can specify that the row and column numbers of members of the IIS found be (or not be) loaded into an array provided - instead of, or in addition to, being put out in OSL output messages to stdout. This is accomplished by assigning the appropriate value to the fourth parameter (called "output") in the subroutine's calling sequence. As before, the parameter is a bit mask, but here only the first two bits are used. If mode 4 is on, and bit one of "output" is nonzero, EKKNFES will put output to stdout, and if bit two of "output" is nonzero, EKKNFES will write output into the table provided. If writing to a table is requested, and the space provided is not large enough to hold the data, EKKNFES will fill the available space, and issue a warning message. It will not write beyond the end of the table.
See the description of the EKKNFES subroutine for more information on its calling sequence and notes on its use. See "Sample FORTRAN Program EXNFES" for an example of the use of EKKNFES.
[ Top of Page | Previous Page | Next Page | Table of Contents ]