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 ]