Parallelizing SCIP-SDP via the UG framework
Tristan Gally
joint work with Marc E. Pfetsch, Chuen-Teck See, and Yuji Shinano

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 1

Mixed-Integer Semidefinite Programming

I Mixed-integer semidefinite program
MISDPinfs.t.

bT ym
X

Ai yi − A0  0,i=1yi ∈ Z ∀ i ∈ I

for symmetric matrices (Ai )i ≤m .

I Linear constraints, bounds, multiple blocks possible within SDP-constraint.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 2

Contents

Applications
Solution Approaches
SCIP-SDP
Parallelization
Numerical Results
Conclusion

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 3

Contents

Applications
Solution Approaches
SCIP-SDP
Parallelization
Numerical Results
Conclusion

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 4

Truss Topology DesignI n nodes V = vi ∈ Rd : i = 1, ... , n
I nf free nodes Vf ⊂ V
I m possible bars
E ⊆ {{vi , vj } : i 6= j } , |E | = m
I Force f ∈ Rdf for df = d · nf

ground structure 3x3
January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 5

Truss Topology DesignI n nodes V = vi ∈ Rd : i = 1, ... , n
I nf free nodes Vf ⊂ VI m possible bars
E ⊆ {{vi , vj } : i 6= j } , |E | = m
I Force f ∈ Rdf for df = d · nf

ground structure 3x3
January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 5I Cross-sectional areas x ∈ Rm+ forbars that minimize the volume
while creating a “stable” truss

I Stability is measured by thecompliance 12 f T u with node
displacements u

optimal structureTruss Topology Design

TTD-SDP [Ben-Tal, Nemirovski 1997]

XminI `e : length of bar e`e xe

I x : cross-sectional arease ∈E


s.t.

2cmax
f

I E : set of possible bars

TfA(x)

I f : external force

0xe ≥ 0I cmax : upper bound on∀e ∈ E

compliance

I Ae : bar stiffness matriceswith stiffness matrix A(x) =PAe `e xe .

e ∈EJanuary 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 6

Truss Topology Design

I In practice, we won’t be able to produce/buy bars of any desired size.
⇒ Only allow cross-sectional areas from a discrete set A.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 7

Truss Topology Design

I In practice, we won’t be able to produce/buy bars of any desired size.
⇒ Only allow cross-sectional areas from a discrete set A.
TTD-MISDP [Kočvara 2010, Mars 2013]
minX`ee ∈EXa∈As.t.

a xea

2cmaxffTA(x)

Xa∈A

where A(x) =Pe∈EAe `ePa∈A 0,xea ≤ 1xea ∈ {0, 1}

a xea .

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 7∀e ∈ E,∀e ∈ E, a ∈ A,

Compressed Sensing

I Task: find sparsest solution to underdetermined system of linear equations,i.e. a solution of`0 -Minimization
minkx k0s.t.

Ax = bx ∈ Rn

where kx k0 := |supp(x)|.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 8Compressed Sensing

I Task: find sparsest solution to underdetermined system of linear equations,i.e. a solution of`0 -Minimization
minkx k0s.t.

Ax = bx ∈ Rn

where kx k0 := |supp(x)|.

I Under certain conditions on A, this is equivalent to`1 -Minimization
minkx k1s.t.

Ax = bx ∈ RnJanuary 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 8Compressed Sensing

One such condition is the (asymmetric) restricted isometry property (RIP):αk2 kx k22 ≤ kAx k22 ≤ βk2 kx k22

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 9∀x : kx k0 ≤ kCompressed Sensing

One such condition is the (asymmetric) restricted isometry property (RIP):

αk2 kx k22 ≤ kAx k22 ≤ βk2 kx k22∀x : kx k0 ≤ k

Theorem [Foucart, Lai 2008]
If Ax = b has a solution x with kx k0 ≤ k and the RIP of order 2k holds for2
√β2k
< 4 2 − 3 ≈ 2.6569,2α2kthen x is the unique solution of both the `0 - and the `1 -optimization problem.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 9Compressed Sensing

One such condition is the (asymmetric) restricted isometry property (RIP):

αk2 kx k22 ≤ kAx k22 ≤ βk2 kx k22∀x : kx k0 ≤ kTheorem [Foucart, Lai 2008]
If Ax = b has a solution x with kx k0 ≤ k and the RIP of order 2k holds for2
√β2k
< 4 2 − 3 ≈ 2.6569,2α2kthen x is the unique solution of both the `0 - and the `1 -optimization problem.
But N P -hard in general to compute optimal constants . . .
January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 9Compressed Sensing

The optimal constant αk2 (and similarly βk2 ) for

αk2 kx k22 ≤ kAx k22 ≤ βk2 kx k22∀x : kx k0 ≤ k

can be computed via the following non-convex cardinality-constrained QP:
RIP-QP
infkAx k22

s.t. kx k22 = 1,kx k0 ≤ k .

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 10

Compressed Sensing

Idea: Substitute X := xx > to obtain the non-convex rank-constrained MISDP
RIP-Rk1-MISDP
mins.t.

Tr(AT AX )Tr(X ) = 1−zj ≤ Xjj ≤ zjnXzj ≤ k∀j ≤n

j=1Rank(X ) =1
X 0z ∈{0, 1}nJanuary 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 11

Compressed Sensing

RIP-MISDP
mins.t.

Tr(AT AX )Tr(X ) = 1−zj ≤ Xjj ≤ zjnXzj ≤ k∀j ≤ nj=1Rank(X ) = 1
X 0z ∈{0, 1}nTheorem [G., Pfetsch 2016]
There always exists an optimal solution for (RIP-MISDP) with Rank(X ) = 1.
January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 12

Further Applications

I Combinatorial optimization problems strengthened by semidefinite relaxations
I Max-cut / minimum k -partitioning
I Stable set
I Quadratic assignment problems (including TSP as special case)I ...
I Nonlinear / semidefinite problems with binary decisions
I Cardinality-constrained least squares
I Transmission switching problems for AC power flow
I Design and control of linear time-invariant systems
I ...
January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 13

ContentsApplications
Solution Approaches
SCIP-SDP
Parallelization
Numerical Results
Conclusion

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 14

LP-Based Cutting Plane Approach

I Solve LP in each node and enforce SDP constraint via linear cuts.
I Cannot use gradient cuts since SDP constraint is non-smooth in general.
I Use characterization X  0⇔

u > X u ≥ 0 for all u ∈ Rn .

P?
I For eigenvector v to smallest eigenvalue of Z ? := mi=1 Ai yi − A0 6 0, thelinear cut!
mX>v
Ai yi − A0 v ≥ 0i=1

∗is valid and cuts off y .

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 15

SDP-Based Branch and Bound

I Solve an SDP in each node of the branch-and-bound tree.
I Needs additional techniques to ensure constraint qualifications for validity ofinterior-point SDP solvers.

I Less efficient warmstarts available for interior-point solvers.
I No simplex tableau available for cutting plane generation.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 16

Comparison of the two Approaches

I Cutting-plane-based approaches used by most commercial solvers formixed-integer second-order cone (MISOCP).

I Outer approximation for SOCPs possible with polynomial number of cuts.
(Ben-Tal/Nemirovski 2001)

I Outer approximation for SDPs needs exponential number of cuts.
(Braun et al. 2015)

I SDP relaxations can still be solved up to given precision in polynomial time.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 17

Contents

Applications
Solution Approaches
SCIP-SDP
Parallelization
Numerical Results
Conclusion

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 18

SCIP-SDPI Plugin for SCIP to extend it to mixed-integer semidefinite programming.
I Supports both SDP-based branch and bound and LP-based cutting plane
approach, can switch between both via parameter settings.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 19

SCIP-SDPI Plugin for SCIP to extend it to mixed-integer semidefinite programming.
I Supports both SDP-based branch and bound and LP-based cutting planeapproach, can switch between both via parameter settings.

I Extends SCIP by an SDP constraint handler, SDP relaxation handler andseveral heuristics, propagators, file readers, . . . .

I Uses penalty approach in case constraint qualification fails.
I Includes interfaces to three different SDP solvers: MOSEK, SDPA and DSDP.
I Currently one of the fastest publicly available MISDP solvers.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 19Numerical Comparison of Solution Approaches

settings
NL-BBLP-based
bestTTD

CLS

solvedtimesolved

time

55
44
55

84.01
169.23
60.59

62
65
65

142.19
11.53
11.53

Mk-P
solved
time
67
30
67

54.44
712.2849.73

Total
solved

time

184
139
187

86.59
134.6534.69

run on Intel Xeon E5-4650 CPUs running at 2.70 GHz with 512 GB of shared RAM; time limit of 3600 seconds, times as shifted geometric means;using developer versions of SCIP 6.0.0, SCIP-SDP 3.1.1, SDPs solved using MOSEK 8.1.0.54, LPs using CPLEX 12.6.3; instances from CBLIB

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 20

ContentsApplications
Solution Approaches
SCIP-SDP
Parallelization
Numerical Results
Conclusion

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 21

Parallelizing an MISDP solver

I Parallelization can happen either on the SDP or the MIP side.
I On the SDP side: Parallel computation of Schur complement matrix andparallel Cholesky factorization.

I Parallel Cholesky may depend on sparsity of the constraint matrices.
I Due to overhead only efficient for large SDPs, not necessarily the smaller
ones appearing in MISDP.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 22

Parallelizing an MISDP solver

I Parallelization can happen either on the SDP or the MIP side.
I On the SDP side: Parallel computation of Schur complement matrix andparallel Cholesky factorization.

I Parallel Cholesky may depend on sparsity of the constraint matrices.
I Due to overhead only efficient for large SDPs, not necessarily the smaller
ones appearing in MISDP.

I On the MIP side: Parallel solution of branch-and-bound subtrees.
I Independent of solution approach for SDP relaxations.
I Cannot solve root node in parallel.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 22

Racing Ramp-Up

I Use racing ramp-up to decide between LP and SDP approach.
I Start a number of SCIP-SDP instances in parallel with half of them using
LP-based and the other half SDP-based settings.

I Additionally change further parameters that are relevant for LP/SDP approach.
I Total of 32 different parameter settings for up to 32 threads.
I After enough nodes have been generated, decide on “best” solver anddistribute this solver’s tree.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 23

Parallelization via UG Framework

I Racing ramp-up uses resources in root node and decides on best settings.
I In the remainder of the solution process have different threads solve theirsubtrees in parallel.

I Implementation allows for both shared and distributed memory.
I Less than 100 lines of additional code.
I Mostly including plugins and changing default parameters

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 24

UG-MISDP Output

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 25

UG-MISDP Solver Statistics

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 26

Contents

Applications
Solution Approaches
SCIP-SDP
Parallelization
Numerical Results
Conclusion

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 27

Racing Statistics

4: LP + easycip emphasis
5: SDP + objcoef branching20

7: SDP + most infeasible
branching# racing winner15

9: SDP + disabled
subdeterminant cuts
10

11: SDP + more aggressiverounding5

15: SDP + objective limit
17: SDP + OBBT

01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

setting

truss topology

cardinality-constrained least squares

min k-partitioning

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 28

19: SDP + never increase
penaltyparam
22: LP + more flow cover cuts

Runtimes

solver

SCIP-SDPUG-MISDP 1 thr.
UG-MISDP 2 thr.
UG-MISDP 4 thr.
UG-MISDP 8 thr.
UG-MISDP 16 thr.
UG-MISDP 32 thr.

TTD

CLS

solvedtime

solved

time

55
54
56
58
58
59
59

84.01
107.49
64.93
39.76
32.07
21.03
21.27

62
62
64
65
65
65
65

142.19156.70
23.31
18.48
14.51
16.37
18.38

Mk -P
solved
time
67
58
56
60
60
59
56

54.44
107.81
92.25
85.61
72.35
78.46
92.14

Total
solved

time

184
174
176
183
183
183
180

86.59
122.23
53.79
42.07
34.57
32.65
36.11

run on Intel Xeon E5-4650 CPUs running at 2.70 GHz with 512 GB of shared RAM; time limit of 3600 seconds, times as shifted geometric means;using developer versions of SCIP 6.0.0, SCIP-SDP 3.1.1, UG 0.8.6, SDPs solved using MOSEK 8.1.0.54, LPs using CPLEX 12.6.3; instances from CBLIB

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 29

Speedups

TTD
CLS
Mk -P
Total
SCIP-SDP

1

Speedup

0.8
0.6
0.4
0.2

12481632# threads
run on Intel Xeon E5-4650 CPUs running at 2.70 GHz with 512 GB of shared RAM; time limit of 3600 seconds, times as shifted geometric means;using developer versions of SCIP 6.0.0, SCIP-SDP 3.1.1, UG 0.8.6, SDPs solved using MOSEK 8.1.0.54, LPs using CPLEX 12.6.3; instances from CBLIB

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 30

Contents

Applications
Solution Approaches
SCIP-SDP
Parallelization
Numerical Results
Conclusion

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 31

Conclusion

I Both SDP-based branch and bound and LP-based cutting plane approachescan be fast on different applications.

I Use racing ramp-up to dynamically choose between both approaches.
I Implemented using the UG framework in just over 100 lines of code.
I Large speedup for two threads due to switching to LPs, further speedups due
to parallel branch and bound for problems with large enough trees.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 32

Obtaining UG-MISDP

SCIP-SDP is available fromhttp://www.opt.tu-darmstadt.de/scipsdp/UG-MISDP is available as part of the UG distribution
and the SCIP optimization suite fromhttps://scip.zib.de/Thank you for your attention!
January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 33

References

A. Ben-Tal and A. Nemirovski.
Robust truss topology design via semidefinite programming.
SIAM Journal on Optimization, 7(4):991–1016, 1997.
A. Ben-Tal and A. Nemirovski.
On polyhedral approximations of the second-order cone.
Mathematics of Operations Research, 26:193–205, 2001.
G. Braun, S. Fiorini, S. Pokutta, and D. Steurer.
Approximation limits of linear programs (beyond hierarchies).
Mathematics of Operations Research, 40(3):756–772, 2015.
A. Eisenblätter.
The semidefinite relaxation of the k -partition polytope is strong.
In W. J. Cook and A. S. Schulz, editors, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, volume 2337 of Lecture Notes in Computer
Science, pages 273–290. Springer, Berlin Heidelberg, 2002.
H. A. Friberg.
CBLIB 2014: a benchmark library for conic mixed-integer and continuous optimization.
Mathematical Programming Computation, 8(2):191–214, 2016.
T. Gally and M. E. Pfetsch.
Computing restricted isometry constants via mixed-integer semidefinite programming.
Technical report, Optimization Online, 2016.
T. Gally, M. E. Pfetsch, and S. Ulbrich.
A framework for solving mixed-integer semidefinite programs.
Optimization Methods and Software, 33(3):594–632, 2018.
M. Kočvara.
Truss topology design with integer variables made easy.
Technical report, School of Mathematics, University of Birmingham, 2010.
S. Mars.
Mixed-Integer Semidefinite Programming with an Application to Truss Topology Design.
PhD thesis, FAU Erlangen-Nürnberg, 2013.
M. Pilanci, M. J. Wainwright, and L. El Ghaoui.
Sparse learning via Boolean relaxations.
Mathematical Programming Series B, 151(1):62–87, 2015.
A. M. Tillmann and M. E. Pfetsch.
The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing.
IEEE Transactions on Information Theory, 60(2):1248–1259, 2014.

January 14, 2019 | Parallelizing SCIP-SDP via the UG framework | Tristan Gally | 34