# Presentation: 040730

## Using Stochastic Programming Problem Structure to Gain Computational Efficiency

- John R. Birge
- Northwestern University

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Outline

- General Model – Observations
- Overview of approaches
- Factorization/sparsity (interior point/barrier)
- Decomposition
- Lagrangian methods
- Conclusions

- Theme: taking advantage of repeated problem structure can yield significant computational savings.

- Sandia National Labs, Livermore, CA

- January 23, 2003

## General Stochastic Programming Model: Discrete Time

- Find x=(x1,x2,...,xT) and p to

**minimize    E****p**** [ ********t=1****T****f****t****(x****t****,x****t+1****,p) ]**
**s.t.          x****t**** ********  X****t, ****x****t****   nonanticipative p in P (distribution class)**
**          ****P[ h****t**** (x****t****,x****t+1,****p****t,****) <= 0 ] >= a (chance constraint)**

**General Approaches:**
** ****Simplify distribution (e.g., sample) and form a mathematical program:**
** ****Solve step-by-step (dynamic program)**
** ****Solve as single large-scale optimization problem**
**Use iterative procedure of sampling and optimization steps**

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Simplified Finite Sample Model

- Assume p is fixed and random variables represented by sample it for t=1,2,..,T, i=1,...,Nt with probabilities pit ,a(i) an *ancestor* of i, then model  becomes (no chance constraints):

**minimize    ********t=1****T ********i=1****N****t**** **pit** ****f****t****(x****a(i)****t****,x****i****t+1****, ********i****t****) **
**s.t.          x****i****t**** ********  X****i****t**

- Observations?
-  Problems for different i are similar – solving one may help to solve others
-  Problems may decompose across i and across t yielding
- smaller problems (that may scale linearly in size)
- opportunities for parallel computation.

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Outline

- General Model – Observations
- Overview of approaches
- Factorization/sparsity (interior point/barrier)
- Decomposition
- Lagrangian methods
- Conclusions

- .

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Solving As Large-scale Mathematical Program

- Principles:
- discretization leads to mathematical program but large-scale
- use standard methods but exploit structure
- Direct methods
- take advantage of sparsity structure
- some efficiencies
- use similar subproblem structure
- greater efficiency
- Size
- unlimited (infinite numbers of variables)
- still solvable (caution on claims)

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Standard Approaches

- Sparsity Structure Advantage
- Partitioning
- Basis Factorization
- Interior Point Factorization
- Similar/Small Problem Advantage
- DP Approaches: Decomposition
- Benders, L-shaped (Van Slyke – Wets)
- Dantzig-Wolfe (Primal Version)
- Regularized (Ruszczynski)
- Various Sampling Schemes (Higle/Sen Stochastic Decomposition, Abridge Nested Decomposition)
- Lagrangian Methods

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Outline

- General Model – Observations
- Overview of approaches
- Factorization/sparsity (interior point/barrier)
- Decomposition
- Lagrangian methods
- Conclusions

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Sparsity Methods: Stochastic Linear Program Example

- Two-stage Linear Model:
- X1 = {x1| A x1 = b, x1 >= 0}
- f0(x0,x1)=c x1
- f1 (x1,x2i,2i) = q x2i  if T x1 + W x2i = 2i,
-                         x2i >= 0; +  otherwise
- Result:  min c x1 + ******i=1****N1**** ****p**2i q x2i
-    s. t. A x1 = b, x1 >= 0
-           T x1 + W x2i = 2i, x2i >= 0

- Sandia National Labs, Livermore, CA

- January 23, 2003

## LP-Based Methods

- Using basis structure:

**PERIOD 1**

**PERIO D 2**

**• ****Modest gains for simplex**

**Interior Point Matrix Structure**

**= **** A’**

** ****A’D****2****A’****T=**

**COMPLETE FILL-IN**

- A

- T

- T

- T

- T

- W

- W

- W

- W

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Alternatives For Interior Points

- Variable splitting   (Mulvey Et Al.)
- Put in explicit *nonanticipativity constraints*

**= **** A’**

**NEW **

**Result**
**Reduced fill-in but larger matrix**

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Other Interior Point Approaches

- Use of dual factorization or modified Schur complement

**A’****T**** D****2**** A’=**

**=**

**Results:**** **
**       • ****Speedups of 2 to 20 **
**       •  ****Some instability => Indefinite system (Vanderbei et al.**
**              ****Czyzyk et al.)**

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Outline

- General Model – Observations
- Overview of approaches
- Factorization/sparsity (interior point/barrier)
- Decomposition
- Lagrangian methods
- Conclusions

- Theme: taking advantage of repeated problem structure can yield significant computational savings.

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Similar/small Problem Structure: Dynamic Programming View

- Stages: t=1,...,T
- States: xt -> Btxt(or other transformation)
- Value Function:
*Q*t(xt) = E[Qt(xt,t)] where
- t is the random element and
- Qt(xt,t)  = min ft(xt,xt+1,t) + *Q*t+1(xt+1)
-            s.t. xt+1   Xt+1t(,t)     xt  given
- Solve : iterate from T to 1

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Linear Model Structure

*Q**N+1**(x**N**) = 0, *for all *x**N*,
*Q**t,k**(x**t-1,a(k)**)* is a piecewise linear, convex function of *x**t-1,a(k)*

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Decomposition Methods

- Benders Idea
- Form an outer linearization of *Q*t
- Add_* Cuts*_ On Function :

*Q***t**

**Linearization at iteration k**

**min at k : < ***Q***t**

**new cut **
***(optimality cut)***

**Use at each stage to approximate  value function**
**    • ****Iterate between stages until all min =**** ***Q***t**

- Feasible region
*(feasibility cuts)*

- Sandia National Labs, Livermore, CA

- January 23, 2003

##  Sample Results 

- SCAGR7 PROBLEM SET

**LOG (NO. OF VARIABLES)**

**LOG (CPUS)**

**3****	****4****	****5****	****6****	****7**

**1**

** ****2**

**3**

**4**

**Standard LP **

**NESTED DECOMP.**

**PARALLEL:**** 60-80% EFFICIENCY IN SPEEDUP**

**OTHER PROBLEMS:   SIMILAR RESULTS**

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Decomposition Enhancements

- Optimal basis repetition
- Take advantage of having solved one problem to solve others
- Use *bunching* to solve multiple problems from root basis
*Share* bases across levels of the scenario tree
- Use solution of single scenario as *hot start*
- Multicuts
- Create cuts for each descendant scenario
- Regularization
- Add quadratic term to keep close to previous solution
- Sampling
- Stochastic decomposition (Higle/Sen)
- Importance sampling (Infanger/Dantzig/Glynn)
- Multistage (Pereira/Pinto, Abridged ND)

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Multistage: Pereira-Pinto Method

- Incorporates sampling into the general framework of the Nested Decomposition algorithm
- Assumptions:
- relatively complete recourse
- no feasibility cuts needed
- serial independence
- an optimality cut generated for any Stage t node is valid for all Stage t nodes
- Successfully applied to multistage stochastic water resource problems

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Pereira-Pinto Method

- 1. 	Randomly select *H* *N*-Stage scenarios
- 2. 	Starting at the root, a forward pass is made through the sampled portion of the scenario tree (solving ND subproblems)
- 3.	A statistical estimate of the first stage objective value     is calculated using the total objective value obtained in each sampled scenario
- the algorithm terminates if current first stage objective value *c**1**x**1** + ****1*  is within a specified confidence interval of
- 4.	Starting in sampled node of Stage t = N-1,  solve all Stage t+1 descendant nodes and construct new optimality cut.  Repeat for all sampled nodes in Stage t, then repeat for        t = t - 1

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Pereira-Pinto Method

- Advantages
- significantly reduces computation by eliminating a large portion of the scenario tree in the forward pass
- Disadvantages
- requires a complete backward pass on all sampled scenarios
- not well designed for bushier scenario trees

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Abridged Nested Decomposition

- Also incorporates sampling into the general framework of Nested Decomposition
- Also assumes relatively complete recourse and serial independence
- Samples both the subproblems to solve and the solutions to continue from in the forward pass

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Abridged Nested Decomposition

- 4.	For each selected Stage t-1 subproblem solution, sample Stage t subproblems and solve selected subset
- 5.	Sample Stage t subproblem solutions and branch in Stage t+1 only from selected subset

_**Forward Pass**_
**1.****	****Solve root node subproblem**
**2.****	****Sample Stage 2 subproblems and solve selected subset**
**3.****	****Sample Stage 2 subproblem solutions and branch in Stage 3 only from selected subset (i.e., nodes 1 and 2)**

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Abridged Nested Decomposition

- _Convergence Test_
- 1. 	Randomly select *H* *N*-Stage scenarios.  For each sampled scenario, solve subproblems from root to leaf to obtain total objective value for scenario
- 2.	Calculate statistical estimate of the first stage objective value
- algorithm terminates if current first stage objective value *c**1**x**1** + ****1*  is within a specified confidence interval of    ; else, a new forward pass begins

_**Backward Pass**_
**1.****	****Starting in first branching node of Stage t = N-1,  solve all Stage t+1 descendant nodes and construct new optimality cut for all stage t subproblems.  Repeat for all sampled nodes in Stage t, then repeat for t = t - 1**

- Sandia National Labs, Livermore, CA

- January 23, 2003

##  Sample Computational Results

-  Sample Computational Results

- Test Problems
- Dynamic Vehicle Allocation (DVA) problems of various sizes
- set of homogeneous vehicles move full loads between set of sites
- vehicles can move empty or loaded, remain stationary
- demand to move load between two sites is stochastic
- DVA.*x.y.z*
*x*	number of sites (8, 12, 16)
*y*	number of stages (4, 5)
*z*	number of distinct realizations per stage (30, 45, 60, 75)
- largest problem has > 30 million scenarios

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Computational Results (DVA.8)

**CPU Time (seconds)**

**Fleet Size****	****50**
**Links****	****72**

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Outline

- General Model – Observations
- Overview of approaches
- Factorization (interior point/barrier)
- Decomposition
- Lagrangian methods
- Conclusions

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Lagrangian-based Approaches

- General idea:
- Relax nonanticipativity
- Place in objective
- Separable problems

**MIN    E [ ********t=1****T**** f****t****(x****t****,x****t+1****) ]**
**s.t.          x****t**** ********  X****t**
**               ****x****t****   nonanticipative**

**MIN       E [ ********t=1****T**** f****t****(x****t****,x****t+1****) ]**
**x****t**** ********  X****t**
**                      ****+ E[**_**w**__**,**_**x] + r/2||x-**_**x**_**||****2**

**Update****:  w****t****;  ****Project****: x into N - nonanticipative space as **_**x**_** **

**Convergence: Convex problems - Progressive Hedging Alg. **
**                        ****(Rockafellar and Wets)**
**Advantage: Maintain problem structure (networks)**

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Lagrangian Methods and Integer Variables

- Idea: Lagrangian dual provides bound for primal but
- Duality gap
- PHA may not converge
- Alternative:  standard augmented Lagrangian
- Convergence to dual solution
- Lose separability
- May obtain simplified set for branching to integer solutions
- Problem structure: Power generation problems
- Especially efficient on parallel processors
- Decreasing duality gap in number of generation units

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Outline

- General Model – Observations
- Overview of approaches
- Factorization (interior point/barrier)
- Decomposition
- Lagrangian methods
- Conclusions

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Some Open Issues

- Models
- Impact on methods
- Relation to other areas
- Approximations
- Use with sampling methods
- Computation Constrained Bounds
- Solution Bounds
- Solution methods
- Exploit specific structure
- Parallel/distributed architectures
- Links to approximations

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Criticisms

- Unknown costs or distributions
- Find all available information
- Can construct bounds over all distributions
- Fitting the information
- Still have known errors but alternative solutions
- Computational difficulty
- Fit model to solution ability
- Size of problems increasing rapidly

- Sandia National Labs, Livermore, CA

- January 23, 2003

## Conclusions

- Stochastic programs structure:
- repeated problems
- nonzero pattern for sparsity
- use of decomposition ideas
- Results
- take advantage of the structure
- speedups of orders of magnitude

- Sandia National Labs, Livermore, CA

- January 23, 2003