Parallel PIPS-SBB
Multi-level parallelism for 2-stage SMIPS
Lluís-Miquel Munguia, Geoffrey M. Oxberry, Deepak Rajan, Yuji Shinano

Our contribution
PIPS-PSBB*: Multi-level parallelism for Stochastic Mixed-Integer programs•

Fully-featured MIP solver for any generic 2-stage Stochastic MIP.

•

Integral parallelization of every component of Branch & Bound.

•

Handle large problems: parallel problem data distribution.

•

Distributed-memory parallelization.

•

Novel fine-grained load-balancing strategies.

•

Actually two(2) parallel solvers:• PIPS-PSBB• ug[PIPS-SBB,MPI]...

Two levels of nested parallelism (B & B and LP relaxations).

•



...

...

*PIPS-PSBB: Parallel Interior Point Solver – Parallel Simple Branch and Bound2

Introduction•••

MIPs are NP-Hard problems: Theoretically and computationally intractable.
LP-based Branch & Bound allows us to systematically search the solution space bysubdividing the problem.
Upper Bounds (UB) are provided by the integer solutions found along the Branch &Bound exploration. Lower Bounds (LB) are provided by the optimal values of the LPrelaxations.

Upper bound (UB)
GAP(%)UB − LB· 100
UBLower bound (LB)3

Coarse-grained Parallel Branch and Bound•

Branch and bound is straightforward to parallelize: the processing of subproblems isindependent.

•Standard parallelization present in most state-of-the-art MIP solvers.

•Processing of a node becomes the sequential computation bottleneck.

•Coarse grained parallelizations are a popular option: Potential performance pitfalls
due to a master-slave approach, and relaxations are hard to parallelize.

Coarse-grained Parallel Branch and Bound• Branch and Bound exploration is coordinated by a special process or thread.
• Worker threads solve open subproblems using a base MIP solver.
•Centralized communication poses
serious challenges: performancebottlenecks and a reduction inparallel efficiency:– Communication stress at rampup and ramp-down.
– Limited rebalancing capability:
suboptimal distribution of work.
– Diffusion of information is slow.

Currently available coarse-grained parallelizations•••

Coarse-grained parallelizations may scale poorly.
Extra work is performed when compared to the sequential case.
Information required to fathom nodes is discovered through the optimization.

•Powerful heuristics are necessary to find good feasible solutions early in thesearch.
6

Branch and Bound as a graph problem•

We can regard parallel Branch and Bound as a parallel graph exploration problem•Given P processors, we define the frontier of a tree as the set of P subproblems
currently being open. The subset currently processed in parallel are the active nodes.

•We additionally define a redundant node as a subproblem, which is fathomable if theoptimal solution is known.

•The goal is to increase the efficiency of Parallel Branch and Bound by reducing thenumber of redundant nodes explored.

Our approach to Parallel Branch and Bound•

In order to reduce the amount of redundant nodes explored, the search must fathom
subproblems by having high quality primal incumbents and focus on the mostpromising nodes.

•To increase the parallel efficiency by:– Generating a set of active nodes comprised of the most promising nodes.
– Employing processors to explore the smallest amount of active nodes.

•Two degrees of parallelism:– Processing of nodes in parallel (parallel LP relaxation, parallel heuristics, parallel
problem branching, …).
– Branch and Bound in parallel.

...

Fine-grained Parallel Branch and Bound•

The smallest transferrable unit of work is a Branch and Bound node.

•Because of the exchange of nodes, queues in processors become a collection ofsubtrees.

•This allows for great flexibility and a fine-grained control of the parallel effort.

•Coordination of the parallel optimization is decentralized with the objective ofmaximizing load balance.

All-to-all parallel node exchange••Load balancing is maintained via
synchronous MPI collectivecommunications.
The lower bound of the most promising K
nodes of every processor are exchanged
and ranked.

Solver 00

12

3

56

8

15

1620

21

22

•0

•

Node transfers are synchronous, while thestatuses of each solver (Upper/lower
bounds, tree sizes, times, solutions, …)
are exchanged asynchronously.

7

910

11

12

13

14

17

18

19

1

2

1

3

K=3, N=3

15
16
4
7
9
10
15
16
4
7
9
10
0
1
2
3
5
6
8
15
16
4
7
9
10
11
12
13
14
17
18
19
Solver 02111213
14
17
18
19
Solver 0
11112
13
14
17
18
19

The top K out of K ·N nodes are selected
and redistributed in a round robin fashion.
Because of the synchronous nature of theapproach, communication must be usedstrategically in order to avoid parallel
overheads.

4Solver 2

Gather top K · N · N bounds(K nodes · N solvers · N solvers)0•

Solver 1

253

658

68

Solver 0Sort, and select top K · N bounds

000

1

1

1

22

2333

4445565667778

Solver 2
Solver 1
Solver 088

Redistribution oftop K · N nodes
Solver 0

Solver 2

Solver 10361516202122

1n47

Node estimation/bound

9n2581011121314171819

Node information

Stochastic Mixed Integer Programming: an overview•

Stochastic programming models optimization problems involving
uncertainty.

•We consider two-stage stochastic mixed-integer programs (SMIPs) withrecourse:– 1st stage: deterministic “now” decisions– 2nd stage: depends on random event & first stage decisions.

•Cost function includes deterministic variables & expected value function of
non-deterministic parameters

Stochastic MIPs and their deterministic equivalent•

We consider deterministic equivalent formulations of 2-stage SMIPs under thesample average approximation•This assumption yields characteristic dual block-angular structure.

min c t xs.t.
⎡AT2

TNW1
W2...

}

T1...

⎤⎡ ⎤ ⎡ ⎤Ax0b0 Common constraints⎢ T1 W1⎥⎢ x1 ⎥ ⎢ b1 ⎥⎢⎥⎢ ⎥ ⎢ ⎥Independent⎢ T2⎥⎢ x2 ⎥ ≤ ⎢ b2 ⎥W2⎢⎥⎢ ⎥ ⎢ ⎥realization...
⎣ ..
⎦⎣ .. ⎦ ⎣ .. ⎦scenarios
TNWN xNbNWNPIPS-PSBB: Design philosophy and features•PIPS-PSBB is a specialized solver for two-stage Stochastic Mixed Integer Programs
that uses Branch and Bound to achieve finite convergence to optimality.

•It addresses each of the the issues associated to Stochastic MIPs:–A Distributed Memory approach allows to partition the second stage scenario data among multiple
computing nodes.

A
T1
T2

W1
W2

...

...

...

TNWN

PIPS-SBB: Design philosophy and features•

PIPS-SBB is a specialized solver for two-stage Stochastic Mixed Integer Programs
that uses Branch and Bound to achieve finite convergence to optimality.

•It addresses each of the the issues associated to Stochastic MIPs:–

A Distributed Memory approach allows to partition the second stage scenario data among multiple
computing nodes.

–

As the backbone LP solver, we use PIPS-S: a Distributed Memory parallel Simplex solver for Stochastic
Linear Programs.

...

PIPS-SBB: Design philosophy and features•

PIPS-SBB is a specialized solver for two-stage Stochastic Mixed Integer Programs
that uses Branch and Bound to achieve finite convergence to optimality.

•It addresses each of the the issues associated to Stochastic MIPs:–

A Distributed Memory approach allows to partition the second stage scenario data among multiple
computing nodes.

–

As the backbone LP solver, we use PIPS-S: a Distributed Memory parallel Simplex solver for Stochastic
Linear Programs.

–PIPS-PSBB has a structured software architecture that is easy to expand in terms of functionality andfeatures.

Our approach to Parallel Branch and Bound•Two levels of parallelism require a layeredorganization of the MPI processors.

•In the Branch and bound communicator,processors exchange:•–Solutions.

–Lower Bound Information.

–Queue sizes and search status.

LP relaxations.

–Primal Heuristics.

–Branching and candidate selection.

Strategies for ramp-up:–Parallel Strong Branching–Standard Branch and Bound

Strategy for Ramp-down: intensify thefrequency of node rebalancing.

P0,2

P1,0

P1,1

P1,2

Pm,0Pm,1Pm,2Branch
and
Bound
Comm 0Branchand
BoundComm 1Branchand
BoundComm 2…
…

P0,n

PIPS-SBB Solver 0

P1,nPIPS-SBB Solver 1…

–

P0,1…

In the PIPS-S communicator, processors
perform in parallel:

P0,0…

•Branch and Bound Nodes.

…

•–…

Pm,nBranchandBoundComm nPIPS-SBB Solver mug[PIPS-SBB,MPI]PIPS-PSBBPIPS-SBB

Parallel Branch and Bound
Descentralized, lightweight control ofthe workload
Fine-grained approach

PIPS-SParallel LP relaxations
Data Parallelization
Sequential Branch and Boundug[PIPS-SBB,MPI]

Parallel Branch and BoundCentralized control of the workload
Coarse-grained, black-box approach•In addition to PIPS-PSBB, we also introduce ug[PIPS-SBB,MPI]: a coarse grained external
parallelization of PIPS-SBB.

•UG is a generic framework used to parallelize Branch & Bound based MIP solvers.

•–Exploits powerful performance of state-of-the-art base solvers, such as SCIP, Xpress, Gurobi, and CPLEX.

–It uses the base solver as a black box.

UG has been widely applied to parallelize many MIP solvers:–

Distributed memory via MPI: ug[SCIP,MPI], ug[Xpress,MPI], ug[CPLEX,MPI]–

Shared-memory via Pthreads: ug[SCIP,Pth], ug[Xpress, Pth]UG[PIPS-SBB,MPI]•UG has been successfully used to solve some open MIP problems using more than80.000 cores. Certainly proven to be scalable.

•ug[PIPS-SBB,MPI] co-developed with Yuji Shinano•The second MIP solver in the world (after PIPS-PSBB) to use two levels of nestedparallelism.
0)

11A

11AA

1:C:A

A A: :A: - A
A AA0)

1BBAA

1- B

1:C

1:C:

A A
:AA A
: :A

1A

1A

1:: - A
A A

-1 1:: ::C
1 1A

1:A

1

1: - A
A A

A:CAA-:2- -E1:
1 1:: : 1/ABA BA1A0):C

Experimental performance results•

We test our solver on SSLP instances, from the SIPLIB library.

•SSLP instances model server locations under uncertainty.

•Instances are coded as SSLPm_n_s, where s represents the number of scenarios.

•Larger number of scenarios means bigger problems– LP relaxations of all instances fit in memory, even in CPLEX– PIPS-SBB can handle much larger LP relaxations•

Details: see http://www2.isye.gatech.edu/~sahmed/siplib/sslp/sslp.html•PIPSBB run on the Cab cluster:– Each node: Intel Xeon E5-2670, 2.6 GHz, 2 CPUs x 8 cores/CPU– 16 cores/node– 2 GB RAM/core, 32 GB RAM/node– Infiniband QDR interconnect•CPLEX 12.6.2 used in some comparisons, in Vanilla setting.

Experimental performance results•

We measure parallel performance in terms of speedup, node inefficiency, andcommunication overhead:–Speedup Sp on the time Tp needed to reach optimality by a configuration with p processors
with respect to the time needed by a sequential baseline T1:

𝑆" =–𝑇%
𝑇"

Communication overhead: Fraction of time Tcomm + Tsync needed for communication andprocessor synchronization with respect to the total time of execution Texec:𝑇)'** + 𝑇,-.)𝐶'( =𝑇/0/)–

Node inefficiency: Fraction of redundant nodes explored Nr with respect to the total numberof nodes explored Ntotal.

𝑁2./33 =𝑁4
𝑁5'567

0000

PIPS-PSBB and ug[PIPS-SBB,MPI]: Performance comparison

70

Communication overhead(%)

Scaling: Time to optimality

Performance comparison between PIPS-PSBB and ug[PIPS-SBB,MPI] when optimizing small instances.
sslp_15_45_5 (5 scenarios, 3390 binary variables, 301 constraints)

605040302010012105010020070PIPS-PSBB:

60oo504030

o20
10o0400

121050

100

200

400

Number of Processors

70000070

60000060

Node inefficiency(%)

Total tree size

Number of Processors

500000400000300000200000100000ug[PIPS-SBB,MPI]:
oo50
40

o30
20
100

121050

100

200

400

1

Number of Processors
PIPS-PSBB

Total tree size

Scales up to 200 cores (66x).
Total work performed remains
within a factor of 2x w.r.t.
sequential.
Communication overhead
dominates after 400 cores.
Node inefficiency grows at aslower rate than ug[PIPSSBB,MPI].

21050

100200

Number of Processors
ug[PIPS-SBB,MPI]

400

Scales up to 200 cores (33x).
Total work varies by processor
configuration.
Higher communication overhead
and higher node inefficiency.

5040
30
20
100121050 100 200 400

Number of Processors
Tight Communication (10-500)

90

5000008070

450000Total tree size

60

Communication overhead(%)

7060
50
40
30
20100

4000003500003000002500002000001500001210150 100 200 400

1050 100 200 400

Number of Processors

Number of Processors
Standard Communication (50-1000)

2Loose Communication (100-50000)

Total tree size

•500000
PIPS-PSBB
allows to modify the frequency between synchronous communications.
450000••Total tree size

Scaling: Time to optimality

Tuning the communication frequency of PIPS-PSBB

Frequency
defined with (x,y), where x and y represent the minimum and maximum
350000
number
300000 of B&B iterations that must be processed before communication takes place.
400000250000200000Tighter
communication increases communication overheads, but reduces work
150000
performed. 1 2 10 50 100 200 400

Number of Processors•The opposite takes place under loose communication.

600500
40030020010002015500] [100] 0[50] 0[25] 5[20] 0[10] 00[5] 00[1]51522151[5Number of solvers[Processors per PIPS-S solver]

1e+07
8e+06
6e+06
4e+06
2e+06
000] [100] 0[50] 0[25] 5[20] 0[10] 00[5] 00[1]
51522
151[5

Number of solvers[Processors per PIPS-S solver]

Number of solvers[Processors per PIPS-S solver]
Ramp up communication overhead(%)

1.2e+07

PIPS-PSBB:• Communication overhead
minimal except at rampup
when LP solver is slow.

10000] [100] 0[50] 0[25] 5[20] 0[10] 00[5] 00[1]51522
151[5Total tree size

PIPS-S:• Speedup to 10 cores is 6x.
• Performance increases up
to 20 cores.

25

Communication overhead(%)

Root node LP Relaxation Time (s)PIPS-PSBB Solver performance exposed: sslp_10_50_500(500 scenarios, 250,010 binary variables, 30,001 constraints)

181614121086
42000] [100] 0[50] 0[25] 5[20] 0[10] 00[5] 00[1]
5
1
52
2
1
51[5

Number of solvers[Processors per PIPS-S solver]

PIPS-SBB: Comparison against CPLEX
Performance comparison against CPLEX 12.6.2
Instance

Scenarios

Configuration
Solvers

PIPS-S
procs

PIPS-PSBB

ug[PIPS-SBB,UG]

CPLEX SM

CPLEX DM

GAP(%) (Time)(s)GAP(%) (Time)(s)

Procs

GAP(%) (Time)(s)

Procs

GAP(%) (Time)(s)sslp_5_25_50

50

22(7.45s)(8.03s)4(0.27s)4(0.27s)sslp_5_25_100100

22(22.37s)(17.79s)4(0.64s)4(0.64s)sslp_15_45_5

52002(107.11s)(163.53s)

16(1.97s)

400(6.26s)sslp_15_45_10

10

200

2

0.09%

0.16%

16(1.81s)

400(15.04s)

sslp_15_45_15

15

200

20.25%

0.30%

16(7.80s)

400(15.75s)sslp_10_50_50

50

200

10

0.13%

0.21%

16(43.88s)

2000

0.15%(M)sslp_10_50_100

100

200

10

0.17%

0.20%

16(221.69s)

2000

0.16%(M)sslp_10_50_500

500

200

10

0.24%

0.24%

16

4.91%(M)2000

1.25%(M)sslp_10_50_1000

1000

200

10

0.24%

0.24%

16

9.91%

2000

6.08%

sslp_10_50_2000

2000

200

10

0.26%

0.26%

16

19.93%

2000

8.11%

Time limit: 1 hour••

Distributed-memory parallelization of CPLEX is often inferior to its shared-memory counterpart.
Both CPLEX versions run into Memory limits for some problems.

••The superior performance of CPLEX’s base solver helps in trivial and small problems.
PIPS-SBB-based solvers show superior performance for large problems.

Conclusions•

We developed a light-weight decentralized distributed memory branch-and-bound
implementation for PIPS-SBB with two degrees of parallelism:– Processing of nodes in parallel (parallel LP relaxation, parallel heuristics, parallel
problem branching, …).
– Branch and Bound in parallel.

•Better parallel efficiency is achieved by focusing the parallel resources in the mostpromising nodes.

•We try to reduce communication bottlenecks and achieve high processor occupancy
via a decentralized control of the tree exploration and a lightweight mechanism forexchanging Branch and Bound nodes.

•

Competitive performance to state-of-the-art commercial MIP solvers, in the context oflarge instances.

A natural progression in the parallelization of Branch & Bound
The presented work contributes to the ultimate goal of improving the parallel
efficiency of Branch & Bound.
•New parallel heuristics, which leverage parallelism in order to increase the effectiveness,
speed and scalability of primal heuristics.

•New parallel algorithms for a better distribution of work in the context of Branch & Bound.

Scalable massively-parallel heuristics

Work-eﬃcient Parallel Branch & BoundTime

The code of PIPS-PSBB is available at: https://github.com/LLNL/PIPS-SBB26

Thank You!