BBPH:
Using Progressive Hedging Within Branch andBound to Solve Multi-Stage Stochastic Mixed
Integer Programs
David L. Woodruff and Jason Barnett
University of California Davis
Jean-Paul Watson
Sandia National Laboratories

Berlin, January 20191 / 13

The paper (and talk) in one slide

Progressive hedging (PH) is an iterative, scenario decomposition
method for solving multi-stage stochastic programs (Rockefellarand Wets).
PH alone is not guaranteed to convergenge for stochastic MIPs.
We motivate and describe a provably convergent branch andbound algorithm that uses PH within each (outer) node.
Computational experiments show that for some difficult problem
instances BBPH can find improved solutions within a few branches(but that’s not really the main thing).

1 / 13

A few B&B algorithms

Shabbir Ahmed. A scenario decomposition algorithm for 0-1
stochastic programs.
Technical report, ISYE, Georgia Tech, 2013
Claus C Carøe and Rüdiger Schultz. Dual decomposition instochastic integer programming.
Operations Research Letters, 24(1):37–45, 1999
Laureano F. Escudero, Araceli Garı́n, Marı́a Merino, and GloriaPérez. Bfc-msmip: an exact branch-and-fix coordination approachfor solving multistage stochastic mixed 0–1 problems.
TOP, 17(1):96–122, 20092 / 13Our Paper

J Barnett, JP Watson, DL Woodruff Operations Research Letters 45(1), 2017, 34-39

3 / 13

Bounds
Lower bound with roughly the same effort as a PH iteration
D. Gade, G. Hackebeil, S.M. Ryan, J.P. Watson, R.J.B. Wets, andD.L. Woodruff. Obtaining lower bounds from the progressive
hedging algorithm for stochastic mixed-integer programs.
Mathetmatical Programming Series B, 157:47–67, 2016(not an integer relaxation)
Upper bound, e.g., by computing the expected value of a scenario
solution“Side effect:”
Ge Guo, Gabriel Hackebeil, Sarah M Ryan, Jean-Paul Watson,and David L Woodruff. Integration of progressive hedging anddual decomposition in stochastic integer programs.
Operations Research Letters, 43(3):311–316, 2015
4 / 13

Motivation“Unsolvable by PH” examples in the paper
Theorem in the paper
But mainly it puts you in the midst of an exact algorithm when
you use PH

5 / 13

Sketch of PHBB
Let u be the non-leaf decisions and y the leaf-node decisions.
1 Initialize: Set z̄ = ∞ and z = −∞. Set L ← {(SMIP)}.
02 Choose node: Select a node N i ∈ L. If L = ∅, goto Step 5.
3 Calculate bounds: Remove N i from L. Run PH on the selectedouter B&B node N i . After each iteration of PH,
1

24

5

6

Obtain x̂ = (û, ȳ), calculate the corresponding objective value m;
set z̄ ← min{m, z̄}. Remove nodes N i ∈ L ∪ N with z i > z̄.
Compute bound D(wν ). If z̄ − D(wν ) < , terminate PH and returnto step 2.

Branch: Select a non-fixed variable u1 (i), and create subnodes
N i0 and N i1 corresponding to the branches u1 (i) ≤ ū1 (i) andu1 (i) > ū1 (i) respectively. If u1 (i) are fixed ∀i, continue with u2 (i)(and so on). If N i0 and N i1 are fully real-valued problems, add
them to N , else add them to L. Return to step 2.
Choose terminal node: Select a node N i ∈ N and continue toStep 6. If N = ∅, terminate BBPH with the following: if z̄ = ∞,the problem is infeasible, otherwise our solution is x̂ with objectivevalue z̄.
Solve terminal node: Remove N i from N . Run PH on N i with
6 / 13

Three Potential Levels of Parallelism

1“Outer” BBPH nodes

2PH by scenario

3BB nodes within the scenario MIP solves

7 / 13

Conclusions

An implementation of PH and some test instances are available atpyomo.org
BBPH was released with the paper.
BBPH puts PH in an exact algorithm.

8 / 13

Mulistage Stochastic Formulation(for people who already know most of the notation)

T

X

ft xt ; ~x t−1 , ξ~ tmin f1 x1 + Ex

(1)

t=2

subject to x(ξ) ∈ Yξ , ξ ∈ Ξ,(2)9 / 13

Multi-stage formulation with a tree
Followed by Sketch of PH Algorithm

Let Gt be the set of all scenario tree nodes for stage t and let Gt (ξ) bethe node at time t for a particular scenario, ξ. For a particular node D
let D−1 be the set of scenarios that define the node.
In the presence of a scenario tree, non-anticipativity must be enforcedat each non-leaf node, so using the discrete scenario tree notation,problem (1) becomes#"TXXminπξ f1 (x1 (ξ)) +ft xt (ξ); ~x t−1 , ξ~ t(3)x,x̂ξ∈Ξ

t=2s.t. x(ξ) ∈ Yξ , ξ ∈ Ξxt (ξ) − x̂t (D) = 0, t = 1, . . . , T − 1, D ∈ Gt , ξ ∈ D−1(4)(5)

10 / 13

1

Initialization: Let ν ← 0 and wν (Gt (ξ)) ← 0, ∀ξ ∈ Ξ, t = 1, . . . , T .
Compute for each ξ ∈ Ξ :"#TXX
1tt−1 ~ txν+1 (ξ) ∈ arg minπξ f1 (x (ξ)) +ft x (ξ); ~x,ξ.
x∈X(ξ) ξ∈Ξt=22

Iteration Update: ν ← ν + 1.

3

Aggregation: For each t = 1, . . . , T − 1 and each D ∈ Gt : XXx̄tν (D) ← π xtν (Gt (ξ)) / π .
ξ̂ξ̂∈D −14ξ̂ξ̂∈D −1

Weight Update: For each t = 1, . . . , T − 1 and each ξ ∈ Ξ:wν (Gt (ξ)) ← wν−1 (Gt (ξ)) + ρ[xtν (G(ξ)) − x̄ν (G t (ξ))].

5

Decomposition: For each ξ ∈ Ξ: assign xν+1 (ξ) ∈ arg minx∈X(ξ)
f1 (x1 (ξ)) +6−1 h TXi
ρft xt (ξ); ~x t−1 , ξ~ t +hwνt (ξ), xt i + kxt − x̄tν (ξ)k2 .
2
t=2
t=1

TX

Termination criterion: If the solutions at the tree nodes are equal (upto a given tolerance ) or the maximum iteration count is reached, stop.

11 / 13

Test results for network flow minimization problems; times are wall-clock
seconds.
Instance
1ef50
2ef50
3ef50
4ef50
5ef50

EF
Objective
158653151060161466153854150401

PHTime
2579
1172
2843
2296
1190

Obj.
166848156211
167871157229155002

BBPH
Time
Obj.
18161 162163
15330 156211
33390 165733
18150 157229
8556 152686

PH Bundles
TimeObj.
31891 162946
9486 154065
30228 166174
8349 157697
7841 156109

12 / 13

Test results for three stage network flow with a branching factor of ten for thesecond stage and three for the third; times are wall-clock seconds.

Instance

Time

EF
Objective

TimePH
Objective

1ef10
2ef10
3ef10
4ef10
5ef10

10,046
10,045
3,424
2,327
4,295

160,964
156,637
157,025
170,067
161,840

1,934
2,065
1,748
1,428
2,432166,189
160,849
166,406
191,796
169,287

BBPH
Time Objective
18,606
13,767
13,581
13,786
14,911

163,647
160,052
160,032
176,127
168,542

13 / 13