ParaQapNB : Massively Parallelized DNN-based
Branch-and-bound QAP solver*Koichi Fujii, Naoki Ito, Sunyoung Kim,
Masakazu Kojima, Yuji Shinano, Kim-Chuan Toh
NTT DATA Mathematical Systems Inc., FAST RETAILING CO., LTD.,
Ewha W. University, Chuo University, Zuse Institute Berlin,
National University of Singapore

2nd UG workshop, 01 October 2021
16 December 2021 revised

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

1 / 36

Summary : DNN-based Branch-and-bound for the
Quadratic Assignment Problem
Motivation• Quadratic assignment problems still remain as one of the mostdiﬃcult combinatorial problems• Recent conic relaxation technique updates the lower bounds of (open)
quadratic assignment problem
Goal
Solve all open instances of QAPLIBOur Results
Our DNN-based branch-and-bound solver solved two open instances(tai30a, sko42).
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

2 / 36

Summary: Quadratic Assignment Problem• n facilities i = 1, . . . , n: fij : flow from facility i to facility j.
• n locations k = 1, . . . , n: dkℓ : distance from loc k to loc ℓ.
• Assign each facility to each location to minimize flow × distance.
n = 4, Flow fijji 1 2 3 4
1 0 5 4 2
2 4 0 2 5
3 2 3 0 4
4 1 5 3 0

QAP :Distance dkℓℓ
k 1 2 3 4
1 0 6 7 8
2 6 0 9 6
3 7 9 0 8
4 8 6 8 0

minimizeikthe total cost =Assignment
1
2
3
k1 k2 k3
∥
∥
∥
4
1
3

∑

4
k4
∥
2

fij dki kj

i, jsubject to

k1 , . . . , kn : a permutation of 1, . . . , n• n! feasible solutions; 40! = 8.2e47 — too large combination
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

3 / 36

Summary: DNN relaxation
Polynomial optimization problem (POP) with non-negative variables
minx {f0 (x) | fi (x) = 0 (i = 1, 2, . . . , m), x ≥ 0}
• 0-1 binary quadratic optimization problem• Optimal power flow, sensor network localization, ...
Doubly non-negative (DNN) relaxation{}⟨Ai , X ⟩ = b (i = 1, 2, ..., m), X ∈ K1 ∩ K2
min ⟨A0 , X ⟩X
K1 : semidefinite cone, K2 : polyhedral cone
SDP relaxation + non-negative constraints• better lower bounds than SDP• very large O(n2 ) non-negative constraints

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

4 / 36

Summary: Newton-bracketing method• ζ ∗ : The optimal value of QAP• y ∗ : The optimal value of Lagrangian DNN relaxation; y ∗ ≤ ζ ∗ .
Newton-bracketing method
Lagrangian DNN relaxation problem
can be regarded as minimization problem of convex function g : R → R+ .
• Newton method (+ secant
method)y ∗ ← y r +1 ≤ y r ≤ · · · ≤ y 0 .
• (Valid) lower boundℓ1 ≤ · · · ≤ ℓr ≤ ℓr +1 → y ∗

g(y)

y*

y k+1 y k y k-1

yy ∗ ∈ [ℓr , y r ], |y r − ℓr | → 0.

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

5 / 36

Agenda1

Lagrangian DNN relaxation of QAP

2

DNN Optimization and Newton-bracketing method

3

QapNB: DNN-based Branch-and-bound solver for QAP

4ParaQapNB: parallelized DNN-based branch-and-bound solver for QAP

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

6 / 36

Lagrangian DNN relaxation of QAP

Lagrangian DNN relaxation of QAP
QAP( 01-QOP ){∗ζ := min ⟨B ⊗ A, xx ⟩T}

x ∈ {0, 1}m.

(I ⊗ e T )x = (e T ⊗ I )x = e

where A × B denotes Kronecker product of A and B.
( ) ( )T1
1
by X ∈ K1 ≡ S1+mwith Xpq ≥ 0 (0 ≤ p, q ≤ m).
⇓ Replace+xx{

X ∈ K1 , X00 = 1, ⟨H 1 , X ⟩ = 0,
η = min ⟨Q, X ⟩ :Xpq ≥ 0, Xp0 = Xpp (1 ≤ p, q ≤ m)where H 1 ∈ K1 ≡ S1+m(semidefinite cone).
+∗

KoichiFujii (MSI)ParaQapNB}≤ζ ∗ ,

2nd UG workshop, 2021

7 / 36

Lagrangian DNN relaxation of QAP

Lagrangian DNN relaxation of QAP{

X ∈ K1 , X00 = 1, ⟨H 1 , X ⟩ = 0,
η = min ⟨Q, X ⟩ :Xpq ≥ 0, Xp0 = Xpp (1 ≤ p, q ≤ m)
1+m
1
ここで H ∈ K1 ≡ S+ (semidefinite cone).
∗}≤ζ ∗ ,000
H 0 ∈ S1+m
+ ; H00 = 1, Hpq = 0 ((p, q) ̸= (0, 0)) ⇒ X00 = ⟨H , X ⟩,K2 ≡ {X ∈ S1+m : Xpq ≥ 0, X0p = Xp0 = Xpp (1 ≤ p, q ≤ m)} (poly.)⇓{}η ∗ = min ⟨Q, X ⟩ : X ∈ K1 ∩ K2 , ⟨H 0 , X ⟩ = 1, ⟨H 1 , X ⟩ = 0 .
⇓⟨H 1 , X ⟩ ≥ 0, ∀X ∈ K1 ≡ S1+m+ ,Q λ ≡ Q + λH 1 (λ ≥ 0) ↙ a penalty term
⟨Q λ , X ⟩ ≡ ⟨Q, X ⟩ + λ⟨H 1 , X ⟩ ≥ ⟨Q, X ⟩ ∀X ∈ S1+m , λ ≥ 0.

Lagrangian DNN{ relaxation of 01-QOP:

P: η λ = min ⟨Q λ , X ⟩ : X ∈ K1 ∩ K2 , ⟨H 0 , X ⟩ = 1 (X00 = 1)}

ζ ∗ (QAP opt. val) ≥ η ∗ ≥ η λ → η ∗ as 0 ≤ λ → ∞.
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

8 / 36

Lagrangian DNN relaxation of QAP

Lagrangian DNN relaxation of QAP
QAP(01-QOP){ζ ∗ := min ⟨B ⊗ A, xx T ⟩}x ∈ {0, 1}m(I ⊗ e T )x = (e T ⊗ I )x = e.

⇓
Lagrangian DNN{ relaxation of QAP

P: η λ = min ⟨Q λ , X ⟩ : X ∈ K1 ∩ K2 , ⟨H 0 , X ⟩ = 1 (X00 = 1)
K1
K2

KoichiFujii (MSI)}:

semidefinite cone{}Xαβ ≥ 0 (nonnegative)
1+m
:=
X ∈S
:
X0α = Xα0 = XααParaQapNB

2nd UG workshop, 2021

.

(1)
(2)

9 / 36

DNN Optimization and Newton-bracketing method

DNN Optimization{}
P: η λ = min ⟨Q λ , X ⟩ : X ∈ K1 ∩ K2 , ⟨H 0 , X ⟩ = 1 (X00 = 1)
⇕ Strong duality
D: y ∗ = max{y ∈ R : Q λ − H 0 y ∈ (K1 ∩ K2 )∗ ≡ K∗1 + K2 ∗} = η λ ,| {z }G (y )

Feasible

Infeasibley ∗ : Opt.

y

BP method ([Kim, Kojima, & Toh, ’16], [Ito, et al., ’18]) : Bisection
methodNewton-bracketing method ([Kim, Kojima, & Toh, ’20]) : Netwton
method (+ secant method)．
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

10 / 36

DNN Optimization and Newton-bracketing method

DNN Optimization
How to judge if G (y0 ) ∈ K∗1 + K∗2 ? ⇒ solve regression modelf ∗ = min {∥G − (Y1 + Y2 )∥2 | Y1 ∈ K∗1 , Y2 ∈ K∗2 }Y1 ,Y2= min{min{∥(G − Y1 ) − Y2 ∥2 | Y2 ∈ K∗2 } | Y1 ∈ K∗1 }Y1

Y2= min{∥(G − Y1 ) − ΠK∗2 (G − Y1 ))∥2 | Y1 ∈ K∗1 }Y1= min{∥ΠK2 (Y1 − G )∥2 | Y1 ∈ K∗1 } (where Y2 = ΠK∗2 (G − Y1 ))Y1• Obviously, f ∗ = 0 ⇔ G ∈ K∗1 + K∗2 .
• Apply accelerated proximal gradient (APG) to check if f ∗ = 0.
→ [Assumption 1] ΠK2 , ΠK1 can be computed eﬃciently.
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

11 / 36

DNN Optimization and Newton-bracketing method

DNN Optimization : APG method
Constrained optimization: min f (α)α∈SGradient projection method (e.g., [Goldstein,
’64])

(
)
Step 1: αk+1 = ΠS αk − L1k ∇f (αk )APG method [Beck and Teboulle, ’09]()
Step 1: αk = ΠS β k − L1k ∇f (β k )√1+ 1+4tk2
Step 2: tk+1 =2−1
Step 3: β k+1 = αk + ttkk+1(αk − αk−1 )|{z}KoichiFujii (MSI)

momentum

ParaQapNB

2nd UG workshop, 2021

12 / 36

DNN Optimization and Newton-bracketing method

DNN Optimization: Newton-bracketing method{}
P: η λ = min ⟨Q λ , X ⟩ : X ∈ K1 ∩ K2 , ⟨H 0 , X ⟩ = 1 (X00 = 1)
⇕ Strong duality
D: y ∗ = max{y ∈ R : Q λ − H 0 y ∈ (K1 ∩ K2 )∗ ≡ K∗1 + K2 ∗} = η λ ,| {z }G (y )

Define function g : R → R+ as:b (y )∥.
g (y ) := ∥Q λ − H 0 y − (Yb1 (y ) + Yb2 (y ))∥ = ∥X

(3)

It holds:
Lemma (Arima, Kim, Kojima & Toh, ’18)
• g : R → R+ is a continuous and convex function.
b (y )⟩/g (y ) > 0 . In this• If y > y ∗ holds, g ′ (y ) = dg (y )/dy = ⟨H, X
case, g is diﬀerentiable and monotonous increasing.
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

13 / 36

DNN Optimization and Newton-bracketing method

DNN Optimization: Newton-bracketing method
Netwton method of Lagrangian DNN relaxation
Step 0: Start with upper bound y 0 > y ∗ .
Step 1: Obtain (X , Y1 , Y2 ) ∈ (K1 ∩ K2 ) × K∗1 × K∗2 satisfying KKT
condition by APGR method.
k)
Step 2: Update y k by Newton iteration y k+1 := y k − gg′(y．
(y k )

Step 3: k ← k + 1, goto Step1.
Theorem (Kim, Kojima, & Toh, ’20)(i) y k converges to y ∗ as k → ∞.
(ii) Assume that Q λ − H 0 y lies in the interior of K∗1 + K∗2 forsome y . Then the convergence of y k to y ∗ are quadratic.

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

14 / 36

DNN Optimization and Newton-bracketing method

DNN Optimization : Newton-bracketing method
y k+1 = y k −g (y k )e (y k )⟩ ≥ η λ= ⟨Q λ , X
g ′ (y k )e (y k ) : feasible solution of Lagrangian DNN relaxation.
Xy ∗ ← y k+1 ≤ y k ≤ y k−1 ≤ · · · ≤ y 0
y 0 : upper bound of y ∗
g(y)

⇐
y*

y k+1 y k y k-1

KoichiFujii (MSI)

For k > 1, apply secant method insteadof Newton method.

yParaQapNB

2nd UG workshop, 2021

15 / 36

DNN Optimization and Newton-bracketing method

DNN Optimization: Newton-bracketing method(lower
bound){}
P: η λ = min ⟨Q λ , X ⟩ : ⟨H 0 , X ⟩ = 1, X ∈ K1 ∩ K2 )⇓ Identity matrix I ∈ K1 and suﬃciently large ρ ≥ 0min{⟨Q λ , X ⟩ | ⟨H 0 , X ⟩ = 1, ⟨I , X ⟩ ≤ ρ, X ∈ K1 ∩ K2 }X

⇕ Strong duality
max{y + ρµ | Q λ − y H 0 −µI ∈ K∗1 + K∗2 , µ ≤ 0}y ,µ| {z }G (y )⇕
max {y + ρµ | G (y ) − Y2 − µI ∈ K∗1 (= Sn+ ), Y2 ∈ K∗2 , µ ≤ 0}

y ,µ,Y2

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

16 / 36

DNN Optimization and Newton-bracketing method

DNN Optimization: Summary{}
P: η λ = min ⟨Q λ , X ⟩ : ⟨H 0 , X ⟩ = 1, X ∈ K1 ∩ K2 )Dual of Lagrangian relaxation with parameter ρ ≥ 0
max {y + ρµ | G (y ) − Y2 − µI ∈ K∗1 (= Sn+ ), Y2 ∈ K∗2 , µ ≤ 0}

y ,µ,Y2

Newton-bracketing method
Step 0: Start with upper bound y 0 > y ∗ .
Step 1: Obtain (X , Y1 , Y2 ) ∈ (K1 ∩ K2 ) × K∗1 × K∗2 satisfying KKT
condition by APGR method.
k)
Step 2: Update y k by Newton iteration y k+1 := y k − gg′(yor(y k )
secant iteration．

Step 3: µ ← min eig. of G (y k ) − Y2 , ℓk ← max{y k + ρµ, ℓk }Step 4: Obtain [ℓk , y k ](∋ η λ ), k ← k + 1, goto Step1.
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

17 / 36

QapNB: DNN-based Branch-and-bound solver for QAP

QapNB: DNN-based Branch-and-bound solver for QAPWhat is diﬀerent from MIP solver?
• Node relaxation is much harder.
• No warm start.
• No presolving.
solverNuOpt (LP-based B & B)
QapNB

#nodes1.74e+8
195

time/node
4.66-4s
1.97s

Table: comparison between LP-based and DNN-based branch-and-bound withchr20aKoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

18 / 36

QapNB: DNN-based Branch-and-bound solver for QAP

QapNB: DNN-based Branch-and-bound solver for QAP
QAP{ζ ∗ := min ⟨B ⊗ A, xx T ⟩}x ∈ {0, 1}m(I ⊗ e T )x = (e T ⊗ I )x = e.

(1) Incumbent solution• Apply robust tabu search method（ [Tailard 1991] ）to obtain global
upper bound ζ̂.

(2) Stop condition of Newton-bracketing method[Condition 1] Stop if lower bound of DNN ℓk exceeds ζ̂→ prune the node
[Condition 2] Stop if upper bound of DNN y k gets below ζ̂→ branch on the node
(3) Branching strategy (Polytomic branching)

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

19 / 36

QapNB: DNN-based Branch-and-bound solver for QAP

QapNB: DNN-based Branch-and-bound solver for QAP
QAP

{

∗

ζ := min ⟨B ⊗ A, xx ⟩T}

x ∈ {0, 1}m(I ⊗ e T )x = (e T ⊗ I )x = e.

(3) Branching strategy (Polytomic branching)
1. Select facility f → fix xf ,l = 1 for ∀ℓ.
2. Select location ℓ → fix xf ,l = 1 for ∀f .

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

20 / 36

QapNB: DNN-based Branch-and-bound solver for QAP

QapNB: DNN-based Branch-and-bound solver for QAP
Branching strategy
Estimate the score φ(f , ℓ) for unfixed facility f and location ℓ.
average branching
φ(f , ℓ) := avg. obj. value of feasible solutions in QAP(F ∪ f , L ∪ ℓ)primal DNN branching
Step1. Obtain primal feasible solution of DNN Lagrangian relaxation
b := X /⟨H 0 , X ⟩.
X
b onto subproblem space：
Step2. Project primal solution Xbb
X 7→ X (f , ℓ)b (f , ℓ)⟩.
Step3. φ(f , ℓ) := ⟨Q 0 ((F ∪ f ), (L ∪ ℓ)), X

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

21 / 36

QapNB: DNN-based Branch-and-bound solver for QAP

Computational Results of QapNB

problem
nug12
nug14
nug15
nug16anug16bnug17
nug18

ADMM([1])#node time(s)
23
43.74
14
49.56
15
147.8516
144.8431
419.06
188
1151.46805
5071.32BBCPOP([2])#node time(s)
35
31.39
28
73.64
72
138.5946
194.35
197
384.59191
541.90355
1532.24

QapNB#node time(s)
35
20.77
15
28.67
16
34.86
17
42.05
17
57.13
50
97.23
104
143.47

Table: ADMM vs BBCPOP vs NewtonBracket
Mac OSX 10.14.2, Intel(R) Core(TM) i5-8500B CPU @ 3.00GHz[1] Zhenyu Liao. (2016). Branch and bound via the alternating direction methodof multipliers for the quadratic assignment problem.
[2] Koichi Fujii, Naoki Ito, Yuji Shinano (2019). DNN-based Branch-and-boundfor the Quadratic Assignment Problem.
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

22 / 36

QapNB: DNN-based Branch-and-bound solver for QAP

Computational Results of QapNB
problem
nug12
nug14
nug15
nug16anug16b
nug17
nug18
nug20
nug21
nug22
nug24
tai10atai10btai12atai12btai15atai15btai17atai20atai20btai25b
KoichiFujii (MSI)

average branching#nodetime(s)
35
20.77
15
28.67
16
34.86
17
42.05
17
57.13
50
97.23
104
143.47685
1210.33312745.53429
1083.881245
4978.72
11
13.42
11
12.72
34
18.50
34
24.18
188
100.397653.19
364
226.792464
3245.62166
172.22372
1248.68
ParaQapNB

primal DNN branching#nodetime(s)
13
19.66
15
28.97
16
35.03
17
42.35
17
59.36
50
98.58
87
128.86247
509.72218
472.78290596.18586
2807.63
11
13.79
11
12.72
34
18.66
34
25.16
201
108.427654.05
269
169.672525
3169.68166
185.95372
1376.28
2nd UG workshop, 2021

23 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

ParaQapNB: parallelized DNN-based branch-and-boundsolver for QAPUG : Ubiquity Generator Framework• C++ parallel branch-and-bound framework• NuOpt, SCIP and Xpress has been parallelized with UG• New features (Self-splitting ramp-up, etc.) were added for
ParaQapNB

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

24 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

ParaQapNB: parallelized DNN-based branch-and-boundsolver for QAP

Figure: Design of ParaQapNB
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

25 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

ParaQapNB: parallelized DNN-based branch-and-boundsolver for QAP
TIPS for UG (prospective) users:• Insert callback code into your solver• The callbacks should be called as much frequently as possible• Do not worry about load balancing, UG will take care
• Supercomputer is not always available• Test carefully, especially multiple checkpoint loading (how to checkvalidity)• Enjoy working with Yuji (UG)!

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

26 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

ParaQapNB: parallelized DNN-based branch-and-boundsolver for QAP
Self-splitting [M. Fischetti et al. 2014]• The same enumeration tree is initially build by all workers.
• After the sampling phase, each workers solve the nodes which belong
to it.
• Assumuption: sampling phase is not a bottleneck.

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

27 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

ParaQapNB: parallelized DNN-based branch-and-boundsolver for QAP
Self-splitting for ParaQapNB• Avoid redundant sampling• Only with light sampling (branching rule average only)

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

28 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

ParaQapNB: parallelized DNN-based branch-and-boundsolver for QAP

Self-splitting + heuristics for ParaQapNB• Robust Tabu Search [Tailard 1991] + randomization• Extremal Optimization [Boettcher et al 2000]• Memetic Iterated Tabu Search [Silva et al 2020]• Genetic Algorithm [Tate et al 1995]

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

29 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

ParaQapNB: parallelized DNN-based branch-and-boundsolver for QAP
Self-splitting + heuristics for ParaQapNB

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

30 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

Computational Results of ParaQapNB
problem
nug18
nug20
nug21
nug22
nug24
nug25
nug27
tai17atai20atai20btai25bsolver=1#nodetime(s)104165.31
685
1882.153121002.70689
2939.451245
9076.03
8270
59752.86
2610
39234.07379
364.662554
5193.36166
207.62919
4019.42solver=3#nodetime(s)
104
74.86
685
786.94312428.34429
776.801245
3817.108270
25827.81
2610
16506.58
379
143.172949
2258.41166
183.671020
2417.45solver=5#nodetime(s)
104
72.69
685
662.80312366.66429
672.71
1245
3428.928270
22958.26
2610
14303.89
394
121.293069
1988.36166
196.56659
1689.15

Table: computational results of ParaQapNB on medium instances
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

31 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

Computational Results of ParaQapNB

problem
nug18
nug20
nug21
nug22
nug24
nug25
nug27
nug28
tai17atai20atai20btai25bdepth=1#nodetime(s)
104
72.69
685
662.80312366.66429
672.71
1245
3428.928270
22958.26
2610
14303.89
10291
60081.25
394
121.293069
1988.36166
196.56659
1689.15depth=2#nodetime(s)
104
50.55
685
688.19312364.48429
682.61
1245
3382.968270
22221.25
2610
13885.30
10921
57520.11
379
95.17
3304
1973.81220
124.72815
1794.82

depth=3#nodetime(s)
325
31.52
761
588.25632
373.88765
686.171521
3219.328558
21889.72
3026
13715.36
11245
62761.53
394
92.54
3088
1878.41557
109.61
1215
1535.79

depth=4#nodetime(s)5221
110.957241
630.678422
684.379725
1363.2313225
4805.3420242
23278.26
19376
19939.51
28145
63198.93
4489
161.877535
1658.287457
315.8615367
4029.07

Table: computational results of Self-splitting ParaQapNB on medium instanceswith solver=5*depth: sampling tree depth at Self-splitting

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

32 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

Computational Results on Large Instances

problem
nug30
tai30atai35btai40bsko42

Opt.val
6,124
1,818,146
283,315,445
637,250,948
15,812#node
26,181
34,000,579
2,620,547
278,465
6,019,419

time(sec)
3.14e35.81e5 ≈ 6.8 days
2.49e51.05e55.12e5 ≈ 5.9 days

No. of CPU
cores used
1,728
1,728
1,728
1,728
5,184

Table: Computational results on large scale QAPs

• HPE SGI 8600 (384 nodes，13,824 cores，144TB) @ ISM• Adopt average branching as branching strategy• Normal ramp-up
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

33 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

Computational Results on large instances

Figure: ParaQapNB computation log of sko42
KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

34 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

Summary• Newton-bracketing method for Lagrangian DNN relaxation of QAP• QapNB: DNN-based Branch-and-bound solver for QAP(1) Incument solution: robust tabu search(2) Stop condition of Newton-bracketing method(3) Branching strategy: average branching and primal DNN branching• ParaQapNB: massively parallel DNN-based branch-and-bound solver
for QAP• Solved open instances tai30a and sko42.

Fujii, K., Ito, N., Kim, S., Kojima, M., Shinano, Y., & Toh, K. C. (2021).
Solving Challenging Large Scale QAPs. arXiv preprint arXiv:2101.09629.

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

35 / 36ParaQapNB: parallelized DNN-based branch-and-bound solver for
QAP

Conguratulations on UG ver1.0!
• ParaQapNB solved nug24 in 3219.32(s) with 6 processes

Yuji Shinano, Tetsuya Fujie (1999). Parallel Branch-and-Bound Algorithms
on a PC Cluster using PUBB.

KoichiFujii (MSI)ParaQapNB

2nd UG workshop, 2021

36 / 36