typedef struct {
long nrow; /* number of rows */
long ncol; /* number of columns */
long nels; /* number of matrix elements */
long nstg; /* number of stages */
long nblocks; /* number of blocks in matrix */
double *drlo,*drup; /* row bounds */
double *dclo,*dcup; /* column bounds */
double *dobj; /* objective */
long *mrow; /* matrix row indices */
long *mcol; /* matrix column indices */
double *dels; /* matrix elements */
long *rowstart; /* starts for stage partition of rows */
long *colstart; /* starts for stage partition of cols */
long *elemstart; /* starts for stage partition of matrix
Matrix is partitioned by row blocks
and then by column blocks
thus t*(t+1)/2-1 is the matrix index for
the start of the t-th stage node block
(as would be obtained by numbering blocks
starting from the top and moving left to
right).The matrix is assumed full lower
block triangular. */
long *sortin2exr; /* in-to-external row index translation */
long *sortin2exc; /* in-to-external col index translation */
} usrCoreData;
The three arrays rowstart, colstart and elemstart
identify the starting indices for each time stage in the list of row, column,
and matrix entry indices respectively. Index numbering for matrix elements
always begins from one (for compatibility with the IBM Optimization Library).
If, for example, the rows with indices 1, 2, 3, and 4 are first stage rows, and the rows with indices 5, 6, 7, 8, 9, and 10 are second stage rows, then the first four entries in the row bounds arrays drlo and drup are bounds for the first stage rows, and the next six entries are bounds for the second stage rows. Of course, the ordering here may not correspond to the original ordering in the calling sequence for the ekks_CreateCore subroutine that created the core data structure. The array sortin2exr provides the original row indices. Thus, the first element of sortin2exr gives the original index for the first row, etc. Similar comments hold for the column arrays colstart and sortin2exc.
The elemstart array has a more complex structure. The core
matrix is sorted first into row blocks, within which each row belongs to
the same stage, and then each row block sorted into column blocks, within
which each column belongs to the same stage. For example, if the problem
has 4 stages, then this method sorts the matrix into lower block triangular
form with up to ten blocks in the following order: In this case the elemstart
array has 11 entries. For example, if then the diagonal block 6 has 9 entries
starting at the 26th entry of the matrix triple (mrow, mcol, dels),
and the off-diagonal blocks 4, 7 and 8 have no entries at all. The matrix
triple is stored "by indices," and thus the 26th entry has value
dels[25] (using the indexing convention of the C programming language)
row index mrow[25] and column index mcol[25].
typedef struct {
long nnode; /* number of nodes */
usrNode *node; /* array of node structures */
long nleaf; /* number of leaves */
long *leaf; /* list of leaf positions in node array (first=1) */
void *user; /* (optional) pointer to user structure */
} usrStoch;
The nodes are described by an array of Node structures. The leaves
of the tree are identified by the leaf array. For example, if
one has then there are three scenarios in the model and the terminal nodes
of the scenarios are described by the 4th, 8th, and 9th entries in the
node array. A pointer is provided to point to a user structure,
if needed (this information is for the user's purposes only; at this time
it cannot be stored or retrieved). typedef struct {
double prob; /* probability of node in model */
long orig; /* original node name (numbered from 1) */
long par; /* parent's position in list (first=1) */
long child; /* next-stage child (end=0) */
long sib_cous;/* same-stage sibling or cousin (end=0) */
long stag; /* original time stage */
long scen; /* original scenario number */
long rbas; /* row offset in matrix */
long cbas; /* column offset in matrix */
long nrow; /* number of rows */
long ncol; /* number of columns */
long virtual; /* = 1 if node not actually in model */
void *user; /* (optional) pointer to user structure */
} usrNode;
A node points to all information and data corresponding to a given time
stage along a given scenario. The prob field contains the node's
probability in the stochastic model. This probability multiplies the node's
objective in the stochastic model. The orig field identifies the
node's original numbering in the Stoch_Data structure, and must
be used when accessing the LP data for the node.
The next three fields allow the user to move around the tree. The numbers refer to the ordering in the node array of the Stoch structure. The par field identifies the node's parent, that is, the node from which it branched in the stage immediately preceding. If the node happens to be a root, then its par field is set equal to zero. The child field identifies one of the children of the node. If there are no children (i.e. this is a leaf node) the field is set to zero. The sib_cous field identifies one sibling (that is, sharing a common parent) or cousin (merely share the same time stage). The sib_cous fields of nodes sharing a common time stage are arranged in a ring. All children of a node node can be found by following the sib_cous fields of the child, checking to see that they all share the same parent. All nodes of a given stage can be found by following the sib_cous fields around until the starting point is reached again.
The stag field identifies the node's stage and the scen
field the original scenario number. The two fields rbas and cbas
are the row and column bases that give the node's offset in the (deterministic
equivalent) stochastic model. Finally, the virtual field identifies
whether the node was (=0) or was not (=1) included in the nodelist which
generated the stochastic model. Nodes whose descendents are in a model
but that do not themselves appear in the nodelist generating the model
need to be identified as such when constructing the LP for the stochastic
model, so that offsets may be allocated for the virtual node columns. A
pointer is provided to point to a user structure, if needed (this information
is for the user's purposes only; at this time it cannot be stored or retrieved).
typedef struct {
long stg; /* stage of node ( = number of partitions) */
long nrow; /* number of rows */
long ncol; /* number of columns */
long nels; /* number of node block elements */
double *drlo,*drup; /* row bounds */
double *dclo,*dcup; /* column bounds */
double *dobj; /* objective */
long *mrow; /* block row indices */
long *mcol; /* block column indices */
double *dels; /* block elements */
long *elemstart; /* starts for stage partition of node block:
thus t-1 is the index for the start of the
t-th stage arc block and stg-1 is the
index for the start of the node block.
The node block has (poss.empty) arc
blocks for all stages t < istg. */
} usrNodeData;
This data must be combined with the core data to construct the actual node
LP data. The convention in IBM Stochastic Extensions is to add the
core and stochastic data.
When a user accesses node data, the incoming arc matrices are copied over in the same subroutine call. This should be taken into consideration when transferring large amounts of data from the SP-file into memory.
The matrix associated with a node is the stochastic row-block;
that is, all the stochastic row data in the given time stage in the given
scenario are found in this matrix. Of course, there may not be any elements
in the stochastic row-block. The structure of the matrix is similar to that
of the matrix in the CoreData structure, that is, it has been
sorted into column blocks, by stage. The column indices in each of the
column-blocks have been normalized to begin with index 1. The actual column
index of an off-diagonal block is found by locating the node's ancestor for
that stage and adding the ancestor's column offset cbas to the
matrix column index. The actual column index of the diagonal block is found
by adding the current node's column offset cbas to the column
index. The actual row index of all entries is found by adding the row
offset rbas for the current node.
Takes an event for a INDEP_DISCRETE distribution and adds it as
a scenario.
FUNCTION PROTOTYPE:
void ekks_AddEvent (long *rc, Stoch_Data *stoch, Tree **treep,
long *index, double dp, long replace );
INPUT:
Stoch_Data *stoch pointer to a Stoch_Data struct
Tree **treep address of pointer to event tree under
construction (must be NULL in first call)
long *index pointer to event indices
double dp probability
long replace 0=>add to, 1=>replace core values
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Adds a scenario to stochastic problem, sets the scenario probability,
the branching information, and stores the scenario data by node in
an SPL file.
Errors occur when branching information is inconsistent
or when dimensions are inconsistent with the core.
If this call is repeated for the same scenario, the
scenario probability is incremented by the amount of
the new probability. No other data is changed.
All scenario LP data is ADDED to the corresponding core data when
forming an LP. This requires a convention for dealing with infinite
bounds in the core. If the core value is infinite and the incoming
scenario value is nonzero, then a warning message is issued and the
incoming scenario value is set to zero.
CORE VALUE SCENARIO VALUE ACTION MESSAGE RC
finite infinite none none 0
infinite nonzero scenario value zeroed warning 1
The LP data is NOT kept in core memory. (It may be retrieved
for the user by a call to ekks_GetNodeData.) The LP matrix
must be in "indices" sparse format.
If replace = 0:
LP data should be the "difference" of the intended scenario
LP data and the core LP data.
If replace = 1:
Scenario LP data should "replace" the core LP data. In this
case, the subroutine calculates the difference for you.
FUNCTION PROTOTYPE:
void ekks_AddScenario (long *rc, Stoch_Data *stoch, long nscn,
long ianc, long istg, double dprob, long itype, long nrow,
long ncol, long nels, double *dobj, double *drlo,
double *drup, double *dclo, double *dcup, long *mrow,
long *mcol, double *dels, long replace );
INPUT:
Stoch_Data *stoch pointer to Stoch_Data struct initialized
by ekks_InitializeApplication
long nscn scenario number (1, 2, ...)
long ianc ancestor scenario number
long istg branching stage number
double dprob probability of scenario
long itype matrix type (MUST be 1 - by indices format)
long nrow number of rows (must match core model)
long ncol number of columns (must match core model)
long nels number of elements in scenario matrix
double *dobj array of objective entries
double *drlo array of row lower bound entries
double *drup array of row upper bound entries
double *dclo array of column lower bound entries
double *dcup array of column upper bound entries
long *mrow array of matrix row indices
long *mcol array of matrix column indices
double *dels array of matrix entries
long replace 0=>add to, 1=>replace core values
Output:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Updates scenario tree with data values in arr[].
If arr[] is already in tree, then ekks_AddToTree increments
counters and returns the original scenario number, otherwise
it creates a new scenario from data values in arr[], and returns
the newly created scenario number.
FUNCTION PROTOTYPE:
long ekks_AddToTree (long *rc, Tree *tree, long *arr, long narr,
double dp);
INPUT:
Tree *tree pointer to tree initialized by
ekks_InitializeTree
long *arr point to array of integer values
long narr number of data values (stages) in arr[]
double dp probability of events
OUTPUT:
long *rc pointer to return code:
1 if maximum number of samples exceeded
2 if tree not initialized or corrupted
RETURNS:
scenario number as described above
Applies Benders L-shaped decomposition to the stochastic model,
with cut made at the stage number IPCUT.
METHODOLOGY:
A single master problem is created and up to MAXMOD subproblems
corresponding to a cut made at stage IPCUT; that is, the master
problem contains all rows and columns for stages prior to IPCUT.
If MAXMOD is not sufficient to hold all the subproblems, the
subproblems are distributed as evenly as possible among the
MAXMOD models.
The program performs MAXITS iterations of Benders decomposition,
terminating if optimality, infeasibility, or unboundedness
is detected.
FUNCTION PROTOTYPE:
void ekks_BendersLSolve (long *rc, Stoch_Model *smodel,
long ipcut, long maxmod, long maxits, double rmaxmin,
long inwmt, long icrsh, long ilpdc, long iscal,
long iprsl, long iprsltype, long iprslunit, long isalg,
long largebounds, long *status, double *optgap );
INPUT:
Stoch_Model *smodel pointer to stochastic model created by OSL
long ipcut period at which Benders cuts are made
long maxmod maximum number of subproblems
long maxits maximum number of Master iterations
double rmaxmin -1.0 => maximize, 1.0 => minimize
long inwmt compress model matrices into a new copy,
0 => do not compress
long iscal 0=>don't, 1=>do scale each submodel
long icrsh type of crash to perform before first
solution of submodels (0 => none)
long ilpdc 0=>don't, 1=>do do LP decomposition for
each submodel
long iprsl 0=>don't, 1=>do presolve each submodel
long iprsltype type of presolve
long iprslunit presolve unit
long isalg specifies simplex algorithm to be used by
EKKSSLV for first solution of submodels
long largebounds 0=>don't, 1=>do add large bounds to master
double *optgap pointer to maximum optimality gap before
stopping BendersLSolve
OUTPUT:
long *rc pointer to return code (code >1 => fatal error)
long *status pointer to status; value = 0=>optimal,
1=>infeasible, 2=>unbounded, 3=>unfinished
double *optgap pointer to Optimality gap at termination
RETURNS:
void
Updates leaf node probabilities with new scenario probabilities.
Note: The original scenario probabilities are unaffected.
These can be restored by a call to ekks_ChangeProbability
with a NULL usrProb parameter.
FUNCTION PROTOTYPE:
void ekks_ChangeProbability ( long *rc, Stoch_Data *stoch,
double *usrProb );
INPUT:
Stoch_Data *stoch pointer to Stoch_Data struct initialized
by ekks_InitializeApplication
double *usrProb pointer to array of new probabilities
OUTPUT:
long *rc pointer return code (2 is fatal)
RETURNS:
void
Clears registration of a call back function previously registered
by a call to ekkse_RegisterCallBack
FUNCTION PROTOTYPE:
void ekkse_CloseCallBack (int *cbid);
INPUT:
int *cbid pointer to user exit id number
RETURNS:
void
Sorts core model row and column indices by stages, groups core
model data into blocks corresponding to stages, and stores all
model information, sort keys, and grouped data into an SPL file.
The data may be accessed by a call to ekks_GetCoreData.
FUNCTION PROTOTYPE:
void ekks_CreateCore (long *rc, Stoch_Data *stoch, long nstg,
long *Rstag, long *Cstag, long irow, long icol, long iels,
double *dobj, double *drlo, double *drup, double *dclo,
double *dcup, long *mrow, long *mcol, double *dels,
double *dqdg);
INPUT:
Stoch_Data stoch pointer to Stoch_Data struct initialized
by ekks_InitializeApplication
long nstg number of stages in the core model
long *Rstag array of stage numbers for rows
long *Cstag array of stage numbers for columns
long irow number of rows in core model
long icol number of columns in core model
long iels number of matrix elements in core model
double *dobj array of objective entries
double *drlo array of row lower bound entries
double *drup array of row upper bound entries
double *dclo array of column lower bound entries
double *dcup array of column upper bound entries
long *mrow array of matrix row indices
long *mcol array of matrix column indices
double *dels array of matrix entries
double *dqdg array of quadratic matrix diagonal entries
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Performs a Benders cut on smodel before stage ipcut, creating node
lists for at most maxmodels problems. The first list is for the
root subproblem, and consists of all (nonvirtual) nodes having stage
less than ipcut. The rest of the nodes are distributed among the
leaf subproblems in such a way that the difference in the number of
branches allocated between any two subproblems is no more than one.
FUNCTION PROTOTYPE:
void ekkse_CutModelAtStage (long *rc, Stoch_Model *smodel,
long *ipcut, long maxmodels);
INPUT:
Stoch_Model *smodel pointer to Stoch_Model to be cut
long ipcut period at which model is cut
long maxmodels maximum number of models (Master + Subs)
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Generates "depth-first" partition of the model. Number of nodes is
controlled by the value of maxNodes. The minimum size of a
model is determined by dividing 0.9 times the value of maxNodes
into the number of rows of the problem.
The method adds a scenario to a model, then starting from the leaf
and going back to the root, all children of the parent of the node
are added until the minimum size is reached.
Then models with smaller than minimum are added to their masters,
until maxNodes models remain.
FUNCTION PROTOTYPE:
void ekkse_CutModelByNode (long *rc, Stoch_Model *smodel,
long maxNodes, long **masters);
INPUT:
Stoch_Model *smodel pointer to Stoch_Model to be cut
long maxNodes maximum number of nodes
to be generated
MODIFIED:
long **masters list of master nodes for submodels
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Generates "depth-first" partition of the model. Size of models is
controlled by the value of minNumRows.
The method adds a scenario to a model, then starting from the leaf
and going back to the root, all children of the parent of the node
are added until minNumRows is reached.
FUNCTION PROTOTYPE:
void ekkse_CutModelByRow (long *rc, Stoch_Model *smodel,
long minNumRows, long **masters);
INPUT:
Stoch_Model *smodel pointer to Stoch_Model to be cut
long minNumRows minimum number of rows per model
OUTPUT:
long *rc pointer to return code (2 is fatal)
long *masters list of master nodes for each submodel
RETURNS:
void
Create parametric stochastic model
The user supplies arrays which are used to perturb the objective
and bounds of the CORE model. These then are sorted and replicated
to produce perturbations for the stochastic model (objective
perturbations are multiplied by the node probabilities). The CORE
perturbation is replicated for each node of the stochastic model.
FUNCTION PROTOTYPE:
void ekkse_DefineParametricModel (long *rc, Stoch_Model *smodel,
double *cdelta, double *lrdelta, double *urdelta,
double *lcdelta, double *ucdelta, long mask );
INPUT:
Stoch_Model *smodel pointer to stochastic model initialized by OSL
double *cdelta array of objective coefficient perturbations
double *lrdelta array of lower row bound perturbations
double *urdelta array of upper row bound perturbations
double *lcdelta array of lower column bound perturbations
double *ucdelta array of upper column bound perturbations
long mask determines which perturbations are used:
mask = C*1 + LR*2 + UR*4 + LC*8 + UC*16
where C, LR, UR, LC, and UC are 1 or 0
depending on whether a perturbation of the
corresponding objective coefficient, row, or
column bound is (1) or is not (0) to be made
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Creates model node information structures and offsets from
user-supplied nodelist.
If nodelist is empty (nnodes=0) then all nodes in the Stoch_Data
struct are included.
Node probabilities are inherited from Stoch_Data structure.
Zero probability nodes (and their incoming arcs) are removed.
Virtual nodes (ancestors not in model one of whose children are)
are recorded and offset by the total number of real node columns.
If calcprob is set, the probabilities for each node are recomputed
and normalized so that the probability totals to one.
No matrix data is passed. Number of blocks to be passed is returned.
FUNCTION PROTOTYPE:
void ekks_DescribeModel (long *rc, Stoch_Data *stoch, long nnodes,
long *usrndlist, Stoch_Model **smodel,
long *nblocks, long calcprob );
INPUT:
Stoch_Data *stoch pointer to Stoch_Data structure
long nnodes number of nodes
long *usrndlist pointer to list of nodes to be included
in model
long calcprob 0=>don't, 1=>do recompute node probabilities
OUTPUT:
Stoch_Model **smodel pointer to new stochastic model
long *nblocks number of blocks in model
RETURNS:
void
Finds the node corresponding to arr[0, ..., nstg-1], and reports
the conditional distribution to standard output.
FUNCTION PROTOTYPE:
void ekkse_DistributionAtTreeNode (long *rc, Tree *tree,
long *arr, long narr);
INPUT:
Tree *tree pointer to Tree struct initialized by
ekks_InitializeTree
long *arr pointer to array of integer values
long narr number of data values (stages) in arr[]
OUTPUT:
long *rc return codes:
1 if maximum number of samples exceeded
2 if tree not initialized or corrupted
RETURNS:
void
Free all data structures and temporary files associated with
the Stoch_Data or Stoch_Model structure.
FUNCTION PROTOTYPE:
void ekks_FreeStructure (Stoch *stoch);
INPUT:
Stoch *stoch pointer to Stoch_Model or Stoch_Data to be deleted
RETURNS:
void
Copy core data pointers into the usrCoreData struct.
If *pcore is NULL, then a new usrCoreData struct is malloc'ed
and the pointer returned.
The data pointed to by usrCoreData pointers is stable.
(It is the original data as formed by ekks_CreateCore.)
FUNCTION PROTOTYPE:
void ekks_GetCoreData (long *rc, Stoch_Data *stoch,
usrCoreData **pcore );
INPUT:
Stoch_Data *stoch pointer initialized by ekks_CreateCore
and ekks_InitializeApplication
OUTPUT:
usrCoreData **pcore address of pointer to type usrCoreData
RETURNS:
void
Put scenario duals at location pointed to by dualsout[].
(Must be allocated by user.)
FUNCTION PROTOTYPE:
void ekkse_GetDualSolution (long *rc, Stoch_Model *smodel, long s,
long colrowtype, double *solution, long *indx);
INPUT:
Stoch *stoch pointer to the Stoch_Model or Stoch_Data struct
long s scenario number for which solution
info is desired
long colrowtype type of solution values desired
(1 => rows, else columns)
OUTPUT:
long *rc pointer to return code (2 is fatal)
double *solution pointer to the solution
long *indx pointer to the indices
RETURNS:
void
Get stochastic node data into usrNodeData struct
Allocates a new usrNodeData struct. Accesses stochastic matrix
and costs/bounds data from SPL file and places them in volatile
working memory.
Costs and bounds are expanded to their dense form.
usrNodeData pointers are appropriately set.
Note: ALL matrix and costs/bounds arrays are volatile!
The next call to a Stochastic Solutions/Extensions
routine WILL OVERWRITE THEM! (To protect yourself,
copy them to a memory region that you maintain.)
Note: The matrix and costs/bounds arrays contain only the
stochastic part of the data. They must be ADDED to
the relevant core data.
FUNCTION PROTOTYPE:
void ekks_GetNodeData (long *rc, Stoch_Data *stoch, long node,
usrNodeData **punode );
INPUT:
Stoch_Data *stoch pointer to a Stoch_Data struct initialized
by ekks_InitializeApplication
long node node number to be accessed
OUTPUT:
long *rc pointer to return code (2 is fatal)
usrNodeData **punode pointer to usrNodeData
RETURNS:
void
Mallocs an independent data struct and sets it to point to the
information collected in a ekks_ReadMPS reading of an
INDEPENDENT/DISCRETE format.
FUNCTION PROTOTYPE:
void ekks_GetPointerToDistribution ( long *rc, Stoch_Data *stoch,
Independent **s_indep );
INPUT:
Stoch_Data *sdata pointer to a Stoch_Data struct
OUTPUT:
long *rc pointer to return code (2 is fatal)
Independent **s_indep pointer to an Independent struct
RETURNS:
void
Gets a pointer to the solution region for a stochastic model.
FUNCTION PROTOTYPE:
void ekks_GetPointerToReducedCosts (long *rc, Stoch *stoch,
long *nmod, double **redcosts, long *ncol);
INPUT:
Stoch *stoch pointer to Stoch_Model or Stoch_Data struct
long *nmod pointer to the number of the model
OUTPUT:
double **redcosts pointer to solutions region
long *rc pointer to return code (2 is fatal)
long *ncol pointer to the number of columns
RETURNS:
void
Gets a pointer to the solution region for a stochastic model.
FUNCTION PROTOTYPE:
void ekks_GetPointerToRowDuals (long *rc, Stoch *stoch, long *nmod,
double **rowduals, long *nrow);
INPUT:
Stoch *stoch pointer to Stoch_Model or Stoch_Data struct
long *nmod pointer to the number of the model
OUTPUT:
double **rowduals pointer to the solutions region
long *rc pointer to return code (2 is fatal)
long *nrow pointer to the number of rows
RETURNS:
void
Gets a pointer to the solution region for a stochastic model.
FUNCTION PROTOTYPE:
void ekks_GetPointerToRowSolution (long *rc, Stoch *stoch,
long *nmod, double **rsoln, long *nrow);
INPUT:
Stoch *stoch pointer to Stoch_Model or Stoch_Data struct
long *nmod pointer to the number of the model
OUTPUT:
double **rsoln pointer to the solutions region
long *rc pointer to return code (2 is fatal)
long *nrow pointer to the number of rows
RETURNS:
void
Gets a pointer to the solution region for a stochastic model.
FUNCTION PROTOTYPE:
void ekks_GetPointerToSolution (long *rc, Stoch *stoch, long *nmod,
double **dsoln);
INPUT:
Stoch *stoch pointer to Stoch_Model or Stoch_Data struct
long *nmod pointer to the number of the model for which
the solution pointer is desired
OUTPUT:
long *rc pointer to return code (2 is fatal)
double **dsoln pointer to the solutions region
RETURNS:
void
Finds scenario information for sample number nsmp.
Note: if branching stage, "istg", has value 1, this means
that the scenario branches from the root (ianc=0).
FUNCTION PROTOTYPE:
void ekks_GetScenarioFromTree (long *rc, Tree *tree, long nsmp,
long *ianc, long *istg, double *wgt, long *nscn, long **arr);
INPUT:
Tree *tree pointer to Tree struct initialized by
ekks_InitializeTree
long nsmp sample number (first sample is 0, etc)
OUTPUT:
long *rc pointer to return code:
1 if maximum number of samples exceeded
2 if tree not initialized or corrupted
long *ianc pointer to ancestor scenario number
long *istg pointer to branching stage number
double *wgt pointer to scenario weight
long *nscn pointer to scenario number
long **arr pointer to data array for scenario
RETURNS:
void
Creates a user accessible stochastic struct
The user needs to copy over the information to
preserve it beyond the next Stochastic Solution call.
The input can be either a Stoch_Data struct or a
Stoch_Model structure, in which case information for
only those nodes in the model is compiled.
FUNCTION PROTOTYPE:
void ekks_GetScenarioTree (long *rc, Stoch *stoch,
usrStoch **pstree );
INPUT:
Stoch *stoch pointer to a Stoch_Data or Stoch_Model struct
OUTPUT:
long *rc pointer to return code (2 is fatal)
usrStoch **pstree pointer to a usrStoch structure
Note: arrays pointed to by pstree are volatile!
RETURNS:
void
Gets a solution for a scenario.
FUNCTION PROTOTYPE:
void ekks_GetSolution (long *rc, Stoch *stoch, long s,
long colrowtype, double *solution, long *indx);
INPUT:
Stoch *stoch pointer to Stoch_Model or Stoch_Data struct
long s scenario number for which solution
info is desired
long colrowtype type of solution values desired
(1 => rows, else columns)
OUTPUT:
long *rc pointer to return code (2 is fatal)
double *solution pointer to solution data
long *indx pointer to indices
RETURNS:
void
Copies Stoch_Data structures from SPL file.
FUNCTION PROTOTYPE:
void ekks_GetStochasticData (long *rc, Stoch_Data *stoch,
const char *filename );
INPUT:
Stoch_Data *stoch pointer to Stoch_Data struct initialized by
ekks_InitializeApplication
char *filename name of SPL file
OUTPUT:
long *rc return code (2 is fatal)
RETURNS:
void
Initializes Stochastic data structures
FUNCTION PROTOTYPE:
int ekks_Initialize();
RETURNS:
integer return code
Allocates pointers for stochastic data structures,
opens SPL file, returns Stoch_Data pointer
FUNCTION PROTOTYPE:
void ekks_InitializeApplication (long *rc, Stoch_Data **stoch,
long maxscn );
INPUT:
long maxscn maximum number of scenarios
OUTPUT:
long *rc pointer to return code (2 is fatal)
Stoch_Data **stochdata pointer to Stoch_Data struct
RETURNS:
void
Creates tree and initializes structures.
Creates first scenario from data values in arr[].
FUNCTION PROTOTYPE:
void ekks_InitializeTree (long *rc, Tree **tree, long *arr,
long narr, long *mxsmp, double dp );
INPUT:
long *arr pointer to an array of integer values
long narr number of data values (stages) in arr[]
long mxsmp maximum number of samples to be stored
long dp probability of events
OUTPUT:
long *rc pointer to return code 0
Tree *tree pointer to tree structure
RETURNS:
void
Applies Nested decomposition to the stochastic model smodel.
METHODOLOGY:
Subproblems are created according to the assignment of nodes
to subproblems. The logic is as follows:
if minNumRows > 0, nodes are accumulated into subproblems
until minNumRows is exceeded
else if ipcut > 0, subproblems are generated by cutting
at period ipcut
else if maxmod > 0, use minNumRows = 0.9 * totalrows/maxmod
and distribute any excess evenly among subproblems
The program performs MAXCYCLES iterations of Nested
decomposition, terminating if optimality, infeasibility,
or unboundedness is detected.
FUNCTION PROTOTYPE:
void ekkse_NestedLSolve (long *rc, Stoch_Model *smodel,
long minNumRows, long ipcut, long maxmod, long maxcycles,
double rmaxmin, long inwmt, long icrsh, long iscal,
long isslvalg, long isslvinit, long largebounds,
long *status, double *optgap );
INPUT:
Stoch_Model *smodel stochastic model created by OSL
long minNumRows min number of rows for size of subproblems
long ipcut period at which Nested cuts are made
long maxmod maximum number of subproblems
long maxcycles maximum number of Master iterations
double rmaxmin 1.0 => maximize, -1.0 => minimize
long inwmt EKKNWMT type (0 => none EKKNWMT)
for all problems
long iscal 1=>do, 0=>don't perform scaling for
each submodel
long icrsh crash type (0 => none) for first
first solution of submodels
long ilpdc 1=>call, 0=>don't perform LP decomposition
for each submodel
long iprsl 1=>call, 0=>don't perform presolve for
each submodel
long iprsltype type of presolve to be done
long iprslunit presolve unit
long isalg EKKSSLV algorithm for first solution
of submodels
long largebounds 1=>add, 0=>don't add large bounds to master
long *optgap pointer to Target optimality gap
OUTPUT:
long *rc pointer to return code (code >1 => fatal error)
long *status pointer to status; value = 0=>optimal,
1=>infeasible, 2=>unbounded, 3=>unfinished
long *optgap pointer to relative accuracy of attained
optimality gap
RETURNS:
void
Passes matrix, costs and bounds data to the Optimization Library
model corresponding to smodel.
FUNCTION PROTOTYPE:
void ekks_PassModelToOSL (long *rc, Stoch_Model *smodel );
INPUT:
Stoch_Model *smodel stochastic model declared by OSL
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Sets type of core model. Valid arguments are: linear, quadratic.
FUNCTION PROTOTYPE:
void ekks_ProblemType ( long *rc, Stoch_Data*stoch,
CoreType type );
INPUT:
CoreType type type of core model
Stoch_Data *stochdata pointer to Stoch_Data struct
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Puts the Stoch_Data struct into a named SPL file.
Opens the file as a buffered direct access file, writes
the data and then closes it.
File may be read by a call to ekks_GetStochasticData.
FUNCTION PROTOTYPE:
void ekks_PutStochasticData (long *rc, Stoch *stoch,
char *filename);
INPUT:
Stoch_Data *sdata stochastic data pointer initialized by
ekks_InitializeApplication
char *filename name of SPL file
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Processes the Stochastic MPS files.core, .time and .stoch, creates scenario data and stores it in the StochData structure. The value of replace is set to 0 if STOCH file contains 'ADD' at position 40 in the first line. FUNCTION PROTOTYPE: void ekks_ReadMPS (long *rc, Stoch_Data *stoch, long*smpstype, long *replace, char *corefile, char *timefile, char *stochfile ); INPUT: Stoch_Data *sdata pointer to Stoch_Data structure to be filled in by ekks_ReadMPS char *corefile pointer to the core MPS filename char *timefile pointer to the time MPS filename char *stochfile pointer to the stoch MPS filename OUTPUT: long *rc pointer to return code (2 is fatal) long *smpstype integer identifying type of SMPS distribution long *replace 0=>add to, 1=>replace core values RETURNS: void
Registers by name a function to be called in place of an
Optimization Library user exit subroutine, identified by number.
The correspondence between values of the numerical identifier
and the names of the user exit subroutines is as follows.
1 corresponds to MIP User Exit EKKBRNU
2 corresponds to MIP User Exit EKKCHNU
3 corresponds to MIP User Exit EKKCUTU
4 corresponds to MIP User Exit EKKEVNU
5 corresponds to MIP User Exit EKKHEUU
6 corresponds to Iteration User Exit EKKITRU
7 corresponds to Message User Exit EKKMSGU
8 corresponds to MIP User Exit EKKNODU
9 corresponds to Row Ordering User Exit EKKORDU
10 corresponds to MIP User Exit EKKSLVU
FUNCTION PROTOTYPE:
void ekkse_RegisterCallBack (int *cbid, void *ekkcbptr);
INPUT:
int *cbid pointer to user exit function id number
void *ekkcbptr name of call back function being registered
OUTPUT:
none
RETURNS:
void
Turn Stochastic Extensions messages on/off.
Message msgid (use symbolic names from message table) is
turned off, if onoff is 0, and turned on, if onoff is 1.
FUNCTION PROTOTYPE:
void ekkse_SetMessage (long *rc, long msgid, long onoff);
INPUT:
long msgid Message identifier (from message table)
long onoff 0 turns off printing, 1 turns on printing
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
Solve parametric model. If lambda is non-zero, then lambda times
the perturbation vector is added to the original and the resulting
problem is solved with EKKSSLV. Thereafter, the perturbation is
added in increments multiplied by the value of lambdadelta up
to the maximum value, lambdalim.
It is more efficient to set up the problem so that the original is
solved with ekkse_NestedLSolve, then call
ekkse_SolveParametricModel with lambda=0.
Each time the incremented problem is solved, the function pointed
to by report() is called with the OSL work space attached to smodel
as argument.
The mask argument is used in the same way as in
ekkse_DefineParametricModel
FUNCTION PROTOTYPE:
void ekkse_SolveParametricModel (long *rc, Stoch_Model *smodel,
double lambda, double lambdadelta, double lambdalim,
long mask, long (*report) (double *) );
INPUT:
Stoch_Model *smodel pointer to Stoch_Model
double lambda initial perturbation to be added
double lambdadelta incremental perturbation to be added
double lambdalim maximum perturbation to be added
long mask see ekkse_DefineParametricModel
long (*report) (double *)) called after solution
OUTPUT:
long *rc pointer to return code (2 is fatal)
RETURNS:
void
| EKK0402 | Informational. | Entering Stochastic Solutions function M01. |
|---|---|---|
| EKK0403 | Informational. | Core model has I01 rows, I02 columns, and I03 stages. |
| EKK0404 | Informational. | Scenario I01 Ancestor I02 Stage I03 Probability D01. |
| EKK0405 | Informational. | Declaring stochastic model in OSL. Number of rows I01, number of columns I02. |
| EKK0406 | Informational. | Total number of blocks declared to OSL is I01. |
| EKK0407 | Informational. | Total number of C01 is I01. |
| EKK0408 | Informational. | Constructing stochastic model from original node list. |
| EKK0409 | Informational. | Process time for C01 is D01 seconds. |
| EKK0410 | Informational. | Beginning C01. |
| EKK0411 | Informational. | C01 C02 I01 ... |
| EKK0412 | Informational. | C01 C02 ... |
| EKK0413 | Informational. | C01 D01 ... |
| EKK0414 | Informational. | Beginning first pass of Benders decomposition. |
| EKK0415 | Informational. | Subproblem I01 did not solve. Exiting. |
| EKK0416 | Informational. | Master infeasible. Terminating. |
| EKK0417 | Informational. | Master unbounded. Generating ray. |
| EKK0418 | Informational. | Estimated subproblem value at new master proposal is E0126. |
| EKK0419 | Informational. | Beginning cycle I01. |
| EKK0420 | Informational. | Solving subproblem I01. |
| EKK0421 | Informational. | Unboundedness detected in subproblem I01 in cycle I02. |
| EKK0422 | Informational. | Subproblem actual value at master proposal E0126. |
| EKK0423 | Informational. | Problem is unbounded. Terminating. |
| EKK0424 | Informational. | Optimality gap for current master proposal is E0114. |
| EKK0425 | Informational. | Relative optimality gap is E0114. |
| EKK0426 | Informational. | Optimal solution found to within relative optimality gap E0114. |
| EKK0427 | Informational. | No new cuts from subproblems. Terminating. |
| EKK0428 | Informational. | Maximum cycles exceeded. Terminating. |
| EKK0429 | Informational. | No quadratic terms found in model. Resetting type to linear. |
| EKK0430 | Informational. | Master problem value is E0126. |
| EKK3401 | Warning. | Scenario I01 has already been defined. Probability is changed to D01. |
| EKK3402 | Warning. | Scenarios that branch from the root have branching stage = 2. |
| EKK3403 | Warning. | Scenario I01 branches prior to ancestor's branch stage: true ancestor is I02. |
| EKK3404 | Warning. | Data for current model-block contains elements for earlier stages. |
| EKK3405 | Warning. | SPL file is already opened for this application. No action taken. |
| EKK3406 | Warning. | No filename supplied. Opening temporary SPL file in /tmp. |
| EKK3407 | Warning. | Core C01 value at index I01 is infinite. Nonzero value in scenario I02 ignored. |
| EKK3408 | Warning. | Node list is non-empty. Ignored. |
| EKK3409 | Warning. | I01 zero probability nodes have been removed from model node list. |
| EKK3410 | Warning. | No ENDATA card in C01 file. Ignored. |
| EKK3416 | Warning. | Warning! No scenario C01. |
| EKK3417 | Warning. | Warning! No stage C01. |
| EKK3418 | Warning. | Warning! No column C01. |
| EKK3419 | Warning. | Warning! No row C01. |
| EKK3420 | Warning. | Warning! Ignored LB of Col I01 Scn I02. |
| EKK3421 | Warning. | Warning! Ignored UB of Col I01 Scn I02. |
| EKK3422 | Warning. | Warning! Ignored UB of Row I01 Scn I02. |
| EKK3423 | Warning. | Warning! End of File. |
| EKK7401 | Error. | Malloc failed in subroutine M01. Check maximum memory allocation for user. |
| EKK7402 | Error. | Zero allocation attempted in subroutine M01. Check subroutine arguments. |
| EKK7403 | Error. | C01 structures not initialized or corrupted. This was detected in subroutine M01. |
| EKK7404 | Error. | Sort of C01 failed in subroutine M01. |
| EKK7405 | Error. | Error detected while trying to open SPL file C01 in subroutine M01. |
| EKK7406 | Error. | Error detected while trying to close SPL file C01 in subroutine M01. |
| EKK7407 | Error. | Attempt to reposition within SPL file C01 failed in subroutine M01. |
| EKK7408 | Error. | Error detected in subroutine M01 while writing to SPL file C01. |
| EKK7409 | Error. | Error detected in subroutine M01 while reading from SPL file C01. |
| EKK7410 | Error. | Invalid mode specified in subroutine M01 for opening SPL file C01. |
| EKK7411 | Error. | Invalid mode specified in subroutine M01 for closing SPL file C01. |
| EKK7412 | Error. | Unable to allocate file pointer for SPL file C01 in subroutine M01. |
| EKK7413 | Error. | Unable to allocate filename storage for SPL file C01 in subroutine M01. |
| EKK7414 | Error. | Invalid SPL file pointer specified in subroutine M01. |
| EKK7415 | Error. | Error detected in subroutine M01 while attaching SPL file C01. |
| EKK7416 | Error. | Error detected in subroutine M01 while detaching SPL file C01. |
| EKK7417 | Error. | Invalid virtual record specified in subroutine M01 for SPL file C01. |
| EKK7418 | Error. | Negative virtual record size specified in subroutine M01 for SPL file C01. |
| EKK7419 | Error. | Empty string specified for SPL filename in subroutine M01. |
| EKK7420 | Error. | Existing SPL file C01 opened in subroutine M01 is improperly initialized. |
| EKK7421 | Error. | Error detected in subroutine M01 while deleting SPL file C01. |
| EKK7422 | Error. | File-size discrepancy for SPL file C01 detected in subroutine M01. |
| EKK7423 | Error. | Unknown error code for SPL file access used in subroutine M01. |
| EKK7424 | Error. | Unable to initialize C01 for SPL file C02 in subroutine M01. |
| EKK7425 | Error. | Error detected while attempting to save SPL file with name C01. |
| EKK7426 | Error. | Number of C01 requested, I01 exceeds declared maximum I02. |
| EKK7427 | Error. | Branching stage out of bounds. |
| EKK7428 | Error. | Scenario has negative probability. |
| EKK7429 | Error. | Ancestor scenario I01 does not exist. |
| EKK7430 | Error. | Number of C01 in CORE model I01 does not match number I02 in scenario. |
| EKK7431 | Error. | Data for current model-block is not block lower-triangular. |
| EKK7432 | Error. | Total probability in model is zero. |
| EKK7433 | Error. | Node list is empty. Cannot construct model. |
| EKK7434 | Error. | Error creating hash tables for C01 names. |
| EKK7435 | Error. | Not enough space in dspace for C01 file processing. |
| EKK7436 | Error. | Index error in C01 file. |
| EKK7437 | Error. | Error reading C01 file. |
| EKK7438 | Error. | Distribution type not implemented. |
| EKK7439 | Error. | Premature EOF reached in C01 file. |
| EKK7440 | Error. | Expecting C01 card in C02 file. |
| EKK7441 | Error. | Too many elements in scenario I01. Consider revising CORE file, so that more of these elements appear there. |
| EKK7442 | Error. | Ranges not implemented in SMPS format. |
| EKK7443 | Error. | OSL not initialized or corrupted. This was detected in subroutine M01. |
| EKK7444 | Error. | Not enough space in OSL for matrix. Need at least I01 more doublewords. |
| EKK7445 | Error. | Duplicate root node discovered in model node tree. |
| EKK7446 | Error. | Master status is confused. Exiting. |
| EKK7447 | Error. | Bad return code from OSL solving subproblem I01 in cycle I02. |
Stephen E. Wright (now at Miami University of Ohio) was co-developer of SP/OSL during his postdoc years 1991-3 and during a summer visit in 1994. The elegant SP-file object and the flexible and robust implementation of the parallel decomposition were entirely designed and written by him.
Robert Entriken (now a consultant with PG&E) wrote the first version of SP/OSL, a matrix generator, in early 1990. The important node/arc metaphor basic to SP/OSL data structures is due to him. Hercules Vladimirou (now at University of Cyprus) developed and tested an early parallel implementation of single-cut Benders during his postdoc in 1991-2. Chris Donohue (University of Michigan) developed the prototype tree-generation software during his stint as a summer student in 1992. Shabbir Ahmed (now at the University of Illinois, Urbana Champaign) prepared the section on examples in this documentation. Special acknowledgement also is due to Roger Wets, for inspiration, guidance and support during his frequent visits throughout the development period.
Two significant corporate consulting engagements played a major role in the development of SP/OSL.
In 1990, the Frank Russell Corporation asked IBM Research to assess the solvability of certain stochastic programs generated by an asset/liability management system. In response, Robert Entriken quickly built a matrix generator capable of translating SMPS format to OSL problem structures, and Alan King and Robert Entriken working together solved the problem during several overnight runs on an IBM mainframe computer.
In 1992, the Allstate Corporation's Palo Alto Research Center asked IBM to assist them in the development of a multiperiod asset allocation pilot for their property and casualty portfolio. This relationship spurred major development of SP/OSL both as a model generator and as a decomposition solver.
In the period 1993 to 1997, SP/OSL was distributed under special agreement with principal investigators at selected universities and corporate research centers for field testing.
[ Top of Page | Previous (Users Guide) | Next (Examples) | Roadmap ]