Proposed New AMPL Features Draft of August 27, 1996

Stochastic Programming Extensions

The features proposed here are designed to support the use of AMPL for common kinds of stochastic programming (or robust optimization) models, which are becoming increasingly popular for planning under uncertainty.

We begin by proposing a statement for defining different data scenarios associated with the same model. Scenarios can be defined without reference to stochastic programming, and are likely to be of general interest to AMPL users. A scenario can be specified by reading modifications to a parent scenario from external files, or by computing modifications using AMPL statements.

A second extension introduces a statement for defining a stochastic framework for a model and its scenarios. Given this framework, AMPL can combine all of the scenarios into a single stochastic program with recourse that can be sent to solvers in various forms. By default the objective of the stochastic program is the expected value of the objective of the underlying model, but an option is provided for specifying an alternative objective such as one incorporating a variance term.

These proposals emphasize recourse problems based on explicitly specified scenarios. A concluding section sketches a number of alternatives that would require different extensions to AMPL.


Scenarios

A scenario is a collection of data for a model. By declaring and maintaining multiple scenarios, a user of AMPL can keep track of multiple model instances and can compare their solutions. Scenarios thus have much the same relationship to data as named problems have to models.

AMPL's stochastic programming features provide a convenient way of finding solutions that are robust over a tree of scenarios, as described in subsequent sections. The scenario feature is intended to also be useful independently of stochastic programming, however.

Users define and switch among scenarios by means of a scenario statement that is analogous to the current problem statement. We explain first how this statement is used, and then how data values in the resulting scenarios are specified and referenced. Additional subsections describe the interaction of scenarios with solve and other AMPL commands, and propose a few extensions.

Defining scenarios. At the start of a session (or after reset) there is a single, current scenario named Root. A command of the form 

   scenario scen-name;
giving any name not previously defined, creates a new scenario and makes it current. It initially inherits all of the previously current scenario's data (including "undefined" for sets and parameters not yet given values in the previously current scenario). Further changes to the data -- from either data or let statements -- affect only the new current scenario, however, while leaving the previously current scenario unchanged.

The same command with optional indexing, 

   scenario scen-name {indexing};
defines an indexed collection of scenarios, all inheriting the data of the current scenario. The identity of the current scenario is left unchanged, however (since in general several new scenarios are defined, and there is no compelling reason to make any one of them current).

Making an existing scenario current. A statement of the form 

   scenario scen-ref;
where scen-ref refers to any previously defined scenario, makes the indicated scenario current and causes the data to have the values associated with that scenario (including "undefined" for sets and parameters not yet given a value in that scenario). A scen-ref is either scen-name for some previously-defined single scenario, or scen-name[object-expr] from some previously defined indexed collection of scenarios.

Referencing data of a particular scenario. Any reference to a model component's value is assumed to refer to its value in the current scenario, unless another scenario is specified by appending @scen-ref. Thus avail@LOW, avail@MIX, avail@SUPPLY[3] give values of the parameter avail in three different scenarios. Subscripts to a component go before the @ operator, as in rate["bands"]@LOW or rate["bands"]@SUPPLY[3] (the latter being the value of parameter rate["bands"] in scenario SUPPLY[3]).

Scenarios can also be denoted by generic scenario names, which are analogous to the generic synonyms for sets, parameters, and variables: 

   _nscens                 number of scenarios defined
   _scenname {1.._nscens}  names of scenarios
   _scen {1.._nscens}      synonyms for scenarios
References to data can use these names, so that for example avail@_scen[5] is the value of parameter avail in the 5th scenario on AMPL's list. The default scenario Root is always _scen[0].

Entering data for a scenario. All data values entered by any means become part of the current scenario, but do not change the values in any other scenario. Data may be entered by either set and param data statements, or let commands.

A scenario statement in data mode makes all sets and parameters updatable, so that any inherited value may be modified once by a subsequent data statement. Thus a single data file can concisely specify a series of arbitrary scenarios: 

   param T := 4;

   param: PROD:  rate  inv0  prodcost  invcost :=
          bands   200   10      10       2.5
          coils   140    0      11       3.0 ;

   scenario TOP;
      param avail :=  1 40  2 40  3 32  4 40 ;

   scenario LOW;
      param avail :=  1 40  2 40  3 32  4 32 ;

   scenario MIX;
      param avail :=  1 40  2 36  3 36  4 40 ;
Alternatively, an indexed collection of scenarios can be defined and then given data individually: 
   scenario SUPPLY {1..3};

   scenario SUPPLY[1];
      param avail :=  1 40  2 40  3 32  4 40 ;

   scenario SUPPLY[2];
      param avail :=  1 40  2 40  3 32  4 32 ;

   scenario SUPPLY[3];
      param avail :=  1 40  2 36  3 36  4 40 ;
If these scenario statements were typed in model mode, then an update data avail command would have to be issued before each param avail statement except the first.

Alternatively, a let statement can be used to define data systematically over an indexed collection of scenarios. For example, given the following declarations in the model, 

   param T > 0;
   param avail {1..T} >= 0;
and the following data, 
   param T := 4;
   param avail :=  1 40  2 40  3 32  4 40 ;
an arithmetic progression of parameter values for a sequence of scenarios can be defined by the following AMPL command script: 
   model steelTS.mod;
   data steelTS.dat;

   param N := 7;
   param av_step := 0.25;

   scenario SUPPLY {1..N};

   let {t in 1..T, k in 1..N} 
      avail[t]@SUPPLY[k] := avail[t]@Root + k * av_step;
A random sample of values can also be assigned, by using AMPL's random functions in a let statement: 
   param N := 7;
   param av_range := 4.0;
   param av_var := 0.35;

   scenario SUPPLY {1..N};

   let {k in 1..N} 
      avail[1]@SUPPLY[k] 
         := Uniform (avail[1]@Root, avail[1]@Root+av_range);

   let {t in 2..T, k in 1..N} 
      avail[t]@SUPPLY[k] := Normal (avail[t-1]@SUPPLY[k], av_var);
This example exhibits two kinds of random data generation. In each scenario, the value of avail[1] is chosen from a random distribution related to the base data, after which avail[2], . . . , avail[T] are determined by a random process starting from avail[1].

Any sets and parameters of a model can vary from one scenario to the next, and a model's structure can depend on these sets and parameters in any way. Thus no special features are needed to allow structural differences between scenarios such as plants opened or closed and products introduced or discontinued.

Solving a scenario. A solve (or write) command sends the solver a problem instance generated from the current scenario. Values subsequently returned by the solver become part of the scenario, and are accessed using the @ operator in the same way as for sets and parameters. As an example, the following script solves each scenario in an indexed collection, then displays a table of the optimal values: 

   for {k in 1..N} {
      scenario SUPPLY[k];
      solve;
   }

   display {k in 1..N} Total_Profit@SUPPLY[k];
When scenarios have arbitrary names (LOW, MIX, and so forth), a concise script of this sort can still be written using the generic scenario names: 
   for {k in 1.._nscens} {
      scenario _scen[k];
      solve;
   }

   display {k in 1.._nscens} (_scenname[k], Total_Profit@_scen[k]);
Wherever a refernce to a model component's value may appear, the reference followed by @scen-ref may also be used. Thus data from multiple scenarios can participate in arithmetic and comparisons. The @ always follows all other qualifiers on a name, so that for example the reduced cost of the variable for inventory of product p in time t, in the solution for scenario LOW, would be written Sell[p,t].rc@LOW.

Options. The complete form of the scenario command has two additional options that may be used when defining scenarios.

A phrase of the form parent scen-ref indicates that the new scenario should take its data from the previously defined scenario indicated by scen-ref, rather than from the current scenario.

A phrase of the form weight const-arith-expr associates a nonnegative numerical value with a scenario. This value can be used automatically by the stochastic framework (as explained below) in forming a joint objective function.

Related features. The addition of scenarios does not affect most existing language features. Some commands such as show and purge may be extended to apply to scenarios, but without any change to their existing behavior on other kinds of model components.

AMPL currently provides a way to save the results of solving a problem instance, by use of the write and solution commands, but this procedure is likely to become unacceptably cumbersome when there are more than a few scenarios. Thus it will be desirable to have a new facility to save (and later restore) the entire current state of an AMPL session, including all currently defined scenarios. Since the resulting save file could be tens of megabytes for even a medium-sized application with a dozen scenarios, there should be options to keep it compact through compression and through omission of information (such as computed parameter values) that is readily reconstructed.


Recourse problems

Since stochastic programs with recourse (or, strictly speaking, their deterministic equivalents) are an important kind of optimization problem, we would like to make them easier to state and solve using AMPL. Rather than extend the modeling language's declarations for this purpose, we propose to let a stochastic programming problem be built from a few more manageable pieces: We focus on the situation in which the user specifies each scenario explicitly, using the tools described in the preceding section. A subsequent section remarks in a more general way on other possibilities, including the specification of scenarios implicitly by means of probability distributions on parameters.

Much of the information that defines a stochastic program is inherent in the definitions of the scenarios and in the corresponding problem instances. The few remaining aspects of the stochastic framework can be declared in a single statement. We first consider the required part of the statement, which identifies the stages. Then we consider options for listing the scenarios and weights explicitly, and for declaring objective functions. We conclude with some notes on the interaction of the stochastic framework with the solver.

Stages. At a minimum, given a model and a collection of scenarios, the definition of a stochastic program requires the identification of a set of ``times" and its partition into stages. A new declaration to provide this information consists (in its simplest form) of the keyword stochastic and a list of stages in the form of sets of numbers or objects that (usually) represent time periods. If the periods are numbered, then stages may be given in any of several ways as shown by the following examples:

Stages may also be given by sets of objects that come from an ordered set in the model, either explicitly or indexed: The listed sets must be disjoint, and their union should be the set of all time periods. They induce a partitioning of the each scenario's problem instance into periods, and this partitioning in turn induces a tree structure on the collection of defined scenarios: Thus for example if 2 were in the time set, then cap[2], cap["SFO",2], cap[2,"SFO"], cap["SFO",2,3] or cap["SFO",3,2] would be associated with the stage containing 2. If a scenario were defined by changing only cap[3,"SFO"], cap[4,"SFO"], . . . from their values in the scenario's parent, then it would branch from its parent after the stage containing 2.

Scenarios. By default, a stochastic program uses all scenarios currently defined. To provide greater flexibility, the scenarios to be used may instead be listed explicitly in the stochastic statement. The list of stages is followed by a colon, the keyword scenarios, and a comma-separated list with optional indexing as in other AMPL statements: 

   stochastic {0,1} {2} {3}: scenarios TOP, LOW, MIX;
   stochastic 0..1, 2..T: scenarios {k in 1..N} SUPPLY[k];
A weight for each scenario is optionally given after its entry in the list: 
   stochastic {0,1} {2} {3}: scenarios TOP .55, LOW .15, MIX .30;

   param wt {1..N};
   stochastic 0..1, 2..T: scenarios {k in 1..N} SUPPLY[k] wt[k];
(Handling of the default scenario Root remains to be resolved.)

The stochastic statement could be further generalized to give a name to the specified collection of scenarios. Using these names, it would be easier to switch among different stochastic frameworks (much as one switches between different named problems using the problem statement).

Objectives. The standard expected-value objective function for stochastic programs is given by the summing the objective functions for the individual scenarios times the weights of the scenarios. It is desirable to be able to specify an alternative objective in the stochastic statement, however. To make this possible, we could adopt the following conventions that are consistent with the current AMPL design:

Thus if the model's objective function is 
   maximize Total_Profit:
      sum {p in PROD, t in 1..T} (revenue[p,t]*Sell[p,t] -
         prodcost[p]*Make[p,t] - invcost[p]*Inv[p,t]);
and if only revenue varies from one scenario to the next, then the expected-value objective could be written as one of the following, 
     _weight@TOP *
       sum {p in PROD, t in 1..T} (revenue[p,t]@TOP*Sell[p,t]@TOP -
         prodcost[p]*Make[p,t]@TOP - invcost[p]*Inv[p,t]@TOP)
   + _weight@LOW *
       sum {p in PROD, t in 1..T} (revenue[p,t]@LOW*Sell[p,t]@LOW -
         prodcost[p]*Make[p,t]@LOW - invcost[p]*Inv[p,t]@LOW)
   + _weight@MIX *
       sum {p in PROD, t in 1..T} (revenue[p,t]@MIX*Sell[p,t]@MIX -
         prodcost[p]*Make[p,t]@MIX - invcost[p]*Inv[p,t]@MIX)

   sum {k in 1..N} _weight@SUPPLY[k] *
     sum {p in PROD, t in 1..T} (
       revenue[p,t]@SUPPLY[k] * Sell[p,t]@SUPPLY[k] -
       prodcost[p] * Make[p,t]@SUPPLY[k] - 
       invcost[p] * Inv[p,t]@SUPPLY[k] )
but would preferably be written much more concisely, as one of: 
   _weight@TOP * Total_Profit@TOP +
   _weight@LOW * Total_Profit@LOW +
   _weight@MIX * Total_Profit@MIX

   sum {k in 1..N} _weight@SUPPLY[k] * Total_Profit@SUPPLY[k]
Alternatively, using the generic scenario names defined above, the expected-value objective can be written for any combination of scenarios as: 
   sum {k in 1.._nscens} _weight@_scen[k] * Total_Profit@_scen[k]
Other possibilities for the objective can be straightforwardly expressed with the same terminology. Using the generic names for illustration, the objective with weights normalized to sum to 1 (like probabilities) is 
   (1 / sum {k in 1.._nscens} _weight@_scen[k])
      * sum {k in 1.._nscens} _weight@_scen[k] * Total_Profit@_scen[k]
Given an additional nonnegative parameter var_pen_wt, a penalty term for variance can be added like this: 
   sum {k in 1.._nscens} _weight@_scen[k] * Total_Profit@_scen[k] 

      - var_pen_wt * 

   sum {k in 1.._nscens} _weight@_scen[k] * 
      (Total_Profit@_scen[k] - 
         sum {kk in 1.._nscens} 
            _weight@_scen[kk] * Total_Profit@_scen[kk]) ^ 2
In both of these cases, the objective cannot be expressed in the underlying model because it contains a subexpression summing over all scenarios. In contrast, penalty terms for violating the constraints -- so-called soft constraints for robust optimization -- could be incorporated directly into the model's objective, because the penalty for one scenario can be expressed without reference to any of the other scenarios.

Any of these alternative objectives would be expressed as an option to the stochastic statement, following the keyword minimize or maximize: 

   stochastic 0..1, 2..T: scenarios {k in 1..N} SUPPLY[k] wt[k],
      maximize 
         (sum {k in 1..N} _weight@SUPPLY[k] * Total_Profit@SUPPLY[k])
            / sum {k in 1..N} _weight@SUPPLY[k];
This could be generalized by allowing multiple, named objectives to be defined, though the statement would then potentially become very long.

As an alternative to incorporating lengthy objective expressions, additional terminology could be introduced for more of the common cases, such as normalized weights and variances. These would have the advantage of applying automatically to whichever objective happened to be current.

Solving a stochastic program. When a solve is issued after a stochastic framework has been set up by a stochastic statement, problem instances for all of the scenarios are generated and sent to the solver. Information about the stochastic framework is also sent to the solver, in any of several forms:

The first of these is most general, and would be preferred for use by a solver that is specialized to stochastic programs. The second is likely to be preferred for general-purpose interior-point solvers, and the third for general-purpose simplex solvers.

When a solution is returned, a part of it is stored with each scenario. Only those values in a scenario that are different from the corresponding values in its parent need be stored explicitly. Solution values in a particular scenario are distinguished by use of the @ operator, in the same way as for data values.


Other formulations

The features described above permit scenarios to be determined outside of AMPL and read as data, or to be computed by AMPL expressions. Although this is the most appropriate form of extension for many stochastic programming applications, a more implicit specification of the scenarios might be a valuable option in some cases.

Most obviously, AMPL's random functions -- such as Normal and Uniform -- could be used to assign probabilistic distributions rather than explicit values to parameters. These "random parameters" would be declared with the keyword random, to distinguish them from ordinary parameters that are meant to be assigned one particular random value. Random parameters could be independent, 

   param avail_mean >= 0;
   param avail_var >= 0;

   param avail {1..T} random := Normal (avail_mean, avail_var);
or dependent as in this example of a random process: 
   param mktbas {PROD} >= 0;
   param grow_min {PROD} >= 0;
   param grow_max {PROD} >= 0;

   param market {p in PROD, t in 1..T} random :=
      if t = 1 then mktbas[p] 
      else market[p,t-1] + Uniform (grow_min[p], grow_max[p]);
A feature could be added to AMPL to generate a specified number of random scenarios from this model; this would only be a shortcut, however, for the explicit generation of random scenarios (as illustrated in the preceding discussion of the scenario statement).

A more ambitious approach would send the random expressions to the solver, in the expression-tree format that is already used for objectives and constraints in nonlinear models. The solver could then use its own strategy of sampling. It could adaptively choose the number of samples, or could employ techniques such as importance sampling to get more significant results from a given number of samples.

Discrete distributions are a separate case. The user might be allowed to specify several alternative values for certain parameters, with associated probabilities, after which AMPL would automatically generate all of the resulting (finite number of) scenarios. An extension to the AMPL data statements would be necessary to permit selected data values to be replaced by discrete distributions.

Finally, we could consider the introduction of chance constraints, which specify lower limits on the probabilities of satisfying certain inequalities. A chance constraint must involve both variables and random parameters, but it is significantly different in form from the constraints in recourse problems. Chance-constrained problems are thus likely to require a different and largely independent collection of AMPL extensions.


Comments or questions?
Write to info@ampl.com or use our comment form.

Return to the AMPL proposed new features page.

Return to the AMPL update page.

Return to the AMPL home page.

LAST MODIFIED 27 AUGUST 1996 BY 4er.