# Changeset 1957

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

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

### Legend:

Unmodified
 r1830 The pysp package extends the pyomo modeling language to support multi-stage stochastic programs with enumerated scenarios. Pyomo and pysp are Python version 2.6 programs. The underlying algorithm in pysp is based on Progressive Hedging (PH) \cite{RockafellarWets}, which progressively computes {\em weights} corresponding to each variable to force convergence. In order to enumerated scenarios. Pyomo and pysp are Python version 2.6 programs.  In order to specify a program, the user must provide a reference model and a scenario tree. \end{verbatim} but notice that there are two dashes before the word help.'' Command line arguments are summarized in Section~\ref{cmdargsec}. The underlying algorithm in pysp is based on Progressive Hedging (PH) \cite{RockafellarWets}, which decomposes the problem into sub-problems, one for each scenario. The algorithm progressively computes {\em weights} corresponding to each variable to force convergence and also makes use of a {\em proximal} term that provides a penalty for the squared deviation from the mean solution from the last PH iteration. \subsection{Reference Model} Note that both PH extensions (WW PH and your own) can co-exist; however, the WW plugin will be invoked first. \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. Whatever options specified are persistent across all solves. \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. \item \verb|--write-ef|\\            Upon termination, write the extensive form of the model - accounting for all fixed variables. \item \verb|--solve-ef|\\            Following write of the extensive form model, solve it. \item \verb|--suppress-continuous-variable-output|\\ Eliminate PH-related output involving continuous variables. Default: no output. \item --keep-solver-files\\   Retain temporary input and output files for scenario sub-problem solves.  Default: files not kept. \item --output-solver-logs\\  Output solver logs during scenario sub-problem solves. Default: no output. \item --output-ef-solver-log\\ \item \verb|--keep-solver-files|\\   Retain temporary input and output files for scenario sub-problem solves.  Default: files not kept. \item \verb|--output-solver-logs|\\  Output solver logs during scenario sub-problem solves. Default: no output. \item \verb|--output-ef-solver-log|\\ Output solver log during the extensive form solve. Default: no output. \item --output-solver-results\\ \item \verb|--output-solver-results|\\ Output solutions obtained after each scenario sub-problem solve. Default: no output. \item --output-times\\        Output timing statistics for various PH components. Default: no output. \item \verb|--output-times|\\        Output timing statistics for various PH components. Default: no output. \item \verb|--disable-warmstarts|\\ Disable warm-start of scenario sub-problem solves in PH iterations >= 1. Do not linearize PH objective terms involving binary decision variables. 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). \item \verb|: --linearize-nonbinary-penalty-terms|\\ Approximate the PH quadratic term for continuous variables with a piece-wise linear function. Default=False. \item \verb|--linearize-nonbinary-penalty-terms|=BPTS\\ Approximate the PH quadratic term for non-binary variables with a piece-wise linear function. The argument BPTS gives the number of breakpoints in the linear approximation. The default=0. Reasonable non-zero values are usually in the range of 3 to 7. Note that if a breakpoint would be very close to a variable bound, then the break point is ommited. IMPORTANT: this option requires that all variables have bounds that are either established in the reference model or by code specfied using the bounds-cfgfile command line option. See Section~\ref{LinearSec} for more information about linearizing the proximal term. \item \verb|--breakpoint-strategy|=BREAKPOINT\_STRATEGY Specify the strategy to distribute breakpoints on the [lb, ub] interval of each variable when linearizing. 0 indicates uniform distribution. 1 indicates breakpoints at the node min and max, uniformly in- between. 2 indicates more aggressive concentration of breakpoints near the observed node min/max. \item \verb|--bounds-cfgfile|=BOUNDS\_CFGFILE\\ The argument BOUNDS\_CFGFILE specifies the name of an executable pyomo file that sets bounds. The devault is that there is no file. When specified, the code in this file is executed after the initialization of scenario data so the bounds can be based on data from all scenarios. The config subdirectory of the farmer example contains a simple example of such a file (boundsetter.cfg). \item \verb|--checkpoint-interval|\\ The number of iterations between writing of a checkpoint file. Default is 0, indicating never.. The number of iterations between writing of a checkpoint file. Default is 0, indicating never. \item \verb|--restore-from-checkpoint|\\ The name of the checkpoint file from which PH should be initialized. Default is not to restore from a checkpoint. \begin{verbatim} pyomo\examples\pysp\farmer \end{verbatim} where the directory \verb|pyomo| might be \verb|pyomodist| or something else depending on how you installed pyomo and pysp. The data is in a subdirectory called SCENARIODATA. To coopr\examples\pysp\farmer \end{verbatim} The data is in a subdirectory called scenariodata and the model is in the models subdirectory. To invoke PH for this problem, connect to this farmer directory and use the command: \begin{verbatim} pyomo\packages\coopr\examples\pysp\sizes \end{verbatim} where the directory \verb|pyomo| might be \verb|pyomodist| or something else depending on how you installed pyomo and pysp. coopr\packages\coopr\examples\pysp\sizes \end{verbatim} The data for a three scenario version is in a subdirectory called SIZES3 and a ten scenario \begin{verbatim} pyomo\packages\coopr\examples\pysp\forestry \end{verbatim} where the directory \verb|pyomo| might be \verb|pyomodist| or something else depending on how you installed pyomo and pysp. coopr\packages\coopr\examples\pysp\forestry \end{verbatim} There are two families of instances: Chile'' and Davis,'' each with four stages and eighteen scenarios. This is also a small To run this example, connect to the sizes directory, which is something like: \begin{verbatim} pyomo\packages\coopr\examples\pysp\sizes \end{verbatim} where the directory \verb|pyomo| might be \verb|pyomodist| or something else depending on how you installed pyomo and pysp. coopr\examples\pysp\sizes \end{verbatim} Then use time. 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. \section{Linearizing the Proximal Term \label{LinearSec}} \subsection{Introduction} For a decision variable $x$ the proximal term added to the objective function for each scenario subproblem at PH iteration $k$ is $$\left(x - \bar{x}^{(k-1)}\right)^{2}$$ where $\bar{x}^{(k-1)}$ is the average over the scenarios from the last iteration. Expanding the square reveals that the only quadratic term is $x^{2}$. For binary variables, this is equal to $x$, although this is not the case when a relaxation is solved. For binary variables, the default behaviour is to replace the quadratic term with $x$, but an option allows the quadratic to be retained because this can effect the subproblem solution time due to the use of the quadratic term when the relaxations are solved as part of the branch and bound process. For non-binary variables an option exists to replace the $x^2$ term with a piece-wise approximation and the number of breakpoints in the approximation is under user control. This can have a significant effect on CPU time required to solve sub-problems because the presence of the quadratic term increases the solution times significantly. However, linearization results in a time-quality tradeoff because increasing the number of breakpoints increases the fidelity but each breakpoint introduces another (unseen) binary variable so solution times are generally increased. A few strategies for placing the breakpoints are supported as command a line options: \verb|--breakpoint-strategy|=BREAKPOINT\_STRATEGY. A value of 0 indicates uniform distribution. 1 indicates breakpoints at the min and max for the node in the scenario tree, uniformly in- between. A value of 2 indicates more aggressive concentration of breakpoints near the observed node min/max. Upper and lower bounds for variables must be specified when the linearization option is chosen. This can be done by specifying bounds in the reference model or by using the bounds-cfgfile command line option. It is, of course, best to use meaningful bounds provided in the reference model; however, the modeller must be careful not use estimated bounds that are too tight since that could preclude an optimal (or even a feasible) solution to the overall stochastic problem even though it might not cut off any optimal solutions for the particular scenario. The use of a bounds cfgfile is an advanced topic, but enables the modeller to use bounds that cannot create infeasibilities. \subsection{Bounds-cfgfile} Using a bounds cfgfile is an advanced topic. The modeler is writing python/pyomo code that will be executed by the ph.py file that is the core of the PH algorithm. The first executable line in a bounds file is typically: \begin{verbatim} model_instance = self._model_instance \end{verbatim} This establishes a local variable called model\_instance'' that can be used to refer to the model (of course, a different name can be used, 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 variables defined in the ReferenceModel.py file that can be accessed by name. For example, with the Farmer model, the cfg file sets the uppter bound on DevotedAcreage to be value of the paramter TOTAL\_ACREAGE at intialization (since this is Python, the parentheses after TOTAL\_ACREAGE cause the value in TOTAL\_ACREAGE to be assigned rather than the name of the parameter object: \begin{verbatim} # only need to set upper bounds on first-stage variables, i.e., those being blended. model_instance = self._model_instance # the values supplied to the method upper_bound = float(model_instance.TOTAL_ACREAGE()) for index in model_instance.CROPS: # the lower and upper bounds are expected to be floats, and trigger an exception if not. self.setVariableBoundsAllScenarios("DevotedAcreage", index, 0.0, upper_bound) \end{verbatim} The 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. %\subsection{Sizes Example} \section{Solving sub-problems in Parallel \label{parallelsec}} Here are the commands in order: \begin{enumerate} \item On the master: \verb|pyro-ns| \item On the master: \verb|coopr-ns| \item On the master: \verb|dispatch_srvr| \item On each slave: \verb|pyro_mip_server| \item On the master: \verb|runph ... --solver-manager=pyro ...| \end{enumerate} Note that the command \verb|pryo-ns| and the argument \verb|solver-manger| have a dash in the middle, while Note that the command \verb|coopr-ns| and the argument \verb|solver-manger| have a dash in the middle, while the commands \verb|dispatch_srvr| and \verb|pyro_mip_server| have underscores. The first three commands launch processes that have no internal mechanism for termination; i.e., they will be terminated only if they crash or if they are killed by an external process. It is common to launch these processes with output redirection, such as \verb|pyro-ns >& pyrons.log|. The killed by an external process. It is common to launch these processes with output redirection, such as \verb|coopr-ns >& cooprns.log|. The \verb|runph| command is a normal runph command with the usual arguments with the additional specification that subproblem solves should be directed to the pyro solver manager.