MSLiP (Multistage Stochastic Linear Programming)


MSLiP is a research implementation of nested Benders decomposition  
to solve the multistage stochastic linear program


     minimize z = c x  + E  (min c x  + ... + E  (min c x )...)     (1)
                   1 1    2       2 2          T       T T
                                               

     subject to   A x                                            = b
                   1 1                                              1
 
                  B x  + A x                                     = b
                   2 1    2 2                                       2 
                                .                                .
                                      .                          .
                                            .                    . 

                                                   B x    + A x  = b  
                                                    T T-1    T T    T

                        l  <= x  <= u , t=1,...,T  
                         t     t     t              

 
where all the problem data with subscripts t > 1 are allowed to be random


variables with known, finite distributions and E  denotes mathematical
                                                t 

expectation with respect to the random vector w  = (A , B , b , c , l , u ).   
                                               t     t   t   t   t   t   t 



      The algorithm is based on the observation that, given a 
 
              j
 realization w  of the random vector in period t and given a solution
              t
  a(j)
 x     of the ancestor problem from period t-1, the decision problem 
  t-1

can be written in the form


                j j    j    j
   minimize    c x  + Q   (x )                               (2)
                t t    t+1  t

                j j                 j    j  a(j)
   subject to  A x               = b  - B x
                t t                 t    t t-1

                k,j j               k,j           j
               D   x            >= d   ,  k=1,...r 
                t   t               t             t

       j                                           j
where Q   (.) is a convex function and the number r  of additional 
       t+1                                         t

constraints is at most equal to the number m    of the rows in stage t+1. 
                                            t+1
 


     This problem can be solved using a 'relaxed master problem', viz:

                j j    j
   minimize    c x  + v                                    (3.0)
                t t    t

                j j                   j    j a(j)
   subject to  A x                 = w  - B x              (3.1)
                t t                   t    t t-1

                k,j j                 k,j            j
               D   x              >= d   ,  k=1,...,r      (3.2)
                t   t                 t              t
 
                k,j j    j            k,j            j
               E   x  + v         >= e   ,  k=1,...,s      (3.3) 
                t   t    t            t              t

                         j     j     j
                        l  <= x  <= u
                         t     t     t

                                 _j  _j       _j    j   _j
Problem (3) is solved to obtain (x , v ).  If v  < Q   (x ),
                                  t   t        t    t+1  t 

then another 'optimality cut' (3.3) is added to (3) and (3) is re-solved. 

   _j
If x  forces infeasibility in any future period, then a 'feasibility cut'
    t
                                                      _j     j   _j
(3.2) is added to (3). This process is repeated until v  >= Q   (x ).
                                                       t     t+1  t

Information passing

There is one such problem for each node in the decision tree. Starting from the root problem at stage 1, all problems in the decision tree are examined in sequence and solved either to optimality or until they have been detected infeasible. Information is passed along the decision tree in two ways: dual information is passed back up the tree to generate new cuts (3.2) and (3.3), primal information is passed down the tree to modify the right hand sides. If a particular problem (3) has been found feasible, it is an arbitrary decision in which direction to move. The algorithm always solves all the problems at one stage before deciding whether primal information or dual information is to be created.

Sequencing protocols

Three different sequencing options are available, which are governed by a user-defined switch. Forward first sequencing will create primal information as long as possible and generate cuts only when the primal decision variables do not change anymore. This has also been termed the cautious strategy and amounts to solving each subtree to full optimality before moving back up the tree. Backward first sequencing generates dual information whenever possible. This is an optimistic strategy which attempts to minimize the number of problem that have to be solved at the next stage, since the number of nodes cannot decrease from one stage to the next. The fast forward-fast back method alternates the two methods, moving in one direction (forward or backward) for as long as possible, and reversing direction only when no further progress can be made in the current direction.

Bunching

In the absence of cuts (3.2) and (3.3), many problems at stage t have the same constraint matrix (it is rare to see stochastic A-matrices in practice), implying that the bases and therefore the inverses are the same. The program takes advantage of this fact by considering all these problems simultaneously. The technique used has been termed 'tamping' in the literature and is a variant of the 'trickling' method described in Wets (1983).

Multicuts

The usual procedure places one cut (3.2) or (3.3) at each iteration, aggregating all the information of a node's successors into a single constraint. When the B-matrices are stochastic or when many feasibility cuts must be generated, this is not necessarily very efficient. In these cases it may be better to generate one cut from each of the subproblems, a technique called the 'multicut' method by Birge and Louveaux. This method is available at the user's request.

Input format

The program reads data and data-related information in modified MPS-format, following the standard described in Birge et al.(1987). This requires three input files, commonly referred to as the core file, which fixes non-zero patterns and all deterministic problem data, the time file, which partitions the rows and columns into stages, and the stoch file, which specifies the distributions of the random parameters.

Dual pivots

When a problem is revisited after a cut has been placed in it, the previously optimal solution will still satisfy all but the last constraint and will in particular still be dual feasible. It is therefore possible to use this basis as the starting basis for the dual simplex method. On small problems significant savings in time and number of iterations can be achieved with this option.

Many other options are described in the User's Guide.

References

J.R. Birge, M.A.H. Dempster, H.I. Gassmann, E.A. Gunn, A.J. King and S.W. Wallace, ``A standard input format for multistage stochastic linear programs'', COAL Newsletter #17 (1987), pp.1--19.

J.R. Birge and F.V. Louveaux, ``A multicut algorithm for two-stage stochastic linear programs'', European Journal of Operational Research 34 (1988) 384--392

H.I. Gassmann, ``MSLiP: A computer code for the multistage stochastic linear programming problem'', Mathematical Programming 47 (1990) 407--423.

R.J-B Wets,``Stochastic programming: solution techniques and approximation schemes'', in: Mathematical Programming: The State Of The Art, Bachem, Grotschel and Korte(eds.), Springer Lecture Notes, 1983.

Availability

The code is available to universities and academic institutions for reseach and teaching purposes.

For further information send email to Horand.Gassmann@dal.ca.

A version of the code is also running at the Optimization Technology Center, a joint enterprise of Argonne National Laboratories and Northwestern University. You can submit your own problem and receive the solution through your net browser or via electronic mail.