Large-scale parallelisation for the Benders’decomposition framework in SCIP
Stephen J. Maher
University of Exeter,@sj maher
s.j.maher@exeter.ac.uk

October 1, 2021

1 / 17

Structured mixed integer programming
Basic idea: Minimise a linear objective function over a set of solutions
satisfying a structured set of linear constraints.

minsubject toc >x + d >y ,Ax ≥ b,Bx + Dy ≥ g ,x ≥ 0,y ≥ 0,x ∈ Zp1 × Rn1 −p1 ,y ∈ Zp2 × Rn2 −p2 .

2 / 17

Decomposition methods for mixed integer programming
MasterBlock
Block 1
Linking
BlockBlock 2
Block 3

Linking variables

I Variable decomposition
I Existence of a set of linking variables
I Exploits property of restriction, i.e. blocks are “easy” to solve after
fixing variables
I Parallelisation: each block can be solved in parallel.

3 / 17

Benders’ decomposition
Original problem

minsubject toc >x + d >y ,Ax ≥ b,Bx + Dy ≥ g ,x ≥ 0,y ≥ 0,x ∈ Zp1 × Rn1 −p1 ,y ∈ Rn 2 .

4 / 17

Benders’ decompositionminsubject toc > x + f (x),Ax ≥ b,x ≥ 0,x ∈ Zp1 × Rn1 −p1 .

wheref (x) = min{d > y | Bx + Dy ≥ g , y ∈ Rn2 }y ≥0

4 / 17

Benders’ decomposition
minsubject toc > x + f (x),Ax ≥ b,x ≥ 0,x ∈ Zp1 × Rn1 −p1 .

wheref (x) = min{d > y | Bx + Dy ≥ g , y ∈ Rn2 }y ≥0equivalently, using the dual formulation we can define
f 0 (x) = max{u > (g − Bx) | D > u ≥ d > , u ∈ Rm2 }u≥0(f 0 (x) = f (x))

4 / 17

Benders’ decomposition
Using the dual formulation of f (x), given by
f 0 (x) = max{u > (g − Bx) | D > u ≥ d > , u ∈ Rm2 }u≥0letI O be the set of all extreme points of f 0 (x)I F be the set of all extreme rays of f 0 (x)an equivalent formulation of the original problem isminc > x + ϕ,subject toAx ≥ b,ϕ ≥ u > (g − Bx) ∀u ∈ O0 ≥ u > (g − Bx) ∀u ∈ Fx ≥ 0,x ∈ Zp1 × Rn1 −p1 .
5 / 17

Benders’ decomposition
I The sets O and F are exponential in size
I The reformulated original problem becomes intractable

6 / 17

Benders’ decomposition
I The sets O and F are exponential in size
I The reformulated original problem becomes intractable
I Need to use a delayed constraint generation algorithm

6 / 17

Benders’ decomposition
I The sets O and F are exponential in size
I The reformulated original problem becomes intractable
I Need to use a delayed constraint generation algorithm
Cut generating LP ⇔ Benders’ subproblemz(x̂) = min d > y ,subject toDy ≥ g − B x̂,y ≥ 0,y ∈ Rn 2 .

6 / 17

Standard Benders’ implementation
Start

Solve master problem

Solve subproblems

Yes - add cutz(x̂) > ϕNoStop

I Easy to understand and simple to implement.
I Not always effective, large overhead in repeatedly solving masterproblem.

7 / 17

Standard Benders’ implementation
Start

Solve master problem

Solve subproblems

Yes - add cutz(x̂) > ϕNo
Stop

I Easy to understand and simple to implement.
I Not always effective, large overhead in repeatedly solving masterproblem.
I Easily parallelisable. All subproblems can be solved in parallel.
I Not always efficient—master problem is still solved sequentially.
7 / 17

Branch-and-cut
I Modern solvers pass through a number of different stages during
node processing.
I Some of these stages can be used to generate Benders’ cuts.
I By interrupting node processing, Benders’ cuts are generated during
the tree search.
Solving process
Start

Init

Presolving
Domain propagation

StopSolve LP
Node selection
Conflict analysis

LP inf.

Primal heuristics

Pricing

IP feas.

ProcessingCuts
Enforce constraints

IP inf.

LP feas.

Branching8 / 17

Branch-and-cut
I Modern solvers pass through a number of different stages during
node processing.
I Some of these stages can be used to generate Benders’ cuts.
I By interrupting node processing, Benders’ cuts are generated during
the tree search.
Cut generation - Branch-and-cut
Start

Init

Presolving
Domain propagation

Stop
Solve LP
Node selection
Conflict analysis

LP inf.

Primal heuristics

Pricing

IP feas.

Processing

Cuts
Enforce constraints

IP inf.

LP feas.

Branching8 / 17

Branch-and-cut – parallelisation
I Many software implementations for the parallelisation ofbranch-and-cut, such as the UG framework.
I Useful if solving the subproblems sequentially is not time consuming.
I Addresses issues related to difficult master problem.

9 / 17

Hybrid parallelisation
I Parallelise the branch-and-cut tree search using the UG framework(distributed memory).
I Parallelise the solving of the subproblems using OpenMP (sharedmemory).

10 / 17

Hybrid parallelisation
I Parallelise the branch-and-cut tree search using the UG framework(distributed memory).
I Parallelise the solving of the subproblems using OpenMP (sharedmemory).
Benefits
I Parallelisation of tree search avoids waiting for difficult masterproblem solves.
I Solving the subproblems in parallel takes advantage of available
cores at each node.
I Able to balance the effort between master problem tree search andsubproblem solving.

10 / 17

Current status and features
I Both tree search and subproblem parallelisation available.
I Tree search parallelisation activated by enabling Benders’ framework.
I Subproblem parallelisation enabled by setting the number of threads.
SCIP must be built with OpenMP.

I Customisable sorting of subproblems for load balancing
I Prioritise subproblems with less calls, then by average number of LP
iterations.

I Parallelisation relies on transfer of Benders’ cuts between solvers. By
calling SCIPstoreBendersCut in custom Benders’ cuts plugins,custom Benders’ decomposition implementations can be parallelised.

11 / 17

Current challenges

1.0Fraction of instances

0.8
0.6
0.4
0.2
0.0 010

BasicDefault
CutCheck
RelativeIntThreePhase
101
102
103
Ratio to best setting
Stochastic Server Location Problem
12 / 17

Design Issues

I Each Benders’ subproblem is implemented as a SCIP instance.
I With a large number of subproblems memory consumption can bevery high.
I When parallelising the tree search, the subproblems must be copied
to every solver.
I Large number of solvers and large number of subproblems results ina very high memory consumption.

13 / 17

Design Issues

...

...

...

...

...

...

...

...

...

...

...

...

I Each Benders’ subproblem is implemented as a SCIP instance.
I With a large number of subproblems memory consumption can bevery high.
I When parallelising the tree search, the subproblems must be copied
to every solver.
I Large number of solvers and large number of subproblems results ina very high memory consumption.

13 / 17

Memory saving mode
I Subproblems, especially in the context of stochastic programming,
may have very similar structures.
I differences only in the constraint matrix or objective function
coefficients or in the RHS.

I Create a SCIP instance per each thread. Using a subproblem
difference create each subproblem on the fly.
Disadvantage
I Only applicable when subproblems have similar structures
I Does not benefit from warm starting between subproblem solves
I Creating and destroying subproblems is time consuming

14 / 17

Load balancing
I Current best balance of shared and distributed memory unclear
I Benders’ cuts are not generated at all nodes in the tree, so reserving
threads for subproblem solving may be inefficient.
I Automatic load balancing would allow for idle threads to be used foralternative purposes.

15 / 17

Partial node processing
I Only solve a subset of subproblems at each node in the tree.
Delaying the complete processing of the node.
I The node is not fully evaluated, but enough cuts may be generated
to improve the bound.
I Identify the balance of the number of subproblems to solve to gain
sufficient bound improvement.

16 / 17

Key points
I Hybrid parallel implementation of Benders’ decomposition available
in SCIPI Current version is available to solve smaller scale problems.
I Future development will reduce the memory consumption of theBenders’ framework, enabling its use on large problems and large
computational resources.
I Improved load balancing and partial node processing will beinvestigated.

17 / 17