DECIS™

Problems Solved

DECIS™ solves a well-studied class of problems called two-stage stochastic programs with recourse. In such problems, a decision is to be made in a first stage for which all parameters are known with certainty. That decision establishes initial conditions for a collection of second-stage problems, one for each possible combination of all random parameters. In the case of complete recourse, the problem for each second-stage outcome, under any set of initial conditions, is known to have a feasible solution (that is, one that satisfies all stated constraints). In the case of partial recourse, it is possible that certain initial conditions may lead to a second-stage problem with constraints that cannot be satisfied. Unlike some other stochastic programming systems, DECIS™ handles both of these cases. In either case, the object of the optimization is to minimize the expected cost of the decisions (in both stages) subject to feasibility in the first stage and for all second-stage outcomes.

For some decision problems with more than two stages, it is a reasonable approach to combine the second and later stages in such a way as to define an expanded (possibly approximate) second-stage problem, thus allowing for solution of the multi-stage problem as a two-stage problem.

DECIS™ Solution Algorithms

The real power of DECIS™ lies in its collection of available solution algorithms. Each is based on a core algorithm called Benders Decomposition. This method operates by alternately solving separate problems for the first and second stages, communicating the cost and feasibility status of the second-stage problems by means of special constraints added to the first-stage problem.

For a case in which the total number of second-stage outcomes is not too large (given the size of the problem for any given outcome), it is possible to enumerate and solve all second-stage problems in the course of the Benders algorithm. Such an expansion is called a deterministic equivalent or universe problem. This problem is solved exactly by the decomposition.

In the more difficult case of too many second-stage outcomes, one must be content with an approximate solution to the overall problem. Here DECIS™ algorithms calculate a solution and report a confidence interval that contains the true (but unknown) optimal solution. The basic technique utilizes Monte Carlo sampling to randomly select for solution a subset of the full universe of second-stage outcomes. Larger sample sizes lead to tighter confidence intervals but also to longer computation times.

DECIS™ implements two possible variants of Monte Carlo sampling. In the first, called pre-sampling, a sample of second-stage outcomes is chosen once and for all. Then the resulting collection is composed into a problem that is solved as though it were a deterministic equivalent problem. In the second variant, samples are taken on the fly in the course of the Benders iterations, and the sample is not the same from iteration to iteration. Naturally, this tends to provide better coverage of the universe of possible outcomes.

In the context of sampling on the fly, DECIS™ provides three variations. The first is standard Monte Carlo. The second, called importance sampling, uses modified probability distributions tilted toward more important outcomes, as determined by a specified importance measure. The third, called control variates, constructs and uses an easily computed function that approximates the expected cost function in order to advantageously modify the constraints passed from the second stage to the first stage. Both importance sampling and control variates serve to reduce the variance that determines the width of the confidence interval around the true optimal objective value.

Employing DECIS™

There are three distinct alternatives for employing DECIS™.

• The easiest way to utilize DECIS™ is to select it as the solver in the modeling system of IIT partner GAMS Development Corporation [external link to www.gams.com]. At the core of the GAMS system is a modeling language for stating an optimization problem in a symbolic, algebraic form. Supporting statements provide for performing auxiliary calculations in data setup and for results reporting, building formatted reports, and interchanging data with spreadsheet and database applications. With DECIS™ selected as the solver, GAMS performs the transformations and expansions necessary for communicating the problem to DECIS™, dispatches the selected DECIS™ algorithm, and then retrieves the solution from DECIS™ for use in report writing. In short, the GAMS/DECIS™ combination is a uniquely powerful platform for solving otherwise intractable stochastic problems.

GAMS/DECIS™ documentation.

• A programmatic interface (API) is available for calling DECIS™ functions directly from an outer program written in C or FORTRAN. API functions provide for loading the problem into DECIS™ (in memory), setting solution parameters, solving the problem, and retrieving results (in memory). Alternatively, functions can be called to load the problem and report the results via text files. Either way, this can be the most efficient mode of employing DECIS™ and has the advantage of using DECIS™ seamlessly in the context of a parent application.

DECIS™ User’s Guide (pdf)

• A standalone DECIS™ executable is available that (via the API) loads the problem and reports the results via text files. Relevant control parameters are specified via a small text file and some operating system environment variables. The input data for the problem is stated in a standard format for stochastic programs called SMPS, for Stochastic Mathematical Programming System. This format is described in the DECIS™ User’s Guide and also at this site.