A Scalable Decomposition Approach for
Stochastic Mixed-Integer Programs
Kibaek Kim
Jointly work with Brian Dandurand (ANL), Cosmin Petra (LLNL),
and Victor Zavala (UW-Madison)
Mathematics and Computer Science Division
Argonne National Laboratory
UG Workshop, Berlin, Germany
January 15, 20191

Argonne:
Argonne: Vital
Vital part
part ofof DOEDOE National
National Laboratory
Laboratory System
System2

2

Today’s Talk is about …
§ Stochastic Programming– Integer variables– Parallel algorithms– Software implementation§ Dual Decomposition– New parallel algorithms to accelerate solutions– Asynchronous parallel computation– New branch-and-bound for global optimality§ Numerical Results

Ax0
T1 x 0..
.

..

.

TN x 0
y0 A

= b0
= b1
..
.

+W1 x1+y1 T1
y1 W1

···
..

+WN xN= bN+yN TN

= ⇡0
= ⇡1
..
.

+yN WN= ⇡N.

– Open-source software package– SIPLIB test instances– Test problems for stochastic unit commitment– Argonne’s high performance computing clusters

3

Parallel Decomposition Methods for Stochastic MIP

Kim, Kibaek and Victor M. Zavala. "Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer
programs." Mathematical Programming Computation (2017): 1-42.

4

Stochastic Mixed Integer Programming (SMIP)
General formulation of SMIP:mincT x + E[Q(x, !)]

s.t.

Ax

b,

x 2 Rn+1 p1 ⇥ Zp+1

Make here-and-now decision x• Operational decisions• Logical decisions• Countable items

Recourse function of an integer program:

Q(x, !) = min

q(!)T ys.t.

W (!)yh(!)

T (!)x,y 2 Rn+2 p2 ⇥ Zp+2
Make wait-and-see decision y for given firststage decision x and event ω• Recourse action to event realization(e.g. re-scheduling, system restoration)• Time-dependent decisions

Observe stochastic event ω• System Failure• Demand and supply• Cost and price• Weather5

Dual Decomposition for SMIPcT x(!1 )Ax(!1 )
T (!1 )x(!1 )..
.

+q(!1 )T y(!1 )+q(!N )T y(!N )+W (!1 )y(!1 )..

Nonanticipaticity constraintsx(!1 )
x(!1 ),

−30

..
.

.

...
...
...

y(!1 ),§+cT x(!1 )+...

Ax(!N )T (!N )x(!N )= x(!N )x(!N )+W (!N )y(!N )−35b,h(!1 )

cT x + E[Q(x,ω)]

min
s.t.

−40
−45
−50
−55

b
h(!N )

5
4
3y(!N )

2 Rn+1 p1 ⇥ Zp+1
2 Rn+2 p2 ⇥ Zp+2

Becomes More Challenging!

2
1
x2

0

0

2

1

3

4

x1

– The recourse function is nonconvex and discontinuous.
– Benders Decomposition cannot be used.

§

Dual Decomposition– Lagrangian relaxation of the nonanticipativity constraintsz = min

x0 ,xj ,yjs.t.
Nonanticipaticity
constraints

NX

pj cT xj + qjT yj

j=1(xj , yj ) 2 Gj ,NX

j = 1, . . . , N,

Hj x j = 0 ( )D( ) := min

xj ,yjNX[pj (cT xj + qjT yj )T

Hj x j ]j=1

s.t. (xj , yj ) 2 Gj , j = 1, . . . , N

j=1– Seek for the best lower bound by solvingzzLD := max

N
X
j=1

Dj ( )

Decomposedin each scenario j
65

Dual-Search Method 1:
Subgradient Method

START
SOLVE the Lagrangian dual D(λ) for given λk§§

WIDELY USED in non-differentiable
optimization
The dual variable is updated as
X
k+1
k
k
=
↵
Hs xkss2S

Subgradient of D(λ) at λk

YESD(λ) > zLB?
NOYESzLB improved
for the last m iterations?
NO
REDUCE βk+1 by a halfwhere the step size rule [1] is given by
↵k :=

§

k

k

D( k )k 2
s2S Hs xs k2

zUB
P

UPDATE zLB
UPDATE λk+1 and zUB

No way of proving optimalitymin{Duality gap, βk+1} < ε?

1. Fisher, Marshall L. "The Lagrangian relaxation method forsolving integer programming problems." Management science
50.12_supplement (2004): 1861-1871.

YES

NO
Increment k

END
7Dual-Search Method 2:
Cutting Plane Method
§

START

Outer approximation to solveXmax
Ds ( )SOLVE the Lagrangian dual D(λ) for given λ0

ADD linear inequalities to the Masters2S§

Piecewise linear concave in λ [1]Ds ( ) = min

xs ,yss.t.

§

T(Hs xs )(xs , ys ) 2 conv.hull(Gs )

✓s ,

s.t.

X

SOLVE the Master
SOLVE the Lagrangian dual D(λ) for given λk+1

The Master problem is given by
mk = max§

ps cT xs + qsT ys +UPDATE zLB if D(λk+1) > zLB

✓s

s2S

✓s  Ds ( l ) + (Hs xls )T (s 2 S, l = 0, 1, . . . , k

Finite convergence with Optimalityl),mk- <= D(λk+1)?
YES

NO
Increment k

END

1. Fisher, Marshall L. "The Lagrangian relaxation method for solving integer programming problems." Management science
50.12_supplement (2004): 1861-1871.
8

Ds(λ)

Dual-Search Method 2:
Cutting Plane Methodλ9New Dual Decomposition Method§ The cutting-plane solutions of the Master problem can– oscillate significantly;– suffer from degeneracy.

15
SubgradientCPM
IPM||λk+1 − λk||210§ Interior-Point Cutting-Plane Method

5– Solve the master by using interior-point method
to find feasible solutions (vs. extreme optimal points)– Also use the best known upper bound forearly termination of IPM iterations

0

10

20

30

40
50
60
Number of Iterations

70

80

90

Best known
upper boundDs(λ)§ Adding a set of valid inequalities:– Benders-type feasibility cuts
– Benders-type optimality cuts
– Other cuts can also be added (e.g., cover cuts)– Further cut away the suboptimal solution space

λ
10

100

DSP: Scalable Decomposition Solver§ Decomposition methods for Structured Programming– Exploiting block-angular structures– Dantzig-Wolfe decomposition+ (Parallel) Branch-and-Bound– Benders decomposition– Dual decompositioParallel

Ax0
T1 x 0..
.

..

.

TN x 0
y0 A

= b0
= b1
..
.

+W1 x1+y1 T1
y1 W1

···
..

+WN xN= bN+yN TN

= ⇡0
= ⇡1
..
.

+yN WN= ⇡N.

§ Parallel computing via MPI library

11

12

DSP reads models from Julia(min

1.5 x1

4 x2 +3X
s=1

ps Q(x1 , x2 , ⇠1s , ⇠2s ) : x1 , x2 2 {0, . . . , 5}

)

,

where
Q(x1 , x2 , ⇠1s , ⇠2s ) =min

y1 ,y2 ,y3 ,y4s.t.

2y1 + 3y2 + 4y3 + 5y4  ⇠1s
6y1 + y2 + 3y3 + 2y4  ⇠2s

Only 15 lines of Julia script!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

16y1 + 19y2 + 23y3 + 28y4
x1
x2

y1 , y2 , y3 , y4 2 {0, 1}ssand (⇠1 , ⇠2 ) 2 {(7, 7), (11, 11), (13, 13)} with probability 1/3.
using Dsp, MPI # Load packages
MPI.Init() # Initialize MPI
m = Model(3) # Create a Model object with three scenarios
xi = [[7,7] [11,11] [13,13]] # random parameter@variable(m, 0 <= x[i=1:2] <= 5, Int)@objective(m, Min, -1.5*x[1]-4*x[2])for s in 1:3
q = Model(m, s, 1/3);@variable(q, y[j=1:4], Bin)@objective(q, Min, -16*y[1]+19*y[2]+23*y[3]+28*y[4])@constraint(q, 2*y[1]+3*y[2]+4*y[3]+5*y[4]<=xi[1,s]-x[1])@constraint(q, 6*y[1]+1*y[2]+3*y[3]+2*y[4]<=xi[2,s]-x[2])endsolve(m, solve_type=:Dual, param="myparams.txt")
MPI.Finalize() # Finalize MPI
13

SIPLIB Test Instances§

SIPLIB: publically available test library for stochastic integer programming– http://www2.isye.gatech.edu/~sahmed/siplib/– DCAP: complete recourse, first-stage mixed-integer and second-stage pure integer• Number of scenarios: 200, 300 and 500– SSLP: complete recourse, first-stage pure integer and second-stage mixed-integer• Number of scenarios: 5, 10, 15, 50 and 100
Name
dcap233 200
dcap233 300
dcap233 500
dcap243 200
dcap243 300
dcap243 500
dcap332 200
dcap332 300
dcap332 500
dcap342 200
dcap342 300
dcap342 500# Rows
3006
4506
7506
3606
5406
9006
2406
3606
6006
2806
4206
7006

# Columns
5412
8112
13512
7212
10812
18012
4812
7212
12012
6412
9612
16012

# Integers
5406
8106
13506
7206
10806
18006
4806
7206
12006
6406
9606
16006

Name
sslp 5 25 50
sslp 5 25 100
sslp 15 45 5
sslp 15 45 10
sslp 15 45 15
sslp 10 50 50
sslp 10 50 100# Rows
1501
3001
301
601
901
3001
6001

# Columns
6505
13005
3465
6915
10365
25510
51010

# Integers
6255
12505
3390
6765
10135
25010
50010

14

Computational Results
Instance
dcap233

Scen (r)
200

300

500

dcap243

200

300

500

dcap332

200

300

500

dcap342

200

300

500
<latexit sha1_base64="(null)">(null)</latexit>

Method
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP

Iter
10000
85
36
1503
93
43
2628
117
44
1995
52
37
10000
53
36
126
64
39
126
85
43
126
80
48
126
76
43
126
76
37
126
73
37
126
87
44

UB
1835.34
1835.34
1835.34
1645.221645.221645.221737.941738.471737.942322.502322.502322.502559.482559.92
2559.92
2167.972168.38
2168.38
1068.241065.87
1063.52
1260.421257.01
1257.01
1596.49
1593.00
1592.021620.19
1620.76
1620.18
2069.00
2067.762067.96
1906.18
1905.38
1905.36

LB
1799.08
1833.38
1833.36
1633.881642.73
1642.74
1729.49
1736.66
1736.66
2311.372321.18
2321.182546.912556.66
2556.67
2110.372165.472165.46
983.231059.08
1059.081165.89
1250.901250.911541.24
1587.06
1587.06
1582.101618.071618.072020.112065.432065.42
1861.25
1902.98
1902.97

Gap (%)
1.97
0.11
0.11
0.68
0.15
0.15
0.48
0.10
0.10
0.47
0.05
0.05
0.49
0.12
0.12
2.65
0.13
0.13
7.95
0.64
0.41
7.52
0.49
0.49
3.46
0.37
0.31
2.35
0.16
0.13
2.36
0.11
0.12
2.36
0.12
0.12

Time (s)
3853
935
584
5564
1705
1145
16791
9451
2155
3157
843
694
8869
1313
1167
1992
2648
2290
443
708
512
733
1298
986
1333
2000
1496
505
734
577
881
1271
930
1716
2400
1788

•
•
•
•
•

Smaller gaps in shorter timeLess iterations
Time reduced by a factor of 8
Solution times: 9 ~ 37 mins.
Still positive gaps

15

Computational Results
Instance
sslp 5 25

Scen (r)50100sslp 10 50

50

100

500

1000

2000

sslp 15 45

5

10

15
<latexit sha1_base64="(null)">(null)</latexit>

Method
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP
DDSub
DDCP
DSP

Iter
645
26
5
995
28
5
774
62
11
1224
72
12
344
107
17
177
66
11
115
54
10
914
21
5
427
88
17
541
89
17

UB
-121.60-121.60-121.60-127.37-127.37-127.37-364.64-364.64-364.64-354.19-354.19-354.19-349.13-349.13-349.13-351.71-351.71-351.71-347.26-347.26-347.26-262.40-262.40-262.40-260.50-260.50-260.50-253.60-253.60-253.60

LB-123.76-121.60-121.60-128.94-127.37-127.37-369.21-364.64-364.64-364.64-354.19-354.19-356.35-349.13-349.13-358.88-351.99-351.71-354.03-349.60-347.26-262.42-262.40-262.40-268.15-260.50-260.50-265.30-253.60-253.60

Gap (%)
1.77
0.00
0.00
1.23
0.00
0.00
1.25
0.00
0.00
2.95
0.00
0.00
2.06
0.00
0.00
2.03
0.07
0.00
1.94
0.67
0.00
0.01
0.00
0.00
2.94
0.00
0.00
4.61
0.00
0.00

Time (s)
244
14
6
643
32
19
3105
402
174
9591
1545
777
> 21600
10771
1614> 21600> 216003251> 21600> 21600
4762
2490
164
32
8867
1988
515
> 21600
14917
3092
16

10
DDSub (Solution Time)
DDSub (# of Iterations)
DDCP (Solution Time)
DDCP (# of Iterations)08

sslp_10_50_100

9sslp_10_50_50

sslp_15_45_15

sslp_15_45_10

sslp_15_45_5

sslp_5_25_100

sslp_5_25_50

dcap342_500

dcap342_300

dcap342_200

dcap332_500

dcap332_300

Number of Iterations and Solution Timedcap332_200

dcap243_500

10dcap243_300

1

dcap243_200

10dcap233_500

10dcap233_300

10

Optimality Gap (%)

3

dcap233_200

sslp_10_50_100

sslp_10_50_50

sslp_15_45_15

sslp_15_45_10

sslp_15_45_5−1sslp_5_25_100

sslp_5_25_50

dcap342_500

dcap342_300

dcap342_200

dcap332_500

dcap332_300

dcap332_200

dcap243_500

dcap243_300

dcap243_200

dcap233_500

dcap233_300

dcap233_200

DSP vs. Existing Methods§ Benchmark with
– DSP
– Subgradient method (DDSub)– Standard cutting-plane method (DDCP)

Optimality Gap

10
DDSub
DDCP
DSP

2

7

6

5

4

0

3

2

1

17

DSP vs. Existing Methods - Convergence
−255
−260

Objective Value

−265
−270
−275
−280
DDSub (Lower Bound)
DDSub (Best Lower Bound)
DDCP (Lower Bound)
DDCP (Best Lower Bound)
DSP (Lower Bound)
DSP (Best Lower Bound)

−285
−290
−295
−300

20

40
60
Number of Iterations

80

100

200

300
400
Number of Iterations

500

18

Oscillating Dual Variable Values
15
DDSub
DDCP
DSP

||λk+1 − λk||2

10

5

0

10

20

30

40
50
60
Number of Iterations

70

80

90

100
19

Strong Scaling Results of DSP
2

10

1

10

SpeedupLinear Speedup
sslp_10_50_2000
sslp_10_50_1000
sslp_10_50_500
sslp_10_50_100
sslp_10_50_50

0

10

−1

10

5

10

25
50
Cores

100

250

20

An Asynchronous Variant

Kim, Kibaek, Cosmin G. Petra, and Victor M. Zavala. "An Asynchronous Bundle-Trust-Region Method for Dual Decomposition of Stochastic MixedInteger Programming." SIAM Journal on Optimization (accepted).

21

Dual Decomposition for SMIPcT x(!1 )Ax(!1 )
T (!1 )x(!1 )..
.

+q(!1 )T y(!1 )+q(!N )T y(!N )+W (!1 )y(!1 )..

Nonanticipaticity constraintsx(!1 )
x(!1 ),

−30

..
.

.

...
...
...

y(!1 ),§+cT x(!1 )+...

Ax(!N )T (!N )x(!N )= x(!N )x(!N )+W (!N )y(!N )−35b,h(!1 )

cT x + E[Q(x,ω)]

min
s.t.

−40
−45
−50
−55

b
h(!N )

5
4
3y(!N )

2 Rn+1 p1 ⇥ Zp+1
2 Rn+2 p2 ⇥ Zp+2

Becomes More Challenging!

2
1
x2

0

0

2

1

3

4

x1

– The recourse function is nonconvex and discontinuous.
– Benders Decomposition cannot be used.

§

Dual Decomposition– Lagrangian relaxation of the nonanticipativity constraintsz = min

x0 ,xj ,yjs.t.
Nonanticipaticity
constraints

NX

pj cT xj + qjT yj

j=1(xj , yj ) 2 Gj ,NX

j = 1, . . . , N,

Hj x j = 0 ( )D( ) := min

xj ,yjNX[pj (cT xj + qjT yj )T

Hj x j ]j=1

s.t. (xj , yj ) 2 Gj , j = 1, . . . , N

j=1– Seek for the best lower bound by solvingzzLD := max

N
X
j=1

Dj ( )

Decomposedin each scenario j
225Synchronous Bundle Method
Processors have to wait for the slowest one.
Causing Load-Imbalancing
Resulting in low parallel efficiency
Potentially increasing solution time

§
§
§
§

Synchronization50

Total Solution Time (sec)40

Synchronization

35
30

Solution Time

45

25
20
15

Synchronization

10
5
0

1

2

3
4
Scenario Subproblem

5

Synchronization
23

Asynchronous Bundle Method§ Inexact Approximation of the Lagrangian Dualm̃k,l ( ) := max

X

✓j

j2J

<latexit sha1_base64="GvoilfXn15iVUZEboz8LsEMbqcQ=">AAALunicdZZpcts2FIDldEvoLkn7s38wcdNmgT2W6yZuO5qJHU+cZBo7SeU6E1PWgOSjBQsLA4BazOHVeo8eoPfoAyVZkqVyJGL5APDhbUCUCW7d5uY/Kzc++fSzz7+4eStY/fKrr7+5fefbv6zOTQzHsRbavI+YBcEVHDvuBLzPDDAZCTiJus88P+mBsVyrphtm0JLsXPGUx8xhV/v236HjIoFClu2iS0V5PxQ4OWEPyG8NEko2IOHvJPiRhDaX7eIi5Iq8KknoOuBY+4KEYRA6GLjCbriNcjL2igr4SPbbF5NFz/gD8ojcf4Fo0L7A1lmTTBhZJ9NR1K9EuP8ayuA6MRPFXnlWSVixkSBnvH17bXNjs3rIYqU+rqzVxs+b9p1b/4aJjnMJysWCWXta38xcq2DG8VhAGYS5hYzFXXYOp2w7YxkYKpk556pR33jCVas4By3BmeH8WKwqJsHSpMczW1VbRWWfktxDmJBUG/wrR6re2cmF493LueWK2LHomjgFk9YOZYTreZ3Y68x3/h9zHYlrKeijabQBWYzLsmiOK3NURxZMr3KRsjiaacxv2aU7rYKrLHeg4tE201wQp4l3NZJwA7ETQ6yw2HBUMIk7zLDYoUMG1QdjLSVTSRGihXfL4srYu2W5wPdn+P4SfjDDD5bwlzP85RJ+OMMPl/C3M/ztEv5uhr9bwpszvLmEn8zwkyX8wwz/cJ3vPY/GOEqLaJHGUxov0nxK80Xam9LeIu1PaX+RZlOaLVIzpWaR2im1i3QwpYNFejmll4t0d0orT9sHzAUGXmPXEQY8c9o8LEKMeskxALAMqa8Fc2EFKpfcVaFjwflcfeqb/BJahYDUjbPGwzK4NzuNq1grqwVzDEOGYHIeEsVjICkfQLLe54nrjPIEjhR5gpmjz7EL06zgPVjHCBNzcvgvc3VuvXjCOpSlCPBI4LF1QwGN0LmUSS6GNMDEk0tlG36JVMCAY4qhKINkXSA2N+BDF1deEIWSZ6+rmO5jGIMh3JLDo+ZoGKmGBaiMCMO64XdOJ62RAJiZhLgSI6zSX3Fg2LCkgXWQjQY36lfTIGv4rDxppxxX8gdcw5kcJr2RYKrre+24GzOmReU3tmlQdXd51livb/ziF8IjChSq0uefyfgIz8m5Bbow7GuTjKUeibkncijDKMUUyDG5BzzBgwPPz8nmvPpyi+onILMOwRTP8TsDMlkr8F6HUyaqSOeUcOQtemAAVKUK4804+/XXzGhdsY7ujzmaHSVOmbAw6vf7nrTz7GOuHUya6DOxqHaHYnKFpsvAnz8jkQiz5A/WhPdBGZDKdxJIUR+o2PPce9ZFLjgrg+JKM3i1QJs3wqc0kHhQTLobBSqYO9rvaEshwZrQLKHc4o/hHz7mTFDvPzqlLs/Q69SoyHlCO8x2KH6XCbSeoRgdGBOOZkZL3AruMY/81Go+RuGoZAOK5hO+XZXY9sbH9SGzk7ntah4e1h2dtFFCDA7KMrxWxf5wRWOqnu4CTYTOQGGBpyu1Q3RJScEYbajrGN2neEvwAmEKoS9VSg+ZohmnXNIIMMBx1xwXw9OdVsK43Kixc/m9YGiib0k8ADWtbEMFOMpRTrTQuKB4m6B4I4s7FL2URty7C0oeY6oXNNG08jAqdZJXYstMozwwqIpRyw+MMIWNx3Ap8+oGgZbARei50BEWPvM4uqe1wJ04/9/xr/pj//55iwZYPN6mx+gq1WuneiP2BXJfIH+O5vXNqsT2My3RmINprb61Q3fVkB5q1/GSH2qFcqe5iv0tgl6ZE03O0CQRujbeCgLv6KAs3hR6k1j3bjb218apaBXhWjnqHEVD4zRq/XS9425QErwY1q9fAxcrx1sbv27U326vPd0a3xBv1r6v3a3dr9VrT2pPay9qb2rHtXjlh5VXK3+uNFcbq/EqX+2Oht5YGc/5rjb3rLr/AKsjQl8=</latexit>§

s.t. ✓j  Dj ( i ) + (Hj xij )T (i), i 2 B k,l , j 2 J i

Update the Bundle
with a subset of scenarios

Ingredients are not really new!
– Incremental Subgradient [Kiwiel 2004, Bertsekas 2001, 2011, 2015]– Incremental-Like Bundle [Emiel and Sagastizabal 2010]– Asynchronous Subgradient [Nedic et al. 2001]– Asynchronous Bundle [Fischer and Helmber 2014]– Asynchronous Benders [Linderoth and Wright 2003]§

Trial point queue (for synchronization points)– Necessary to update the trust region– Size of the queue– FIFO vs. LIFO§§

Algorithm should be
carefully designed!

Minimum number of worker processors to wait
for updating the bundle
Static vs. dynamic scenario allocations

MasterLower
Bounding

Trial Point Queue

Lower
Bounding

Lower
Bounding

24

Asynchronous Bundle Method

Synchronization

max ✓1 + ✓2 + ✓3
✓j ,

1

)

✓3  D̄31 + (H3 x̄13 )T (1)

✓1  D̄12 + (H1 x̄21 )T (

2

)

1

)

✓3  D̄32 + (H3 x̄23 )T (2)<latexit sha1_base64="WRFOjK4koMKdgkLoTJvV5u7mX3o=">AAAL4nicfVbbcts2EJV7TehekvaxL5h4kqYprLFsN3EfNBMnnjiZSewkY9eZmIoGJJcSIhBgAFAXs/yCPnX62h/rB7Tf0QVFWZSlliMRiz3AcrE3bJAKbuzW1l9rH338yaeffX7turf+xZdffX3j5je/GJXpEE5DJZR+EzADgks4tdwKeJNqYEkg4CwYPHb42RC04Uqe2EkKnYT1JI95yCyyujf+8RM27ua+7YNl3ffUF7g3YgXxP2Qs8u6QCmmRH2fk9pzcIb7v+RbGNjdN26x2kdouX8AH4gdM5wdFt/XOibn71PEda1yyfnh3Qu5W3yWbpKKQ74TfqX2qLmpnJmrnUtTO/4jq3tjYam6VD1kmWhWx0aiel92b1//2IxVmCUgbCmbMeWsrtZ2cactDAYXnZwZSFg5YD87ZbspS0DRhusdlu9V8wGUn74FKwOrJ4lokJUvA0GjIU1OSnbz0Y0FuIxiRWGn8S0tKbn1zbvngYkFcHloWXFEnZ4kxkyRAeQmzfXMVc8z/wmw/QVkSRmh0pSHJq7HITypiAVWBAT0sQ6nIj2uTxSPbeK+Tc5lmFmQ4PWacCWIVcSFJIq4htGKCBAs1RwOTsM80Cy0Grld+MFRJwmSU+yET+0XuO+WRzPeLYgk/qOEHK/DDGn64An9Ww5+twI9q+NEK/FUNf7UCf13DX6/AT2r4yQr8rIafrcDf1vC3V/FHT4IKDuI8WEbDORouo9kczZbR4RwdLqOjOTpaRtM5mi6jeo7qZdTMUbOMjufoeBm9mKMXy+j+HC0j7QCwFmh4gaxjTHhmlb6X+5j1CccEwNGnjvIW0gpklnBbpo4B62r6uZvyC+jkAmJbVY17hXe7vo3LUEmjBLNYjW8TLOITInkIJOZjiDZHPLL9aZ3AlSKLsHKMOLKwGgs+hE3MMLGgh/sylz3j1BPGoi65h1cHD42dCGj71sYs4WJCPSw8WSJN24mIBYw5lhiKOiRsAMRkGlzqouQlVSh5/KLM6RGmMWjCDTk6PpkuI+UyD40RYFq33cnpbDZVACuTEJdq+GX5yw81mxTUMxbS6eJ263IbpG1XlWfzmKMkdxG2rc5gxg0EkwPHNRUbK6ZB47d3qVeyBzxtb7aaPzlBeJOBRFO6+jNbH+B9uiBgAJOR0lGl9VTNRyKDwg9iLIEci7vHI7w48J6dHc6ZLzNofgJJ2idY4jl+Z0xmsjwXdbhlZop4wQjHzqOHGkCWptDOjfWvv2BaqRLrq1GFo9tR45gJA1O+O/dsnqUfMmVhNsWYCUV5OlSTS3RdCu7+mapEmCHP2Qm88QqPlLETQYz2QMP2MhdZ7zPBWeHll5bBFgR93vYfUi/Bi2LGbudoYG7pqK8MhQgpoVhEucEfwz9g9yCoix8VU5ulGHVyOmQ8on1m+hS/ywR6T1PMDswJS1OtEjwKnjEL3NZyP2bhdGRjiu4Tbl6OOHfOR/mQmtnebrkPL+u+irqoISYHZSm2X6G7XNGZcqgGQCOhUpA44O1KzQRDMqGgtdLU9rUaUewSnEJYQugzGdMjJmnKKU9oAJjgeGqOwvB2p6UyNtOyCi53FkxNjK0EL0BFS99QAZZy1BM9VA0UuwmKnVvYpxilNOAuXFDzEEu9oJGiZYTRREVZqXaSKtQHxuUwnbmF2C9BtYYnSVZ2EOgJFEJ7QgU4uMpj6SOlBJ7Euv+ee7Xuu/fONvVwuL9LTzFUytde+UbYDYi7AfEn6F43LUecP1YJOnM8p1rbe3RfTuiRsn2n+ZGSqHecydB1EfTSnehyhi4JMLSxK/BcoIM02CkMZ7nuwqyK1/a56OT+RjFlTrOhfR50vr/KuOUVBBvD1tU2cJk43W7+3Gy92t14uF11iNca3zVuNe42Wo0HjYeNp42XjdNGuPZ8Ta/la7+uw/pv67+v/zFd+tFatefbxsKz/ue/TsNQCw==</latexit>✓2  D̄11 + (H1 x̄11 )T (<latexit sha1_base64="6aprTjWiujP0vYjgG8Ra88kBtyg=">AAAL2XicfVZLc9s2EJbTV0L3kbTHXjDxpE1T2GPabuIeNBPHnjiZaewkY9eZmIoGJJcWKhBgAFAPc3jpqdNrf10PPfZ/dEFRlmQq5UhcYD9gudgXNswEN3Zz8++VGx99/Mmnn9285a1+/sWXX92+8/WvRuU6gtNICaXfhMyA4BJOLbcC3mQaWBoKOAv7+w4/G4A2XMkTO86gk7ILyRMeMYus7u1/viOB7YFlXZ8EAt6TIGS6OCi7/rst8iO5/8zxHWtUsX54d0LuBwLlx4ysk3qEfBIE3pWoreui/KYo/wOi/EVR24uitqdabV+J2v4frbq31zY3NquHNAd+PVhr1c/L7p1b/waxivIUpI0EM+bc38xsp2Da8khA6QW5gYxFfXYB52wnYxlomjJ9wWXb33jEZae4AJWC1ePFtTiULAVD4wHPTDXsFJX7SnIPwZgkSuNfWlJx5zcXlvcvF8QVkWXhNXUKlhozTkOUlzLbM9cxx/wQZnspypIwRKMrDWlR07I4qQcLqAoN6EEVQWVxPDdZPLJNdjsFl1luQUaTYya5IFYRF4kk5hoiK8Y4YJHmaGAS9ZhmkcV49aoPRipNmYyLIGJirywCpzwOi72ybOAHc/jBEvxwDj9cgj+fw58vwY/m8KMl+Ks5/NUS/PUc/noJfjKHnyzBz+bwsyX42zn87XX8ydOwhsOkCJtoNEOjJprP0LyJDmbooIkOZ+iwiWYzNGuieobqJmpmqGmioxk6aqKXM/Syie7N0CrSDgBrgYYXyDrGhGdW6QdFgFmfckwApAF1I28hrUDmKbdV6hiwrpSfuym/hE4hILF11XhQevfmt3EZKWmUYJZhyhCs3WMieQQk4SOI14c8tr1JncCVIo+xcgw5siyMBB/AOmaYWNDDfZnLC+PUE8aiLoWHNwaPjB0LaAfWJizlYkw9LDx5Kk3biUgEjDiWGIo6pKwPxOQaXOqi5IYqlOy/qHJ6iGkMmnBDjo5PJstItcxDY4SY1m13cjqdTRTAyiTElRpBVf6KQ83GJfWMhWyyuO1fbYOs7arydJ5wlOTuv7bVOUy5oWCy77imZmPFNGj89g71KnafZ+11f+MnJwhGWKLQlK7+TNeHeI0uCOjDeKh0XGs9UfOJyKEMwgRLIMfi7vEYLw68XqeHc+bLDZqfQJr1CJZ4jt8Zkaksz0UdbpmaIlkwwrHz6KEGkJUptHPj/NdfMK1UhfXUsMbR7ahxwoSBCd+dezrPs/e5sjCdYsxEojodqsklui4Dd/9MVCLMkF/YCbzxSo9UsRNDgvZAw17kLrJ+ywVnpVdcWQY7D/R5O3hMvRQviim7XaCBuaXDnjIUYhwJxWLKDf4Y/uF9zgR18aMSavMMo05OSM5j2mOmR/G7TKD3NMXswJywNNMqxaPgGfPQba32YxZOKBtRdJ9w84ri3Dkf5UNmpnu71T68rHsq7qKGmByUZdh1Re5yRWfKgeoDjYXKQCLB25WaMYZkSkFrpantaTWk2CU4hbCE0OcyoUdM0oxTntIQMMHx1ByF4e1OK2VsrmUdXO4smJoYWylegIpWvqECLOWoJ3qoJhS7CYoNW9SjGKU05C5cUPMIS72gsaJVhNFUxXmldpop1AdGFZnM3ELsl6Bew9M0rzoI9AQKoRdChUhc5bH0iVICT2Ldf9e9/Ifuvb1FPSQPd+gphkr12q3eCDuCuCOIP0X3umlFcb6vUnTmaDbyt3bpnhzTI2V7TvMjJVHvJJeR6yLolTvR5QxdEmJoY1fguUAHabBTGExz3YVZHa/tc9EpgrVywpxkQ/s87Hx/nXHXKwk2hv71NrA5ON3a+HnDf7Wz9nir7hBvtr5t3W3db/mtR63HrWetl63TVrSyv8JX9IpZDVZ/X/1j9c/J0hsr9Z5vWgvP6l//ASYkSiE=</latexit>✓2  D̄12 + (H1 x̄21 )T (✓3  D̄33 + (H3 x̄33 )T (

2

)

3

)

Synchronization
Synchronization

Solution Times.t. ✓1  D̄11 + (H1 x̄11 )T (<latexit sha1_base64="kU1ymXNmh0PHvk/bQIWmihFW1TA=">AAALjnicdVbrbts2FHa6W6vs0m4/BwxEg65pxwRxkrXZD2NNGzQtsCZt4SxFI9egpCObM0WqJOVLBL3E3m4PsHfYzx1KcmzHrmDrkOcjjw7PjSdIBTd2Z+eftRufff7Fl1/dvOWtf/3Nt9/dvvP9n0ZlOoSzUAml3wXMgOASziy3At6lGlgSCDgPBs8cfj4EbbiSbTtJoZOwnuQxD5lFVvf23z8T3/bBsu4u8QV8JH7AdH5UdJsfdskvZPNFt1mxxiXrwYc22fQFyo8Y2SL1CPnE970rUXuLovY+7FWi9q5EIesTovYedG9v7GzvlA9ZHjTrwUajfl5379z6149UmCUgbSiYMRfNndR2cqYtDwUUnp8ZSFk4YD24YPspS0HThOkel63m9mMuO3kPVAJWTxbX4lCyBAyNhjw15bCTlzYvyD0EIxIrjX9pScmd35xbPrhcEJeHlgXX1MlZYswkCVBewmzfXMcc81OY7ScoS8IIja40JHlNi7xdDxZQFRjQw9LtRX46N1k8so0POjmXaWZBhtUx40wQq4gLHxJxDaEVExywUHM0MAn7TLPQYpB55QdDlSRMRrkfMnFY5L5THof5YVEs4Udz+NEK/HgOP16Bv5zDX67AT+bwkxX4mzn8zQr87Rz+dgXensPbK/DzOfx8Bf5+Dn9/HX/6PKjhIM6DZTScoeEyms3QbBkdztDhMjqaoaNlNJ2h6TKqZ6heRs0MNcvoeIaOl9HLGXq5jB7O0DLSjgBrgYZXyDrFhGdW6Ye5j1mfcEwApD51I28hrUBmCbdl6hiwrv5euCm/hE4uILZ11XhYePfmt3EZKmmUYJZhyhAsuBMieQgk5mOItkY8sv2qTuBKkUVYOUYcWRbGgg9hCzNMLOjhvsxlzzj1hLGoS+5hmeehsRMBLd/amCVcTKiHhSdLpGk5EbGAMccSQ1GHhA2AmEyDS12UvKQKJc9elTk9wjQGTbghJ6ftahkpl3lojADTuuVOTqezSgGsTEJcqeGX5S8/1mxSUM9YSKvFrebVNkhbripP5zFHSe7SalmdwZQbCCYHjmtqNlZMg8Zv7VOvZA942tpqbv/qBMEYSxSa0tWf6foA774FAQOYjJSOaq0rNZ+KDAo/iLEEcizuHo/w4sA7cXo4Z77MoPkJJGmfYInn+J0xmcryXNThlqkp4gUjnDqPHmsAWZpCOzfOf/0V00qVWF+NahzdjhrHTBio+O7c03mWfsyUhekUYyYU5elQTS7RdSm4+6dSiTBD/mBteOcVHiljJ4IY7YGG7WUusv7KBGeFl19ZBtsF9HnLf0K9BC+KKbuVo4G5paO+MhQiHAnFIsoN/hj+4WPGBHXxo2JqsxSjTlYk4xHtM9On+F0m0HuaYnZgTliaapXgUfCMWeC2lvsxCyvKxhTdJ9y8pDh3zkf5kJrp3m65Dy/rvoq6qCEmB2Uptkqhu1zRmXKoBkAjoVKQSPB2pWaCIZlQ0FppavtajSh2CU4hLCH0pYzpCZM05ZQnNABMcDw1R2F4u9NSGZtpWQeXOwumJsZWghegoqVvqABLOeqJHqoJxW6CYpcV9ilGKQ24CxfUPMRSL2ikaBlhNFFRVqqdpAr1gXFJqplbiP0S1Gt4kmRlB4GeQCG0J1SAxFUeS58qJfAk1v0P3Kv5yL33dqmH5NE+PcNQKV8H5RthRxB3BPHn6F43LSnOn6kEnTmejZq7B/RQTuiJsn2n+YmSqHecydB1EfTKnehyhi4JMLSxK/BcoIM02CkMp7nuwqyO19aF6OT+RlExq2xoXQSd+9cZd72CYGPYvN4GLg/Odrd/226+2d94slt3iDcbPzbuNjYbzcbjxpPGi8brxlkjbPy39tPa/bXN9Tvrj9db679XS2+s1Xt+aCw86y/+Bxv+MNQ=</latexit>

25Computational Experiment Settings§ DSP: an open-source software framework for parallel
decomposition methods– Written in C++ with MPI library– Uses CPLEX for solving the master (by barrier method) and sub-MIP
problems with default parameter settings§ All computations were performed on the Blues cluster.
– 630-node computing cluster at Argonne National Laboratory– Intel Sandy Bridge Xeon E5-2670 2.6GHz– 16 cores per compute node
– 64 GB of memory on each node26

Problem Instances – Stochastic Unit Commitment§ Scheduling power generators anddispatching power from generators toloads– Over electric grid network– For 24-hour time horizon– Under supply uncertainty (wind power
generation)§ A test system data for the WesternElectricity Coordinating Council– 8 load profiles– 10 sets of wind power scenarios– Created 80 problem instances§ Each SMIP has 340,244 variables and352,840 constraints.

27

Load Imbalance§ Percent imbalance metric:
✓ max
◆
tpk
⌫pk :=
1 ⇥ 100%,t̄pk<latexit sha1_base64="ElbjY2VBoxMv0gUEQ6R+C0cLn48=">AAALSnicdZbbbts2GIDVrttadYd2u9wN0aBYVzCBnWVtNsBA0xbNCqxJWyRL0cgLKOmXzZkHlaR8iKC32mvsAbbbbU+wq2E3+ynLsR17gi0ePpL6+Z/IOBfculbrtytX37v2/gcfXr8R3vzo408+vXX7sx+tLkwCx4kW2ryJmQXBFRw77gS8yQ0wGQs4iQdPPD8ZgrFcqyM3yaErWU/xjCfMYdfZrYNIFWdlPqjIdx0SCcjcPRJlhiWl+6mUbFzVsCqjmJnSNS2ySdokMrzXd1+RyHEJlrRbreguPbu10dpq1Q9ZrbSbykbQPC/Pbt/4K0p1UkhQLhHM2tN2K3fdkhnHEwFVGBUWcpYMWA9O2U7OcjBUMtPjqtPeeshVt+yBluDMZHksVhVDwWg65Lmtq92y1ldF7iJMSaYN/pUjde/i5NLxwfnScmXiWHxJnJJJaycyxvUkc317mfnO/2OuL3EtBSPXB21Alk1ZlUdNZYnq2IIZ1iarysOFxvKWXbbbLbnKCwcqmW4zKwRxmnjTk5QbSJyYYIUlhqOCSdJnaGuHDhLWH0y0lEylZZQwsYdW98JjtdyrqhX+dIE/XcP3F/j+Gv58gT9fww8W+MEa/mqBv1rDXy/w12v40QI/WsNPFvjJGv52gb+9zB8/ixscZ2W8SpM5TVZpMafFKh3O6XCVjuZ0tErzOc1XqZlTs0rtnNpVOp7T8So9n9PzVbo3p7WnPQXMBQZeYNchBjxz2twvI4x6yTEAsIyor4VLYQWqkNzVoWPB+dx56pv8HLqlT2xN1rhfhXcXp3GVaGW1YI5hyBBMlhOieAIk42NIN0c8df1pnsCRokgxc4w4djkYCz6ETYwwsSSH/zJXPevFE9ahLGWIKZon1k0EdCLnMia5mNAQE08hle34JTIBY44phqIMkg2A2MKAD11ceUUUSp68qGN6hGEMhnBLDg6PpsNIPSxEZcQY1h2/czprTQXAzCTEhRhRnf7KfcMmFQ2tg3w6uNO+mAZ5x2flWTvjuJI/cDrOFDDrjQVTA99rm27MmBaV39mhYd094Hlns731jV8IxpiiUJU+/8zGx3huLS0wgMlIm7SReirmY1FAFcUZpkCOyT3kKR4ceJ7NNufVV1hUPwGZ9wmmeI7fGZPZWqH3OpwyU0W2pIRDb9F9A6BqVRhvxsWvv2BG65r19ajhaHaUOGPCwrTf73vWLvJ3hXYwa6LPJKLeHYrJFZouB3/+TEUizJIf2BG8CauQ1L6TQob6QMX2Cu9ZPxeCsyosLzSDRz3avBM9oqHEg2LW3SlRwdzRUV9bCinWhGYp5RZ/DP/wrmCCev/RGXVFjl6npkXBU9pntk/xu0yg9QzF6MCYcDQ3WuJWcI9F7KfW8zEKpyUbUzSf8O26xLY3Pq4PuZ3NPavn4WHd1+kZSojBQVmO15zEH65oTDXUA6Cp0DkoLPB0pXaCLikpGKMNdX2jRxRvCV4gTCH0ucroAVM055RLGgMGOO6a42J4utNaGFcY1TiX3wuGJvqWxANQ09o2VICjHOVECzUFxdsExRtS0qfopTTm3l1Q8gRTvaCpprWHUanTohZb5hrlgXFdTFt+IF6ZoBnDpSzqGwRaAhehPaFjLHzmcfSx1gJ34vx/17/aD/z7620aYvFghx6jq9Sv3fqN2BfIfYH8GZrXN+sS20+0RGOO57X29i7dUxN6oF3fS36gFcqdFSrxtwh6YU40OUOTxOjaeCsIvaODsnhTGM5i3btZ46+dU9Eto41q2jmNhs5p3P3ycsedsCJ4MWxfvgauVo63t77dar/a2Xi03dwQrwdfBHeCe0E7eBg8Cr4PXgbHQRL8Evwe/BH8Gf4a/h3+E/47HXr1SjPn82DpuXntP94uI2A=</latexit>– How much the maximum time isdeviated from the mean time.

Highly imbalanced§ Distribution of the average percent
imbalance metrics resulting fromthe synchronous BTR– 27% ~ 84%– 18 highly imbalanced instances (> 50%)28

Load Imbalance – What you really see…
Low Imbalanced Instance
20

40

60

80

0
2
4
6
8
10
12
14

50
40
30
20

Seconds

Process

010
Iteration0

Highly Imbalanced Instance
20

40

60

80

50
40
30
20
10

Iteration

029

Seconds

Process

0
0
2
4
6
8
10
12
14

Asynchronous Computing Results
Async-Q1P1 is the fastest for
70% of the instances.

Sync is slow by afactor 3.4.

Highly imbalanced
Sync is slow for all
the instances.

Highly imbalanced30

Computational Experiments – Other Variants§

Static vs. Dynamic allocation of the scenario subproblems– Dynamic allocation improves parallel efficiency in general.
– However, the dynamic allocation loses the MIP warm-start.

§

FIFO vs. LIFO for evaluating trial points– FIFO shows marginally better results.

§

All these variations do not affect the convergence results of the method.

Static allocation wins!

FIFO wins!

31

Strong Scaling of the Asynchronous Method32

Scalable Branching on Dual Decomposition

Kim, Kibaek and Brian Dandurand. "Scalable Branching on Dual Decomposition of Stochastic Mixed-Integer Programming Problems." Mathematical
Programming Computation (submittted).

33

Scalable Branching Approaches§ Dual decomposition is a bounding method.
zzLD := maxNX

Dj ( )

j=1§ Branch-and-bound is the most natural approach to proving
optimality for MIP.
– We already have a very tight bound from DD.
– Let's branch!

§ Branching rules to consider:– at which solution point (or value)– in which direction

34

Branch-and-Price Method
DWD is the dual of the dual decomposition.
A natural choice for branching is on fractional integer variables in the original space.

§max✓n , n

s.t.

N
X

min

✓n

n=1
N
X

Dualizing
n =0

↵k
n ,x0

(x0 )

s.t.

n=1

✓n  D n (kn ),n=1 k=1
K
X

K
X(↵nk )<latexit sha1_base64="yC1lzGyVcYJqYUdAXcaKgZYQ3uk=">AAAMhHicdVZtjxM3EM7RltLttYX2Y79YIChF5nThXapS8SYoAo63O0Dchsi7601MvPZiey8Jq/1J/TX9VKn9L3282ZDNJY2S2DOPZzz2jGcmyqWwbnf3760TX3z51cmvT30TfLv93fc/nD7z42urCxPzg1hLbd5GzHIpFD9wwkn+NjecZZHkb6LxPY+/OeLGCq323Szn/YwNlUhFzBxYgzNbD8JMqEEZMpmP2EC9H9PpYLci4ceCJcEFEtoiG5Sq163e7zXE2BOPSSh56g7J/YG6GEpsmNTSv5LL5OJ08AGz9/ukBZDQiOHI9clyJxKGQej41JV2x+0s9yzD+lyl4Um1uud0LrbU0ANrl84lCaykYaKdpXsV9covHLO4LdfdILUQalk45B/Jpg3A+o2MP9OPB6fP7e7s1h+yPuk2k3Od5vN8cCY4D9G4yLhysWTWHnZ3c9cvmXEilrwKwsLynMVjNuSH7FrOcm5oxsxQwIqdm0L1yyHXGXdmtroWU8UybmlyJHJbT/tlfaEVOQ8wIak2+ClHam5buHRi/GlFXRk7Fh0zp2SZtbMsgr6MuZE9jnnm/2FulEGX4hM34trwrGzGqtxvJiuojiw3R3WsVuWzFrF6ZJfe6pdC5YXjKp4fMy0kcZr4mCeJMDx2coYJi43ABZN4xAyLHV5GUG8Y6yxjKkHoMXmnKkNvPKblnapaw++38Psb8Ict/OEG/FELf7QBf9LCn2zA91r43gb8RQt/sQF/2cJfbsBftfBXG/D9Fr6/AX/Twt9swN+18HfH8bsPogaO0jJaR+MlGq+jxRIt1tGjJXq0jk6W6GQdzZdovo6aJWrWUbtE7To6XaLTdfTTEv20jt5ZonWk3ufIJYY/BesZEgZz2lxCbjdDJPkKuWUYUj8LVp4lV0UmXP30LHe+6Bx6Unzi/dIn+SbrXKqQslpiQsVaWS2ZY3hyBFVmRpSIOUnFlCeXJyJxo3mewUpZJMg8EwEWMr4UR/wyXqhcscPvLNTQevOkdbClDFDbRGzdTPJe6FzKMiFnNEDiKjJle15FKvlUIEVR2JCxMSe2MNw/fWheM4WSe0/rnDBBGuCGCEv2nu3Pl5F6WYDLiJAWev7kdEHNDUBmk/KzGU2VemjYrKKBdTyfL0ZRWIjxvOez+oJOBTT5St1zpuALbiSZGnuubdjIuBaX37tGg5o9FnnvcnfnuleEaskVrtLnr8X6CAV/RcGYzybaJI3VczPvyoJXYZQihQoUh0AkKDxoBBaH89dXWFw/4Vk+IigRAvtMyUJX4KMOIourSFcu4Zn36EPDuaqvwng3tnd/yozWNTbSkwaH22FxyqTlc74/94Iu8o+FdnxBImZiWZ8OZgoF1+Xc16+5SYRZ8oTt87dBFZA6dhKe4j5wscPCR9aHQgpWBeXnm0GPBJ/3wts0yFBoFuxeiQsWjk5G2lKeYCY1S6iw+DL8ONoASX386JS6IkfUqflQiISOmB1R7MskvGcoXgfehKO50RmOgjMWkRet5fEK5yObUrhPeroeQXvnQz/P7UJ2UMuh2I90MoCFeByU5egPY1+c4Ux1pMecJlLnXGFAdaZ2hpDMKDdGG+pGRk8ougxvEFIIfaRSuscUzQUVGY04HjhOLaAM3QGtjXGFUU1w+bPgaSK2MhRQTWvfUMkdFbATHmoGim6EorWMRxRRSiPhwwWWx0j1kiaa1hFGM50UtdlZrmEPn9bDnPILI6SwZo3IsqLuQOAJKKFDqSMMPvM4eldriZM4/7vl/7o3/P/VKzTAcOMaPUCo1H+36n/AfgDuB+AP4F5P1iPoezqDM6fLWffKLXpHzeiediNv+Z5WsDstVOy7EPrZnXA5g0sihDa6isAHOlcWncbR4q37MGvitXco+2V4rpoz56+hdxj1fznOOBtUBI1l93gbuT55fWWni/mLa+duX2lazFOdnztnOxc73c7Nzu3OH53nnYNOvPXn1l9b/2z9u31ym25f3b4+X3piq5H5qbPy2f79P8vqivw=</latexit>

1.

Dn ( kn )xkn ↵nk = x0 ,(xkj )T

k
n

⇤

↵nk

n = 1, . . . , N ,

k=1
k
k T
n ) + (xn ) ( nn = 1, . . . , N, k = 1, . . . , K<latexit sha1_base64="B1YnWpJkM5p1QBeTu7tnC/EB9zc=">AAAMOXicdVbNb9s2FHe6r07ZR7sddyEatGs7JoizrA0wGGjaoFmxNv1KmqJRalASFXOmSJWkYjuC77tu/87+kh13G3bddYf9KNuxHLuCLT6+3+PTI98Xo1wK69bX/1y69MGHH338yeVPg+XPPv/iyytXv3pldWFifhBrqc3riFkuheIHTjjJX+eGsyyS/DDqPvD44Sk3Vmi17wY5P87YiRKpiJkDq33lvzBj/XYZug53rK1oKLE2ATUk4buCJcENEtoia5eq1Ry+3SMTQRKGQeh435V2za29T3iijLTI+kiE3Oy312/51TdquiR/R3ba6ub5grfdW+Q7L+upt/tkipBVUpeiY1WVbnyWhol2lu6B/yPpns/Jz5PPh0zmndHaoH1lZX1tvXrIPNEcEyuN8fOsfTW4Dn1xkXHlYsmsPWqu5+64ZMaJWPJhEBaW5yzushN+xDZzlnNDM2ZOBExbuyvUcXnCdcadGczKglQs45YmpyK3FXlcVt4dkusAE5Jqg79ypOLWF5dOdM9m1JWxY9EFc0qWWTvIIujLmOvYi5hnvg9znQy6FO/BYdrwrByPw3J/TMygOrLcnFYBNiyf1iazW3bp1nEpVF44ruLRNtNCEqeJD1SSCMNjJwcgWGwEDpjEHWZY7BDOQfXBWGcZU0kZxkxuD8vQGw+y3B4O5/CdGr6zAN+t4bsL8Ec1/NEC/HENf7wA36vhewvw5zX8+QL8RQ1/sQB/WcNfLsD3a/j+Avywhh8uwN/U8DcX8fsPozEcpWU0j8ZTNJ5HiylazKOnU/R0Hu1N0d48mk/RfB41U9TMo3aK2nm0P0X78+jZFD2bR7enaBWpOxy1xPAnYD1FwWBOm9tliKqRCSQQxpB6KphJS66KTLgq9Sx3vlMc+ak448el5KkbV53bQ5Ss2jKhYq2slswxpBxBaxgQJWJOUtHnyWpPJK4zqjOQlEWCytMTYKHUS3HKV5GhcsYO/2WhTqw3T1oHW8oADUnE1g0kb4XOpSwTckADFK4iU7blVaSS9wVKFIUNGetyYgvDfepD85wplDx4UtWEHsoAN0RYsvd0fyRGKrEAhxGhLLT8zulkNjIAlU3KczPCqnyWu4YNhjSwjucjYXSKyTKet3xVn8xTAU2+vbacKfiEG0mmup5rx2xUXIvDb23SoGJ3Rd5aba794BWhTXKFo/T1ayIfoUvPKOjyQU+bZGz1yMz7suDDMEpRQgWaQyASNB5078nm/PEVFsdPeJZ3CFqEwHf6ZKIr8FGHJZOjSGcO4an36K7hXFVHYbwb619/wozWFdbRvTEOt8PilEnLR3y/78m8yN8V2vHJFDETy2p3MFMouC7nvn+NTCLMksdsn78OhgGpYifhKc4DB3tS+Mj6pZCCDYPy/GRwsYHPW+E9GmRoNBN2q8QBC0d7HW0pT0BJzRIqLH4Mf47GL6mPH51SV+SIOjUaCpHQDrMdiu8yCe8ZiuxATjiaG51hK9hjEfml1Xpk4WhkfQr3ST+vRsy986Gf53aytl2tQ7Pv6KQNC5EclOW41MW+OcOZ6lR3OU2kzrnCgO5M7QAhmVFujDbUdYzuUdwyvEEoIfSRSukeUzQXVGQ04khw7FpAGW4HtDLGFUaNg8vvBamJ2MrQQDWtfEMld1TATnhoPFDcRijug3GHIkppJHy4wPIYpV7SRNMqwmimk6IyO8s17OH9ahjNvGCEEjaWEVlWVDcQeAJK6InUEQZfeRy9r7XETpz/b/lX845/f79BAwx3NukBQqV6bVVvwH4A7gfgD+FeP61GzB/oDM7sT6nmxhbdVgO6p13HW76nFexOCxX7Wwg9dydczuCSCKGNW0XgA50ri5vG6STXfZiN47V1JI/LcGU4Yo6yoXUUHX97kXEtGBJcLJsXr5HzxKuNtSbo55sr9zbGV8zLjW8a1xo3G83G3ca9xk+NZ42DRrwULf269NvS78t/LP+1/PfyPyPRS0vjNV83Zp7lf/8HE8tzhg==</latexit>

N X
K
X
⇥

k=1
↵nk

↵nk = 1,0,n = 1, . . . , N,

n = 1, . . . , N, k = 1, . . . , K

Lulli, Guglielmo, and Suvrajeet Sen. "A branch-and-price algorithm for multistage stochastic integer
programming with application to stochastic batch-sizing problems." Management Science 50.6 (2004): 786796.

35

Branch-and-Price Method§

At an optimum (or feasible) of DWD,

<latexit sha1_base64="k+HC2ip5FusUnzdAUfxXs62M3lY=">AAALwnicfVZbb9s2FHa6W6fs0m5v64vQoNhQsEGcZW1eDDRt0KxYm/SSNEVj16AkymJNkSpJ+RJNj/uR+w37E/soy7UcezNsH/J85OHhuTLIBDd2Z+fvjWufff7Fl19d/9rb/Obb776/cfOHN0blOmRnoRJKvw2oYYJLdma5FextphlNA8HOg+Fjh5+PmDZcyVM7zVgvpQPJYx5SC1b/xl9dk6f9Ythpl+//8Cd9+X7odxNqu1RkCa2mnYpRTMr+DvG9olsdWmgWlX73Y04jf0nE9H9ETMu+JKU32yU7bdKNlDXkmPRvbO1s71Qff3XQrgdbrfrzon/Tu4O9YZ4yaUNBjblo72S2V1BteSgYzsgNy2g4pAN2QfcymjFNUqoHHMduP+CyVwyYSpnV0+W1GEqaMkOiEc9MNewV1Y1L/w7AyI+Vxk9av+I2NxeWDy+XxBWhpcEVdQqaGjNNA8hLqU3MVcwx/wuzSQpZko1twpRmaVHTsjitB0uoCgzTo8rTZXHSmCxf2cb7vYLLLLdMhrNrxrnwrfJdxPgR1yy0YooBDTWHgf0woZqGFnHlVQeGKk2pjBAbVByURdcpj2FxUJYr+GEDP1yDHzXwozX40wb+dA3+rIE/W4MfN/DjNfjLBv5yDf6qgb9ag79u4K/X4KcN/HQNft7Az9fg7xr4u6v4oydBDQdxEayi4QINV9F8gear6GiBjlbR8QIdr6LZAs1WUb1A9SpqFqhZRScLdLKKXi7Qy1X0YIFWkXrIUEs0ew7WCQoGtUrfLbqoGilHAoF2iRt5S2nJZJ5yW6WeYdaV7As35ZesVwgW27rq3C1RshrbuAyVNEpQS5FyPmr01Jc8ZH7MJyy6N+aRTWZ1BitFHqHyjDlYlk0EH7F7yFCxpIc7mcuBceoJY6FL4aEz8NDYqWCdrrUxTbmYEg+FK0+l6TgRsWATjhJFoENKh8w3uWYu9SF5RRXiP35e1YQxygDTPjf+8cnpbJlfLfNgjABloeNuTuazmQKobEJ8UqNuI0eaTkviGcuy2WJ0hfk2lnVcVZ/PYw5Jrs91rM7ZnBsIKoeOa2o2Kq6B8Tt7xKvYQ5517rW3f3OC2AQlDqZ09Wu+PkC7XBIwZNOx0lGt9UzNRyJnZTeIUUI5moPHIzQetNH55Zz5cgPz+yzNEh8tguOciT+X5bmow5a5KeIlI5w4jx5pxmRlCu3c2Dz9OdVKVViixjUOt0PjmArDZnx37/k8zz7myrL5FDETiup2UJNLuC5jrn/NVPKp8Z/RU/bWKz2/ip2IxbAHDDvIXWR9yAWnpVd8sgxeGPB5p/uQeCkazZzdKWBgbsk4UYawCCOhaES4wZfix9D3BXHxo2Ji8wxRJ2ck5xFJqEkIzqUC3tME2YGcsCTTKsVVcMc8cFur/cjCGaUTAvcJN68o5s75kM8yM9/br/ah2Scq6kNDJAehGV5XoWvOcKYcqSEjkVAZkyDozsRMEZIpYVorTWyi1ZjgleEUQgkhT2VMjqkkGSc8JQFDguPWHMLwOiCVMjbXsg4udxekJmIrRQNVpPINEcwSDj3hoZoQvEYIHmZhQhClJOAuXKB5iFIvSKRIFWEkVVFeqZ1mCvqwSUVmM7cwQAmr1/A0zasXCDwBIWQgVADiKo8lj5QSuIl1v333177v/n/dJR7I/T1yhlCp/varf8COAHcE+BO4100rivljlcKZk8WovbtPDuSUHCubOM2PlYTecS5D9wohn9wJl1O4JEBo41XhuUBn0uClMZrnuguzOl47F6JXdLfKGXOWDZ2LoPfzVcZtr/TxsGxffUauDt7sbrcxfrm39XC3fmJeb91q3W790mq3HrQetn5vvWidtcLWPxs3N37auLV5uPlh8+OmmS29tlHv+bG19Nn8818qdExd</latexit>

§

K
X

xkn ↵
ˆ nk = x̂0 ,

k=1

K
X

ynk ↵
ˆ nk = ŷn ,n = 1, . . . , N,

k=1
Fractional?

Fractional?

Branching is of the form:KX

xknj ↵nk  bx̂0j c

_

K
X

k
ynj
↵nk  bŷnj c_

k=1<latexit sha1_base64="QyDo+WENQNXq3tL+o4oKdAc7D9A=">AAAL4nichVZbb9s2FHa6Wyfv0m6PeyEaFBs6NoizrA02GGjaolmxNuklaYpGrkFJRxZrilRJypcI+gN7G/a61/2o/ZsdSnJsxx4q2DqH5yOPDnkuPEEmuLHb2/9uXPno408+/ezq5177iy+/+vra9W9eGZXrEE5CJZR+HTADgks4sdwKeJ1pYGkg4DQYPnD46Qi04Uoe22kGvZQNJI95yCyK+tf+8U2e9otht1O+/Z1M+oV8V74dEp+JLGF96VgB7/EVC6U08RNmi0nZL7bflcTXldAj+PjvcxYRP+CDEUA9quUfVD/4gHryI+n0r21ub21XD1llOg2z2WqeZ/3r3k0/UmGegrShYMacdbYz2yuYtjwUUHp+biBj4ZAN4IztZiwDTVOmB1x2O1t3uewVA1ApWD1dnousZCkYGo14Ziq2V1RuKMlNBCMSo8mxkpZU0sXFheXD8yV1RWhZcMmcgqXGTNMA9aXMJuYy5oT/h9kkRV0SxjYBpSEtGloWxw2zhKrAgB5VkVAWRwuD5S3beK9XcJnlFmRYbzPOBbGKuIgiEdcQWjFFhoWa4wGTMGGahRbjzqs+GKo0ZTIq/JCJ/bLwnfHIFvtluYI/XMAfrsEPFvCDNfjjBfzxGvzJAv5kDX64gB+uwZ8v4M/X4C8W8Bdr8JcL+Ms1+PECfrwGP13AT9fgbxbwN5fx+4+CBg7iIlhFwzkarqL5HM1X0dEcHa2i4zk6XkWzOZqtonqO6lXUzFGzik7m6GQVPZ+j56vo/hytIvUhYC3R8BRFR1gwmFX6VuFj1Ug5JhBSnzrOW0pLkHnKbZV6Bqwr6WduyM+hVwiIbVN1bpVYshaWcRkqaZRglmHKEazhUyJ5CCTmE4huj3lkk7rO4EyRR1h5xhxFFiaCj+A2ZqhYssN9mcuBceYJY9GWwsObg4fGTgV0fWtjlnIxpR4WrjyVputUxAImHEsURRtSNgRicg0u9VHziimUPHha1YQxlgHQhBtyeHRcTyPVNA8PI8Cy0HU7p7NRbQBWNiEuzPCr8lkcaDYtqWcsZPXkbudiGWRdV9Vn45ijJncPdq3OYSYNBJNDJzWNGCuuwcPv7lKvEg951r3d2frZKYIJljg8Sle/ZvMDvE6XFAxhOlY6aqyuzbwvcij9IMYSyvFy8HiEFw9es7PNuePLDR4/gTRLCF4RHL8zITNdnos6XDI7injpEI6cRw80gKyOQjs3Ln79KdNKVViixg2ObkeLYyYM1HK379k4z97nysJsiDETimp3aCaX6LoM3P1Vm0SYIU/YMbz2So9UsRNBjOeBBzvIXWS9ywVnpVdcnAx2IOjzrn+PeileNDNxt8AD5paOE2UoRMgJxSLKDf4Y/gG7BkFd/KiY2jzDqJM1yXlEE2YSit9lAr2nKWYH5oSlmVYpbgX3mAduabUes7CmbELRfcKNK4pj53zUD5mZre1X6/CyT1TURwsxOSjLsPsK3eWMzpQjNQQaCZWBRIK3MzVTDMmUgtZKU5toNabYZTiDsITQxzKmh0zSjFOe0gAwwXHXHJVhd0ArY2yuZRNcbi+YmhhbKV6gila+oQIs5WgneqghFLsRio1bmFCMUhpwFy5oeYilXtBI0SrCaKqivDI7zRTaA5OK1CM3McAS1szhaZpXHQh6ApXQgVABEld5LL2vlMCdWPffc6/OHff+aYd6SO7s0hMMleq1V70RdgRxRxB/hO51w4ri+IFK0ZmTOdfZ2aP7ckoPlU2c5YdKot1xLkPXhdALd6LLGbokwNDGrsJzgQ7SYKcxmuW6C7MmXrtnolf4m2UtrLOhexb0vr8suOGVBBvLzuU2cpV5tbPVQf757ua9nabFvNr6rnWj9UOr07rbutf6rfWsddIKN9obnY1fNn5tR+0/2n+2/6qnXtlo1nzbWnraf/8HlbJYDQ==</latexit>

k=1<latexit sha1_base64="LNU/Dz6hy53i/aKOI2Ktdn62+VM=">AAAL+XicjVZbb9s2FHa6W6fs0m6PexEaFBs6NoizrM2LgaYtmhZrk6ZNlqKRG1DSkcWaIlWS8iWCfszehr3udX9k/2aHlBzLsYdNsEXyfOTR4bmHOWfabG39vXbto48/+fSz65976198+dXXN25+86uWhYrgJJJcqjch1cCZgBPDDIc3uQKahRxOw+Eji5+OQGkmxbGZ5tDP6ECwhEXUIOn8xl9l4JiUCuLK8/EJdJGdl8Net3r3iz89L8X76t3QDyjPU3ou7JTDB3wlXErlByk15bRy2/xAOWLN5kNBYz8I2WAEUK/+J/vBf7D3f/S7jlV1fmNja3PLPf7ypNtMNjrN8/L8pnc7iGVUZCBMxKnWZ92t3PRLqgyLOFReUGjIaTSkAzijOznNQZGMqgETve7mfSb65QBkBkZNF/fiVNAMNIlHLNdu2i+dYiv/NoKxn6DgiRTGd9T24dKw4cUCuzIyNLwiTkkzradZiPwyalJ9FbPEf8NMmiEvAWOTglSQlc1YlcfNZAGVoQY1cg5SlYetxeKVTbLbL5nICwMiqq+ZFNw30reO5sdMQWT4FCc0UgwV7EcpVTQy6I6e+2Aks4yKGF2Q8r2qDKzwOC33qmoJf9zCH6/A91v4/gr8WQt/tgJ/3sKfr8APWvjBCvyohR+twF+18Fcr8Nct/PUK/LiFH6/AT1v46Qr8bQt/exV/+CRs4DApw2U0mqPRMlrM0WIZHc3R0TI6nqPjZTSfo/kyquaoWkb1HNXL6GSOTpbRizl6sYzuzVHnqY8Bc4mCF0g6xIRBjVR3ygCzRsYwgHAMiJ15C2EJosiYcaGnwdhMf2aX7AL6JYfENFnnToUpq3WMiUgKLTk1FEPOx9Q+9QWLwE/YBOK7YxabtM4zuJMXMWaeMUOSgQlnI7iLEcoX5LBfZmKgrXhcG5Sl9LCgsEibKYdeYExCM8anxMPEVWRC9yyLhMOEYYoiKENGh+DrQoENfeS8JArxH71wOWGMaQCUz7R/cHhcb/PdNg+VEWJa6Nmbk9mqFgAzG+eXYjTVal/RaUU8bSCvN/e6l8cg79msPlsnDDnZ8tgzqoAZNeRUDC1VN2TMuBqV39shniMPWd6729382TKCCaY4VKXNX7P9IVbZBQZDmI6lihupazEf8gKqIEwwhTIsDh6LsfBg9Z1dzqqv0Kh+H7I89bFEMPzOxJ/x8qzX4ZGZKpIFJRxai+4rAOFUoawZ219/QZWUDkvluMHR7ChxQrmGmm7vPVsX+YdCGpgt0Wci7m6HYjKBpsvB1q9aJJ9q/zk9hjce9g3Od2JIUB+o2EFhPet9wRmtvPJSM9iYoM17wQPiZVhoZuReiQpmhoxTqQnEOOOSxoRp/FH8A/YOnFj/kQkxRY5eJ+qhYDFJqU4JfpdytJ4iGB0YE4bkSmZ4FbxjEdqj7jxGYT3SCUHzcbt2I66t8ZE/5Hp29tydw2KfyvgcJcTgIDTHpiyyxRmNKUZyCCTmMgeBA1ZnoqfokhkBpaQiJlVyTLDLsAJhCiHPREIOqCA5IywjIWCA460ZMsPugDhhTKFE41z2Lhia6FsZFlBJnG0IB0MYyokWagaC3QjBfi5KCXopCZl1F5Q8wlTPSSyJ8zCSybhwYme5RHlg4oZ6ZTeGmMKaPSzLCteBoCWQCRlwGeJgM48hD6XkeBNj/7v21b1n3z9tEw+HezvkBF3FvXbdG2E7IG4HxJ+gee3Sjbh+JDM05mQ+627vkj0xJQfSpFbyAylQ7qQQke1CyKU50eQUTRKia2NX4VlHB6Gx0xjNYt26WeOvvTPeL4ONqibW0dA7C/vfXyXc8iofG8vu1TZyefLr9mYX50c7Gw+2mxbzeue7zq3OD51u537nQedp52XnpBOt3Vp7una09mq9XP9t/ff1P+qt19aaM992Fp71P/8BzEdgLQ==</latexit>

KX

xknj ↵nkbx̂0j c + 1

k
ynj
↵nk

bŷnj c + 1

k=1
K
X

k=1

The second-stage integer variables need branched!

36

Caroe-and-Schultz Branching§

Interesting idea to avoid branching on the second-stage integer variables– At the last iteration K, they used the average for the variable value to branch:

x̃0 =

N
X

pn x Kn,n=1<latexit sha1_base64="VnO3DJp4JJsPwDfJNIlr+gz0BXs=">AAALYnicdZbbbts2GMfd7tQpO7Tr5XYhNCg2FGwQZ1mbGwNNWzQr1iY9pE3R2DUo6VPMmSJVkvIhgp5gT7Pb7Ul2vwfZn7Id27En2OLhR1IfvxMZ5VJYt739z5Wrn3z62edfXPsy2Pjq62++vX7ju7dWFyamN7GW2ryLuCUpFL1xwkl6lxviWSTpJOo/8vxkQMYKrY7dOKdOxs+USEXMHbq612+3nZAJlaOqux22wrYtsm6pWs3qw2GYd1U46qoPv7Hu9c3tre36CVcrzWllszF9XnRvBLfbiY6LjJSLJbf2tLmdu07JjROxpCpoF5ZyHvf5GZ3y3ZznZFjGzZnAt7fuC9Upz0hn5Mx4eSyqimdkWTIQua2rnbJWQxXeBkzCVBv8lQvr3sXJpRP986Xlytjx6JI4Jc+sHWcR1su469nLzHf+H3O9DGspGroeaUNZOS2r8nhaWaI6smQGtSWq8mihsbxll+51SqHywpGKJ9tMCxk6HXqLhokwFDs5RoXHRkDBYdzjhscOdg/qD8Y6y7hKynbM5X5Vtr3wqJb7VbXCHy/wx2v4wQI/WMOfLvCna/izBf5sDT9c4Idr+MsF/nINf7XAX63hrxf46zX8eIEfr+EnC/xkDX+/wN9f5g+fRFMcpWW0SuM5jVdpMafFKh3M6WCVDud0uErzOc1XqZlTs0rtnNpVOprT0So9n9PzVbo/p7WnPibkEkPP0XWEhMGdNnfKNrJGJhBAKNvM14KlsCRVZMLVoWfJ+ZR66pvinDqlpNRNs86dCilrYZpQsVZWS+44Qi5EDh2HSsQUpmJEyd2hSFxvkmcwUhYJMs9QoMvRSIoB3UWEyiU5/JeFOrNePGkdZCkDZG4RWzeW1Go7l/JMyDELkLiKTNmWXyKVNBJIUQwyZLxPoS0M+dDHyiuisPDR8zonDJEGyITChodHx5NhYT0sgDIipIWW3zmbtSYCILNJeSFGu06f5YHh44oF1lE+GdxqXkyjvOWz+qydCqzkz6GWMwXNeiPJVd/32mk3Mq6F8lu7LKi7+yJv3W1u/eIXohFSHFTp89dsfITjbGmBPo2H2iRTqSdiPpQFVe0oRQoVOBwCkeDgwTE325xXX2Gh/pCyvBfiiBD4ziicrRV4r8OUmSrSJSUceYseGCJVq8J4My5+/Tk3Wtesp4dTDrND4pRLS5N+v+9Zu8g/FtrRrAmfiWW9O4gpFEyXkz+/JiKF3IbP+DG9C6ogrH0noRT6gGLPCu9ZvxdS8CooLzSDGwBs3mo/YEGGg2bW3SqhYOHYsKctowQ1qXnChMWP408fCy6Z9x+dMlfk8Do1KQqRsB63PYbvcgnrGYboQEw4lhudYSvYYxH5qfV8ROGk5CMG80nfrku0vfGxPuV2Nrdbz8Nh39NJFxIiOBjPcfuJ/eEMY6qB7hNLpM5JocDpzOwYLpkxMkYb5npGDxluGV4gpBD2VKXskCuWCyYyFhECHLsWWAy3A1YL4wqjps7l94LQhG9lOEA1q23DJDkmICcsNC0YbiMMF6e4x+ClLBLeXSB5jFQvWaJZ7WEs00lRi53lGvLQqC4mLT8wQgqbjhFZVtQ3EFgCi7AzqSMUPvM49lBriZ04/9/zr+Y9//55hwUo7u2yN3CV+rVXv4F9Ae4L8Ccwr2/WJdqPdAZjjua15s4e21djdqhdz0t+qBXkTgsV+1sIuzAnTM5hkgiujVtF4B2dlMVNYzCLde9mU39tncpO2d6sJp2TaGidRp0fL3fcCqoQF8vm5WvkauXtzlYT9Ze7mw92plfMa43vG7caPzWajfuNB41fGy8abxpx44/Gn42/Gn8H/24EGzc2bk6GXr0ynXOzsfRs/PAf2NkqCg==</latexit>– For fractional integer variables,<latexit sha1_base64="+9poqrbxizev2ijFQx379x6nIWI=">AAALtnichZbrb9s2EMCdbt06Zetj+7gvQoNiQ8cGcZa1+WKgaYtmBdqkj6QtGnkBJZ1s1nyoJOVHBP2h+7R/ZUdKjuXYwwRbfPzI0/HueGScc2bszs7fG9e++vr6N9/e+C7Y/P6Hm7du3/nxvVGFTuA0UVzpjzE1wJmEU8ssh4+5BipiDh/i0VPHP4xBG6bkiZ3l0Bd0IFnGEmqx6/z2bHpeys9VGHH4gq+MK6XDyDKeQjmtzssdx7TvDkL/RF8KmoZRzAZjgLrVkLmowf+KCn8Lu+e3t3a2d/wTrla6TWWr0zyvz+8E96JUJYUAaRNOjTnr7uS2X1JtWcKhCqLCQE6TER3AGd3LaQ6aCKoHTPa624+Y7JcDUAKsni2PxaqkAgxJxyw3vtovvWmr8B7CNMxQ5UxJG/re9uTSstHFkrgysTS+ok5JhTEzEaM8Qe3QXGWu87+YHQqUJWFih6A0iLIpq/KkqSxRFRvQY+/dqjxuNZaXbLP9fslkXliQSb3MrOChVaGLkjBlGhLLZ1ihiWZo4DAZUk0Ti7EU+A8mSggq0zJKKD+oysgpj9XyoKpW+LMWf7aGH7b44Rr+osVfrOEvW/zlGn7U4kdr+JsWf7OGv23xt2v4uxZ/t4aftPjJGv6hxT+s4Z9a/NNV/uR53OA4K+NVmixoskqLBS1W6XhBx6t0sqCTVZovaL5K9YLqVWoW1KzS6YJOV+nFgl6s0oMF9ZH6DDCXaHiFXceYMKhV+n4ZYdYQDDcQlhFxtWBpW4IsBLN+6xmwLk2fuSa7gH7JIbNN1rlfYcpqTWMyUdIoTi3FLRdiXp6FkiUQZmwK6YMJS+2wzjM4khcpZp4Jwy4LU87G8AB3KF/Sw32ZyYFx6nFjUZcywNOAJcbOOPQiazMqGJ+RABNXIaTpOREZhynDFEVQB0FHEJpCg9v6KHlFFRI+feVzwgTTAOiQmfDo+KQeFvphARojxrTQcysn81atAGY2zi/ViHz6LA81nVUkMBbyenCvezkN8p7L6vN2xlCSO9t6Vhcw7405lSPXa5puzLgGjd/bI4HvHrG896C7/YcTBFNMcWhKl7/m42M8IpcEjGA2UTpttK7VfMILqKI4wxTK8HAIWIoHDx6d88U58xUGzR+CyIchHhEMvzMN57ICF3U4ZW6KbMkIx86jhxpAelNo58b2119RrZRnQzVpOLodNc4oN1D3u3XP20X+pVAW5k2MmYT71aGaTKLrcnDnV61SSE34kp7Ax6AKQh87KWRoDzTsoHCR9bngjFZBeWkZvFWgz3vRYxIIPGjm3b0SDcwsmQyVIZBijSuaEmbwR/EPeD/gxMWPyogtcow6WRcFS8mQmiHB71KO3tMEdwfuCUtyrQQuBddYxG6qn4+7sC7plKD7uGv7EtvO+SgfcjOfe+7n4WE/VOk5aoibg9Acb1SJO5zRmXKsRkBSrnKQWODpTMwMQ1IQ0FppYodaTQjeMpxCmELIC5mRIypJzggTJAbc4LhqhsLwdkC8MrbQsgkutxbcmhhbAg9QRbxvCAdLGOqJHmoKgrcRgpexZEgwSknMXLig5gmmek5SRXyEEaHSwqstcoX6wNQXdcsNjDGFNWOYEIW/gaAnUAgZcBVj4TKPJU+U4rgS6/777tV96N6/75IAi4d75BRDxb/2/RuxK5C7AvlzdK9r+hLbT5VAZ04Xte7uPjmQM3Kk7NBpfqQk6p0VMnG3EHLpTnQ5RZfEGNp4qwhcoIM0eNMYz/e6C7MmXntnvF9GW1XdWe+G3lnc/+Vqx92gCvFi2b16jVytvN/d7mL9zd7W493minmj83PnbufXTrfzqPO482fndee0k3T+2bi+cXPj1ub+5l+bsDmoh17baOb81Fl6NvN/Af5ZRmg=</latexit>_

xnj  bx̃0j c– For continuous variables,xnj  x̃0j<latexit sha1_base64="36nF0mN3J+31OctIcPXK7D6k+bI=">AAALqHicdVZZb9w2EJZ7pnKPpH3sixAjaJHShtd1E78sECdB3ACJncOO01gLg5JGu8xSpEJSe1jQj+xjf0lfO6S0Xq21FXY15HzkaDgXJ8o502Z395+Nzz7/4suvvr71jb/57Xff/3D7zo/vtCxUDGex5FK9j6gGzgScGWY4vM8V0CzicB6Nn1j8fAJKMylOzTyHQUaHgqUspgZZl7fHs8tSfKyCkMOnIDSMJ1DOqstyF3nbQQi5ZlwKP3BP+KmgSRBGbDgBqGcNspAy7Er57VrK5e2t3Z1d9wTdQa8ZbHnN8+ryjn8vTGRcZCBMzKnWF73d3AxKqgyLOVR+WGjIaTymQ7ig+znNQZGMqiET/d7OQyYG5RBkBkbNV9fiUNAMNEkmLNduOCidMavgHoJJkEqFf2ECx21vLg0bX62IK2NDoxvqlDTTep5FKC+jZqRvYpb5f5gZZShLwNSMQCrIyoZW5WkzWEFlpEFNnD+r8qQ1WT2ySQ8GJRN5YUDE9THTggdGBjYugoQpiA2f44DGiqGBg3hEFY0NRo/vPhjLLKMiKcOY8sOqDK3yOCwPq6qDP23hT9fgRy38aA3+vIU/X4O/aOEv1uDHLfx4Df66hb9eg79p4W/W4G9b+Ns1+GkLP12Dn7fw8zX4hxb+4Sb++FnUwFFaRl00XqJxFy2WaNFFJ0t00kWnS3TaRfMlmndRtURVF9VLVHfR2RKdddGrJXrVRQ+XqIvUp4C1RMFLZJ1gwaBGqvtliFUjY5hASENiR/5KWoIoMmZc6mkwtjBf2Cm7gkHJITVN1blfYclqbWMilkJLTg3FlAuwEs8DwWIIUjaDZHvKEjOq6wyu5EWClWfKkGVgxtkEtjFD+Yoe9stMDLVVj2uDupQ+1n8WazPn0A+NSWnG+Jz4WLiKTOi+FZFymDEsUQR1yOgYAl0osKmPkjuqkODJS1cTplgGQAVMB8cnp/WywC3z0RgRloW+PTlZzGoFsLJxfq1G6MpneaTovCK+NpDXi/u9622Q921VX8xThpLsbdY3qoAFN+JUjC1XN2ysuBqN398nvmOPWd7f7u38YQXBDEscmtLWr8X6CC/FFQFjmE+lShqtazUf8wKqMEqxhDK8HHyW4MWDl+XicNZ8hUbzB5DlowCvCIbfmQULWb6NOtyyMEW6YoQT69EjBSCcKZR1Y/vrL6mS0mEjOW1wdDtqnFKuoebbcy/mRf6pkAYWU4yZmLvToZpMoOtysPdXrVJAdfCCnsJ7v/IDFzsJpGgPNOywsJH1seCMVn55bRnsI9Dn/fAR8TO8aBbsfokGZoZMR1ITSHDEJU0I0/ij+AdsCzix8SNTYooco07UpGAJGVE9IvhdytF7imB2YE4YkiuZ4VHwjEVkt7r9mIU1pTOC7uN27ijOrfNRPnYWi72Xbh9e9iOZXKKGmByE5thDxfZyRmeKiRwDSbjMQSDB25noOYZkRkApqYgZKTkl2GVYhbCEkOciJcdUkJwRlpEIMMHx1AyFYXdAnDKmUKIJLnsWTE2MrQwvUEmcbwgHQxjqiR5qCMFuhGD7FY8IRimJmA0X1DzGUs9JIomLMJLJpHBqZ7lEfWDmSD2zCyMsYc0almWF60DQEyiEDLmMkNjKY8hjKTmexNj/gX31Htj373vER/Jgn5xhqLjXgXsjbAniliD+DN1rp47i/InM0Jmz5ai3d0AOxZwcSzOymh9LgXqnhYhtF0Ku3Ykup+iSCEMbuwrfBjoIjZ3GZJHrNsyaeO1f8EEZblU1s86G/kU0+OUm465fBdhY9m62kd3Bu72dHo5f72892mtazFvez95d71ev5z30Hnl/eq+8My/2/vb+3fA2Njbvb77aPN/8q1762Uaz5ydv5dmM/gO+5EGP</latexit>

✏

_

xnj

xnj

bx̃0j c + 1

x̃0j + ✏Great, the branchings are applied to ALL scenarios!
37Can we do better?
Observations
1. Carøe-and-Schultz (CS) branching uses an arbitrary point (i.e., averagesolution) to branch.
2. DWD solution point provides the Lagrangian dual bound.
• Let x̂0 be the DW solution point (vs. the average point x̃0 by CS) at somenode.
• Assume that x̂0 6= x̃0 .
• When branching on continuous variables at the CS point, one of the child nodes
would still contain the DW solution point.
<latexit sha1_base64="noa13viOc4ijfhxfVwdHOKw66jQ=">AAAOf3icdVdbcxu3FabtXpJtq8TtY1+QyJ44GYgjqnbiPnDGsjRxPWPLcSRHnogcDXYXS6LCAmsAy4t2+Df6u/raH9OZfsAuyaXIciQCOB9wcHDujAsprDs8/M+9+w9+89vf/f6zz6M//PFPe198+fDPv1hdmoR/SLTU5mPMLJdC8Q9OOMk/FoazPJb8Mr458fjlhBsrtLpw84IPczZSIhMJcyBdP7z/r0HMR0JV+TzWs0X1LrbcTAJoFxEhDcpVmXPDHPc0UIXjOTlhphroBT9gKj04T8aldLfkycn5tyQ2TCVjoUaktNwSpggzsXCGmTkptFCOPBFd3qWEQTY24sRqWfo7vyVON6e7rZtOL09XWxoGhdETkYK5G3Pyho1wZiRwUVoySWJdqtQzGHCVbgofKPVjsVq/0N8jbjfe94Y78mgwZq6aLa4PH5GYh8tOL+/K8mRiuwFaPqcmPxo4IVO+PD0nXjXM4XTOidIpbz/x2FpICS6sfSkZKP6JtPm0z1yOuWrpGvIkWjmhSl1aMmFGMLiB9Vd64U7Oa7koNnKis0DESZkGYSyZ6hJzi8tkYMSE2v3gtgwvuXVE6ik3tdZJc8gZzhuOSjuvO5F7m/HVDsizkn1lq6UZrr/cP+wehg/ZnvSayX6n+fx0/TD69yDVCXSoXCKZtVe9w8INK2acSCTsOoArFiy5gX2u2NOCFdzQnBnYvt/r/iDUsBpxGMaZ+eZeTBXLuaXpRBQ2TIdVCLwFeQwwJZk2+IfBA7V9uHLi5naDXZU4b5RNGsutnecx+OXMje1dzBP/H+bGOXgpPoVGteF51YyL6qKZbKB6Hd4bsX7nyS57PqyEKkrHVVI/Myulj02fQ0gqDE+cnGPCEiOgYPgRMyxxyDRRuDDReY60UA0SJo8X1cALj2l1vFhs4act/HQH/qqFv9qBv27hr3fgb1r4mx34WQs/24G/b+Hvd+A/t/Cfd+DnLfx8B37Rwi924Jct/HIH/msL//Uu/vLHuIHjrIq30WSNJttouUbLbXSyRifb6HSNTrfRYo0W26hZo2YbtWvUbqOzNTrbRm/X6O02erxGg6eecuQSw9+C9K7wNUSb76oBskYuEEAYB9TPoo2w9PXG5zGct9z5In7VpLVhJXnmmqzz3SJ63D4mFJIuEi1zDCFHUErmRImEk0zMeHowFakb13kGO2WZIvNMBUiOz6SY8ANEqNyQw9+M3Gq9eNI6yFJF6BVEYt1c8v7AuYzlQs5phMRV5sr2PYtM8plAiqKQIWc3qM2l4T70wXlLFEpO3oacMEUaQAkQlpy9u6i3kbAtgjJipIW+fzldrmoBkNmkXIkxCOmzemXYfEEj63hRb+73Vsd40fdZfbnOBDj5zqfvTMmX1FgydeOptiEj41oov/+URoF8I4r+Qa/7zDPiM6Q4qNLnr+X+GA3UBoMbPp9qkzZS12K+lCVfDOIMKVSgOEToRVB6M7F8nFdfaX1Z5nkxJigRAvfMyJJX5L0OR5aqyDaU8M5b9BVKqAqqMN6M7dvfMqN1wMZ62uAwOyTOmLS8pvt3L9dl8anUji+X8JlEhtdBTFR0bgru61ctEmEWLdUF/xihHQq+k/IM+oBiR6X3rH+WUrBFVK00g54TNu8PXtAoR6FZkvsVFCwcnY61pTzFTGqWUmHxx/DPP6Fbo95/dEZdWcDrVD2UIqVjZscU9zIJ6xmK6EBMOIouIsdT8MYy9kfDeURhPbIZhfmkX4cRa2988OeFXZ69DudQ7Mc6vYaECA7KCvTbiS/OMKaa6BtOU6kLrjCgOlM7h0vmlBujDXVjo6cUXYYXCCmEvlYZPWOKFoKKnIaWEq8WYIbugAZhXGlU41y06dMgAwqopsE2VHJHBeSEhZqBohuhaNWTMYWXUrTQNkieINVLmmoaPIzmOi2D2HmhIQ+fhaFe+Y0xUlizR+R5GToQWAJM6EjqGIPPPI6+1FriJc7/P/dfve/999+OaITh+6f0g28f/dfz8A3YD8D9APxHmNcvw4j1ic5hzNl61jt6To/VnJ5p59s+jApyZ6VKfBdCV+aEyRlMEsO10VVE3tG5sug0JstY927W+Gv/Sg6rwf6iJtbR0L+Kh9/cJXwdLchmexaiKfwW8IWAq4kwWnmezU+Eq96wehwNVvuuMAm/svox4v+rZ4dfIdsk3p4yM2gNa/LRMxp97vNd3ycrI0bjeuZ00T/CGGvndF6TArP93jBaPI4q3wKvZUIP3Lvb8W5Pfjnq9jB/f7T/4qjphj/r/LXzdedJp9f5ofOi84/OT50PneT+fx/sP6APDvbu7X2z1907rLfev9ec+Utn47P39/8BEnNCSg==</latexit>• Best lower bound in the tree would not be improved in the CS branching.

38

New Branching Approach
We use the DWD solution point to branch:
x̂0 =

K
X

xkn ↵
ˆ nk

v.s.

x̃0 =

• For fractional integer variables,_xnj  bx̂0j c• For continuous variables,xnj  x̂0j

pn x Knn=1

k=1<latexit sha1_base64="Via0AR0LxrUyNGgmwwH4jTn5KMQ=">AAAOaXiclVdbj9y2FZ7YvSRqvY1boC3aFyYLo7nQi52tnRgFBvBlYdeIvY6TddbIarKgJGrEDEXKJDWXFQT0J/a1v6AP/RP9KGl2NDtTFBnsDsnzkYfn8FwnKqSw7vDwX+/duPmzn//il+9/EPzq17f2fvPh7d9+Z3VpYv4m1lKbtxGzXArF3zjhJH9bGM7ySPKzaPrE42czbqzQ6tQtCz7O2USJVMTMgXRx+8Y/zjgpLScu4+T47JhYLUsPkUIL5YjTJDJMxdnfAkLCiE+EqpgUE1VjTUgVNiJUhid1mDFXLeqLQzIioS3zi2o6GtY/fEUWF+qHKfFwyGSRMb9sj4fvSpaQUPLUfUJCxxeumh3Yg3oFOCETvslTeZ4npLhQDd+vSGjEJHOfevG4SvrCrSUWjufikneX+hV5qg1JDYu9rkwS6Mon3JAZM4Lh8Sxt925pTHBtpX6svdTv8JVKDU4r3atDj5iG2G3vVInEZMZ5u7rGaPJ/GJHPybCVZlvBvjqxVk6oUpf2J6vRv/Uu7imskFr9NA36PD7f5NEXfGWolU0uPtw/PDhsPmR7Muwm+4Pu8/XF7eCfYaLjMufKxZJZez48LNy4YsaJWMLIIfy5YPGUTfg5u1ewghuaM4MXGA0PvhRqXE24zrkzy829mCqW482SmShsMx1XjX/X5A7AhKTeafDKpKH2D1dOTC832FWx8xbYpLHc2mUegV/OXGavY574vzCX5eCl+ByRqg3Pq26sq9NusoHqyHIza6K8rl71Fpsqu/TBuBKqKB1XcatmWkof9j5bkEQYHju5xITFRuCBSZwxHzbIKUFzYazznMGeYczko7oKvfCYVo/qegs/7uHHO/BnPfzZDvx5D3++A3/Rw1/swE96+MkO/HUPf70D/6aHf7MD/7aHf7sDP+3hpzvwsx5+tgP/vod/fx1//DTq4Citom00XqPxNlqu0XIbna3R2TY6X6PzbbRYo8U2atao2UbtGrXb6GKNLrbRyzV6uY0+WqONpx5z5BLDX4L0CgmDOW0+q0JkjVwggDCG1M+CjbDkqsx9HsN5y50v1+ddWhtXvqh1WeezOrjTPyYUUjUKLXMMIUdQn5dEiZiTVCx4cncuEpe1eQY7ZZkg88wFSCiQUsz4XUSo3JDD3yzUxHrxpHWQpQrQFYjYuqXko9C5lOVCLmmAxFXmyo48i1TyhUCKopAhZ1NObGm4D33fD1wXhZInL5ucMEcaQKEUlpy8Om23kWZbgMeIkBZGXnO6WrUCILNJeSVG1zQ8M2xZ08A6XrSbR8OrY7wY+ay+WqcCnHyPM3Km5CtqJJmaeqrtyMi4Fo8/ukeDhjwVxeju8OC+Z4TmAmWHJz5/rfZHaJU2GEz5cq5N0kndivlYlrwOoxQpVPiCKhIUHrRQK+X885UWz094XmQEJULgngVZ8Qq81+HI6inSjUd45S36zHCumqcw3oz9218yo3WDZXre4TA7JE6ZtLyle71X67J4V2rHV0v4TCwb7SCm73JMwX39akUizJIX7JS/DdAWNL6T8BTvgYedlN6zfiylYHVQXb0MukvYfBQ+pEGOQrMijyo8sHB0nmlLeYKZ1CyhwuKP4Z+ja5DU+49OqSsLeJ1qh1IkNGM2o7gXLcIlijWiAzHhaGF0DlWgYxn5o815RGE7sgWF+aRfNyPW3vjgj9ZjdfaiOYdin+nkAhIiOCgr0FnHvjjDmGqmp5wmUhdcYUB1pnYJl8wpN0Yb6jKj5xRdhhcIKYQ+Vyk9YYoWgoqcNo0VtBZghu6ANsK40qjOuWjXlEEGFFBNG9tQyR0VkBMW6gaKboSiKY8zCi+lkfDuAsljpHpJE00bD6O5TspG7LzQkIcvmqFd+Y0RUli3R+R52XQgsASY0InUEQafeRx9rLWEJs7/P/Bfwy/891+PaIDhi3v0DVyl+XrQfAP2A3A/AH8K8/plM2L9ROcw5mI9Gx49oI/Ukp5ol3nJT7SC3Gmpmo6bXpkTJmcwSQTXRlcReEfnyqLTmK1i3btZ56+jczmuwv26JbbRMDqPxn+5Tvg4qMlme9ZEU6QXbSHgaiaMVp5nlS89+Xw4ru4E4dW+c0ya31OjCPH/0f3Dj5BtYm9PiZ8NeUc+uk+DD3y+G/lk1fwSaWZOF6MjjJF2TuctqWG2PxwH9Z2g8i3wWib0wMPrHe/25LujgyHmr4/2Hx513fD7gz8PPh58MhgOvhw8HPx98PXgzSC+8e+bt27+/uYfbv1n7/beH/f+1G698V535neDjc/e/n8BMewyxw==</latexit>

N
X

✏

_

xnj

xnj

!

(1)

bx̂0j c + 1(2)

x̂0j + ✏(3)

Finite termination has been proved for zero epsilon!
39Some Details of Implementation§

Algorithmic Details:– Upper bounds are evaluated at a given point from each method, after rounding any fractional
integer variable values.
– No warm- or hot-start for node subproblem solutions– Gap tolerance: 0.01%– 2-hour wall clock time limit§

Computation Settings:––––

Implemented in DSP with Coin-ALPS
The master was solved by CPLEX-12.7.0.
Subproblems were solved in parallel using MPICH.
Ran on Argonne's Bebop cluster (Intel Broadwell 36 cores)

40

SIPLIB Test Instances§

SIPLIB: publically available test library for stochastic integer programming– http://www2.isye.gatech.edu/~sahmed/siplib/– DCAP: complete recourse, first-stage mixed-integer and second-stage pure integer• Number of scenarios: 200, 300 and 500– SSLP: complete recourse, first-stage pure integer and second-stage mixed-integer• Number of scenarios: 5, 10, 15, 50 and 100
Name
dcap233 200
dcap233 300
dcap233 500
dcap243 200
dcap243 300
dcap243 500
dcap332 200
dcap332 300
dcap332 500
dcap342 200
dcap342 300
dcap342 500# Rows
3006
4506
7506
3606
5406
9006
2406
3606
6006
2806
4206
7006

# Columns
5412
8112
13512
7212
10812
18012
4812
7212
12012
6412
9612
16012

# Integers
5406
8106
13506
7206
10806
18006
4806
7206
12006
6406
9606
16006

Name
sslp 5 25 50
sslp 5 25 100
sslp 15 45 5
sslp 15 45 10
sslp 15 45 15
sslp 10 50 50
sslp 10 50 100# Rows
1501
3001
301
601
901
3001
6001

# Columns
6505
13005
3465
6915
10365
25510
51010

# Integers
6255
12505
3390
6765
10135
25010
50010

41

Numerical Results - DCAP (Easy)
Instance
dcap233 200

dcap233 300

dcap233 500

dcap243 200

dcap243 300

dcap243 500<latexit sha1_base64="(null)">(null)</latexit>§§

Method
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW

UB
1842.09
1834.71
1834.58
1671.87
1644.35
1644.25
1775.76
1737.61
1737.52
2336.112322.672322.502574.202559.412559.192193.462167.412167.39

LB
1833.43
1834.53
1834.541642.76
1644.191644.191736.69
1737.50
1737.52
2321.442322.482322.472556.592559.122559.192165.402167.212167.31

Gap (%)
0.47
OPT
OPT
1.74
OPT
OPT
2.20
OPT
OPT
0.62
OPT
OPT
0.68
OPT
OPT
1.27
OPT
OPT

Nodes
Solved
1630
29
31
377
57
25
165
51
29
711
137
33
520
29
31
241
33
43

Nodes
Left
1629
0
0
376
0
0
164
0
0
684
0
0
519
0
0
240
0
0

Time
TO
99
93
TO
751
253
TO
589
446
TO
1155
178
TO
195
196
TO
394
660

BNP cannot solve any instance in 2-hour time limit.
New approach tends to solve fewer node subproblems and thus faster than CS.

42

Numerical Results - DCAP (Hard)
Instance
dcap332 200

dcap332 300

dcap332 500

dcap342 200

dcap342 300

dcap342 500<latexit sha1_base64="(null)">(null)</latexit>§§

Method
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW

UB
1098.541060.75
1060.701313.851252.811252.76
1695.66
1589.27
1588.91
1691.89
1619.64
1619.56
2136.25
2067.61
2067.522028.811904.92
1904.73

LB
1059.091060.66
1060.59
1250.841252.68
1252.631586.941588.32
1588.66
1618.091619.48
1619.472065.512067.412067.43
1902.89
1904.61
1904.53

Gap (%)
3.59
OPT
OPT
4.79
OPT
OPT
6.41
0.05
0.01
4.36
OPT
OPT
3.31
OPT
OPT
6.20
0.01
OPT

Nodes
Solved
626
395
89
277
395
89
135
232
223
524
443
177
301
151
125
145
99
95

Nodes
Left
627
0
0
274
0
0
134
213
166
523
0
0
300
0
0
144
72
0

Time
TO
1661
349
TO
4481
832
TO
TO
TO
TO
2496
793
TO
2437
773
TO
TO
1699

CS also failed to solve some instances in 2-hour time limit.
Clear to see that the new approach outperformed CS

43

Numerical Results - SSLP
Instance
sslp 5 25 50

sslp 5 25 100

sslp 10 50 50

sslp 10 50 100

sslp 10 50 500

sslp 10 50 1000

sslp 10 50 2000

sslp 15 45 5

sslp 15 45 10

sslp 15 45 15<latexit sha1_base64="(null)">(null)</latexit>

Method
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW
BNP
CS
CS+DW

UB
-121.6-121.6-121.6-127.37-127.37-127.37-364.64-364.64-364.64-354.19-354.19-354.19-349.136-349.136-349.136-351.711-351.711-351.711-347.263-347.263-347.263-262.4-262.4-262.4-260.5-260.5-260.5-253.601-253.601-253.601

LB-121.6-121.6-121.6-127.37-127.37-127.37-364.64-364.64-364.64-354.19-354.19-354.19-349.136-349.136-349.136-351.711-351.711-351.711-347.263-347.263-347.263-262.4-262.4-262.4-260.5-260.5-260.5-253.601-253.601-253.601

Gap (%)
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT
OPT

Nodes
Solved
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

Nodes
Left
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Time
1
1
1
1
1
1
31
31
30
36
37
36
792
786
788
1964
2275
2544
2024
2006
2008
4
4
4
101
101
101
267
267
267
44

Summary and Future Research Questions§

Dual decomposition is the Lagrangian relaxation applied to SMIP
– Not just that.

§

Allowing to exploit special structures embedded in SMIP
– Benders-type cuts
– Inexact interior point methods and other bundle methods– Any better dual search methods, customized to this setting?

§Parallel computing– Asynchronous communication significantly reduces the solution time.

§

Hope for global optimality– Specialized scalable branching method!
– Other branching ideas? Generalized disjunctions, strong branching, etc.

§

Other questions– Scenario partitioning/grouping– Primal heuristics– Extended to multi-stage stochastic programs

45

Questions?
§ Contact:– Kibaek Kim, kimk@anl.gov§ Acknowledgements:– U.S. Department of Energy, Office of Science, ECRP
– U.S. Department of Energy, Office of Science, MMICCS– U.S. Department of Energy, Office of Electricity, GMLC

46