Changeset 1957


Ignore:
Timestamp:
Dec 3, 2009 4:17:35 PM (11 years ago)
Author:
dlwoodr
Message:

Documentation updates for pysp

Location:
coopr.pysp/trunk/doc/pysp
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • coopr.pysp/trunk/doc/pysp/pyspbody.tex

    r1830 r1957  
    1717
    1818The pysp package extends the pyomo modeling language to support multi-stage stochastic programs with
    19 enumerated scenarios. Pyomo and pysp are Python version 2.6 programs. The underlying algorithm in pysp
    20 is based on Progressive Hedging (PH) \cite{RockafellarWets}, which progressively computes {\em weights} corresponding to each variable to force convergence. In order to
     19enumerated scenarios. Pyomo and pysp are Python version 2.6 programs.  In order to
    2120specify a program, the user must provide a reference model and a scenario tree.
    2221
     
    3231\end{verbatim}
    3332but notice that there are two dashes before the word ``help.'' Command line arguments are summarized in Section~\ref{cmdargsec}.
     33
     34The underlying algorithm in pysp
     35is based on Progressive Hedging (PH) \cite{RockafellarWets}, which decomposes the problem into sub-problems, one for
     36each scenario.
     37The algorithm progressively computes {\em weights} corresponding to each variable to force convergence
     38and also makes use of a {\em proximal} term that provides a penalty for the squared deviation from the
     39mean solution from the last PH iteration.
    3440
    3541\subsection{Reference Model}
     
    140146Note that both PH extensions (WW PH and your own) can co-exist; however, the WW plugin will be invoked first.
    141147 
     148\item \verb|--scenario-solver-options| The options are specified just as in pyomo, e.g., \verb|--scenario-solver-options="mip_tolerances_mipgap=0.2"| to set the mipgap for all scenario sub-problem solves to 20\% for the CPLEX solver. The options are specified in a quote deliminted string that is passed to the sub-problem solver.
     149 Whatever options specified are persistent across all solves. 
     150\item \verb|--ef-solver-options| The options are specified just as in pyomo, e.g., \verb|--scenario-solver-options="mip_tolerances_mipgap=0.2"| to set the mipgap for all scenario sub-problem solves to 20\% for the CPLEX solver. The options are specified in a quote deliminted string that is passed to the EF problem solver.
    142151  \item \verb|--write-ef|\\            Upon termination, write the extensive form of the model - accounting for all fixed variables.
    143152  \item \verb|--solve-ef|\\            Following write of the extensive form model, solve it.
     
    146155  \item \verb|--suppress-continuous-variable-output|\\
    147156                        Eliminate PH-related output involving continuous variables. Default: no output.
    148   \item --keep-solver-files\\   Retain temporary input and output files for scenario sub-problem solves.  Default: files not kept.
    149   \item --output-solver-logs\\  Output solver logs during scenario sub-problem solves. Default: no output.
    150   \item --output-ef-solver-log\\
     157  \item \verb|--keep-solver-files|\\   Retain temporary input and output files for scenario sub-problem solves.  Default: files not kept.
     158  \item \verb|--output-solver-logs|\\  Output solver logs during scenario sub-problem solves. Default: no output.
     159  \item \verb|--output-ef-solver-log|\\
    151160                        Output solver log during the extensive form solve. Default: no output.
    152   \item --output-solver-results\\
     161  \item \verb|--output-solver-results|\\
    153162                        Output solutions obtained after each scenario sub-problem solve. Default: no output.
    154   \item --output-times\\        Output timing statistics for various PH components. Default: no output.
     163  \item \verb|--output-times|\\        Output timing statistics for various PH components. Default: no output.
    155164  \item \verb|--disable-warmstarts|\\
    156165                  Disable warm-start of scenario sub-problem solves in PH iterations >= 1.
     
    162171                  Do not linearize PH objective terms involving binary decision variables.
    163172                  Default=False (i.e., the proximal term for binary variables is linearized by default; this can have some impact on the relaxations during the branch and bound solution process).
    164   \item \verb|: --linearize-nonbinary-penalty-terms|\\
    165                   Approximate the PH quadratic term for continuous variables with a piece-wise linear function.
    166                   Default=False.
     173  \item \verb|--linearize-nonbinary-penalty-terms|=BPTS\\
     174                  Approximate the PH quadratic term for non-binary variables with a piece-wise linear function. The argument
     175                  BPTS gives the number of breakpoints in the linear approximation. The default=0. Reasonable non-zero
     176                  values are usually in the range of 3 to 7. Note that if a breakpoint would be very close to a variable
     177                  bound, then the break point is ommited. IMPORTANT: this option requires that all variables have bounds that
     178                  are either established in the reference model or by code specfied using the bounds-cfgfile command line option. See Section~\ref{LinearSec}
     179                  for more information about linearizing the proximal term.
     180  \item \verb|--breakpoint-strategy|=BREAKPOINT\_STRATEGY
     181                        Specify the strategy to distribute breakpoints on the
     182                        [lb, ub] interval of each variable when linearizing. 0
     183                        indicates uniform distribution. 1 indicates
     184                        breakpoints at the node min and max, uniformly in-
     185                        between. 2 indicates more aggressive concentration of
     186                        breakpoints near the observed node min/max.
     187  \item \verb|--bounds-cfgfile|=BOUNDS\_CFGFILE\\
     188                  The argument BOUNDS\_CFGFILE specifies the name of an executable pyomo file that sets bounds. The devault is that there is no file.
     189                  When specified, the code in this file is executed after the initialization of scenario data so the
     190                  bounds can be based on data from all scenarios. The config subdirectory of the farmer example contains a simple example of
     191                  such a file (boundsetter.cfg).
    167192  \item \verb|--checkpoint-interval|\\
    168                   The number of iterations between writing of a checkpoint file. Default is 0, indicating never..
     193                  The number of iterations between writing of a checkpoint file. Default is 0, indicating never.
    169194  \item \verb|--restore-from-checkpoint|\\
    170195                  The name of the checkpoint file from which PH should be initialized. Default is not to restore from a checkpoint.
     
    344369
    345370\begin{verbatim}
    346 pyomo\examples\pysp\farmer
    347 \end{verbatim}
    348 where the directory \verb|pyomo| might be \verb|pyomodist| or something else depending on how you installed pyomo and pysp.
    349 
    350 The data is in a subdirectory called SCENARIODATA.
    351 
    352 To
     371coopr\examples\pysp\farmer
     372\end{verbatim}
     373
     374The data is in a subdirectory called scenariodata and the model is in the models subdirectory. To
    353375invoke PH for this problem, connect to this farmer directory and use the command:
    354376
     
    379401
    380402\begin{verbatim}
    381 pyomo\packages\coopr\examples\pysp\sizes
    382 \end{verbatim}
    383 where the directory \verb|pyomo| might be \verb|pyomodist| or something else depending on how you installed pyomo and pysp.
     403coopr\packages\coopr\examples\pysp\sizes
     404\end{verbatim}
    384405
    385406The data for a three scenario version is in a subdirectory called SIZES3 and a ten scenario
     
    415436
    416437\begin{verbatim}
    417 pyomo\packages\coopr\examples\pysp\forestry
    418 \end{verbatim}
    419 where the directory \verb|pyomo| might be \verb|pyomodist| or something else depending on how you installed pyomo and pysp.
     438coopr\packages\coopr\examples\pysp\forestry
     439\end{verbatim}
     440
    420441
    421442There are two families of instances: ``Chile'' and ``Davis,'' each with four stages and eighteen scenarios. This is also a small
     
    10101031To run this example, connect to the sizes directory, which is something like:
    10111032\begin{verbatim}
    1012 pyomo\packages\coopr\examples\pysp\sizes
    1013 \end{verbatim}
    1014 where the directory \verb|pyomo| might be \verb|pyomodist| or something else depending on how you installed pyomo and pysp.
     1033coopr\examples\pysp\sizes
     1034\end{verbatim}
    10151035
    10161036Then use
     
    10251045time. It is provided to illustrate the features of the extensions, not to illustrate why you might need them. Much larger instances are are required for that.
    10261046
     1047\section{Linearizing the Proximal Term \label{LinearSec}}
     1048
     1049\subsection{Introduction}
     1050
     1051For a decision variable $x$ the proximal term added to the objective function for each scenario subproblem at PH iteration $k$ is
     1052$$
     1053\left(x - \bar{x}^{(k-1)}\right)^{2}
     1054$$
     1055where $\bar{x}^{(k-1)}$ is the average over the scenarios from the last iteration. Expanding the square reveals that the only
     1056quadratic term is $x^{2}$. For binary variables, this is equal to $x$, although this is not the case when a relaxation is solved.
     1057For binary variables, the default behaviour is to replace the quadratic term with $x$, but an option allows the quadratic to be
     1058retained because this can effect the subproblem solution time due to the use of the quadratic term when the relaxations are solved
     1059as part of the branch and bound process.
     1060
     1061For non-binary variables an option exists to replace the $x^2$ term with a piece-wise approximation and the number of breakpoints in the
     1062approximation is under user control. This can have a significant effect on CPU time required to solve sub-problems because the presence of
     1063the quadratic term increases the solution times significantly. However, linearization results in a time-quality tradeoff because increasing
     1064the number of breakpoints increases the fidelity but each breakpoint introduces another (unseen) binary variable so solution times are generally
     1065increased.
     1066
     1067A few strategies for placing the breakpoints are supported as command a line options:
     1068\verb|--breakpoint-strategy|=BREAKPOINT\_STRATEGY. A value of 0
     1069indicates uniform distribution. 1 indicates
     1070breakpoints at the min and max for the node in the scenario tree, uniformly in-
     1071between. A value of 2 indicates more aggressive concentration of
     1072breakpoints near the observed node min/max.
     1073
     1074Upper and lower bounds for variables must be specified when the linearization option is chosen. This can be done by specifying bounds in the
     1075reference model or by using the bounds-cfgfile command line option. It is, of course, best to use meaningful bounds provided
     1076in the reference model; however, the modeller must be careful not use estimated bounds that are too tight since that could preclude
     1077an optimal (or even a feasible) solution to the overall stochastic problem even though it might not cut off any optimal solutions for the
     1078particular scenario. The use of a bounds cfgfile is an advanced topic, but enables the modeller to use bounds that cannot create
     1079infeasibilities.
     1080
     1081\subsection{Bounds-cfgfile}
     1082
     1083Using a bounds cfgfile is an advanced topic. The modeler is writing python/pyomo code that will be executed by the
     1084ph.py file that is the core of the PH algorithm. The first executable line in a bounds file is typically:
     1085
     1086\begin{verbatim}
     1087model_instance = self._model_instance
     1088\end{verbatim}
     1089
     1090This establishes a local variable called ``model\_instance'' that can be used to refer to the model (of course, a different name can be
     1091used, such as MODINS). The object ``self'' on the right hand side of this assignment refers to the core PH object. The model, in turn contains the parameters and
     1092variables defined in the ReferenceModel.py file that can be accessed by name. For example, with the Farmer model, the cfg file
     1093sets the uppter bound on DevotedAcreage to be value of the paramter TOTAL\_ACREAGE at intialization (since this is Python, the
     1094parentheses after TOTAL\_ACREAGE cause the value in TOTAL\_ACREAGE to be assigned rather than the name of the parameter object:
     1095
     1096\begin{verbatim}
     1097# only need to set upper bounds on first-stage variables, i.e., those being blended.
     1098
     1099model_instance = self._model_instance
     1100
     1101# the values supplied to the method
     1102upper_bound = float(model_instance.TOTAL_ACREAGE())
     1103
     1104for index in model_instance.CROPS:
     1105   # the lower and upper bounds are expected to be floats, and trigger an exception if not.
     1106   self.setVariableBoundsAllScenarios("DevotedAcreage", index, 0.0, upper_bound)
     1107\end{verbatim}
     1108
     1109The same thing could be accomplished by setting the upper bound in the model file, but it does serve as a simple example of a bounds cfg file.
     1110
     1111%\subsection{Sizes Example}
     1112
     1113
    10271114\section{Solving sub-problems in Parallel \label{parallelsec}}
    10281115
     
    10331120Here are the commands in order:
    10341121\begin{enumerate}
    1035 \item On the master: \verb|pyro-ns|
     1122\item On the master: \verb|coopr-ns|
    10361123\item On the master: \verb|dispatch_srvr|
    10371124\item On each slave: \verb|pyro_mip_server|
    10381125\item On the master: \verb|runph ... --solver-manager=pyro ...|
    10391126\end{enumerate}
    1040 Note that the command \verb|pryo-ns| and the argument \verb|solver-manger| have a dash in the middle, while
     1127Note that the command \verb|coopr-ns| and the argument \verb|solver-manger| have a dash in the middle, while
    10411128the commands \verb|dispatch_srvr| and \verb|pyro_mip_server| have underscores. The first three commands launch processes
    10421129that have no internal mechanism for termination; i.e., they will be terminated only if they crash or if they are
    1043 killed by an external process. It is common to launch these processes with output redirection, such as \verb|pyro-ns >& pyrons.log|. The
     1130killed by an external process. It is common to launch these processes with output redirection, such as \verb|coopr-ns >& cooprns.log|. The
    10441131\verb|runph| command is a normal runph command with the usual arguments with the additional specification that subproblem solves should
    10451132be directed to the pyro solver manager.
Note: See TracChangeset for help on using the changeset viewer.