Ubiquity Generator Framework:

Current Status via a SCIP Application Example
Yuji Shinano
Zuse Institute Berlin

14.01.2019

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

1OutlineØ Notes about the UG design and its dynamic load balancing
Ø Main computational results of ParaSCIP and ParaXpressl Solving previously unsolvable instances of MIP
Ø Some other projects with ParaSCIPl A new feature of SCIP is going to be parallelized
l An application of ug[SCIP,*] libraries
Ø How UG applications were developedØ Future planØ Concluding remarks

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

2OutlineØ Notes about the UG design and its dynamic load balancing

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

3Initial design of ParaSCIP
Two Layered Load Balancing

Goal: run with 10,000 cores

MasterBalancer
LoadCoordinator statuses

Send a node to the LoadCoordinator
LoadCoordinator

LoadCoordinatorstatusespool

statusespool

Solver Solver

16.01.2019

SolverFirst intenational UG workshop 2019, Berlin, Germany

SolverSolver4

Solver

16.01.2019

First intenational UG workshop 2019, Berlin, Germany516.01.2019

First intenational UG workshop 2019, Berlin, Germany

616.01.2019

First intenational UG workshop 2019, Berlin, Germany

716.01.2019

First intenational UG workshop 2019, Berlin, Germany

8

Runtime behavior: timtab2 – 240 cores
1.6e+06

Incumbents
OptimalGlobal LBs

1.5e+06

Objective Function Value

1.4e+06

1.3e+06

1.2e+06

1.1e+06

1e+06

900000800000700000600000
10000

20000

30000

40000

Computing Time (sec.)

1e+08

50000

60000

1000

# nodes left
# active solvers + 1

900

1e+07

800

Number of Nodes

1e+06
700
100000

600

10000

500
400

1000

300
100
200
10

100

1
0

10000

20000

30000

40000

50000

Computing Time (sec.)

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

9

0
60000

Number of Active Solvers + 1

0Runtime behavior: timtab2 – 4096 cores
1.6e+06

Incumbents
OptimalGlobal LBs

1.5e+06

Objective Function Value

1.4e+06

1.3e+06

1.2e+06

1.1e+06

1e+06

900000800000700000

0

1000

2000

3000

4000

5000

6000

Computing Time (sec.)

1e+08

7000

8000

12000

# nodes left
# active solvers + 1

11000

1e+07

10000

Number of Nodes

1e+06

9000
8000

100000

7000

10000

6000
5000

1000

4000

100

3000
2000

10
1

9000

1000
0

1000

2000

3000

4000

5000

6000

7000

8000

Computing Time (sec.)
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

10

0
9000

Number of Active Solvers + 1

600000Runtime behavior: timtab2 – 10000 cores
1.6e+06

Incumbents
OptimalGlobal LBs

1.5e+06

Objective Function Value

1.4e+06

1.3e+06

1.2e+06

1.1e+06

1e+06

900000800000700000

0

5000

10000

15000

Computing Time (sec.)

1e+08

20000

25000

12000

# nodes left
# active solvers + 1

11000

1e+07

10000

Number of Nodes

1e+06

9000
8000

100000

7000

10000

6000
5000

1000

4000

100

3000
2000

10

1000

1
0

5000

10000

15000

0
25000

20000

Computing Time (sec.)
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

11

Number of Active Solvers + 1

600000Ø Algorithmic improvements

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

12

Runtime behavior: timtab2 (improved) – 4096
cores
1.6e+06

Incumbents
OptimalGlobal LBs

1.5e+06

Objective Function Value

1.4e+06

1.3e+06

1.2e+06

1.1e+06

1e+06

900000800000700000

0

500

1e+08

1000

1500

2000

2500

3000

Computing Time (sec.)

3500

4000

4500

15000

# nodes left
# active solvers + 1# nodes recevied/sec# nodes sent/sec

1e+07

5000

14000
13000
12000

1e+06

Number of Nodes

11000
100000

10000
9000

10000

8000
7000

1000

6000
100

5000
4000

10

3000
2000

1

1000
0.1

0

500

0
1000 1500 2000 2500 3000 3500 4000 4500 5000

Computing Time (sec.)
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

13

Number of Active Solvers + 1

600000Runtime behavior: timtab2 (improved) – 10000cores
1.6e+06

Incumbents
OptimalGlobal LBs

1.5e+06

Objective Function Value

1.4e+06

1.3e+06

1.2e+06

1.1e+06

1e+06

900000800000700000

0

2000

4000

6000

8000

Computing Time (sec.)

1e+08

10000

12000

15000

# nodes left
# active solvers + 1# nodes recevied/sec# nodes sent/sec

1e+07

14000
13000
12000

Number of Nodes

1e+06

11000
10000

100000

9000
8000

10000

7000
6000

1000

5000
4000

100

3000
2000

10

1000
1

0

2000

4000

6000

8000

0
12000

10000

Computing Time (sec.)
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

14

Number of Active Solvers + 1

600000Runtime behavior: timtab2 (improved2) – 10000cores
1.4e+06

Incumbents
OptimalGlobal LBs

Objective Function Value

1.3e+06

1.2e+06

1.1e+06

1e+06

900000800000700000

0

500

1000

1500

1e+08

2500

3000

3500

4000

15000

# nodes left
# active solvers + 1# nodes recevied/sec# nodes sent/sec

1e+07
1e+06

Number of Nodes

2000

Computing Time (sec.)

14000
13000
12000
11000

100000

10000

10000

9000
8000

1000

7000

100

6000
5000

10

4000

1

3000
2000

0.1
0.01

1000
0

500

1000

1500

2000

2500

3000

3500

Computing Time (sec.)
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

15

0
4000

Number of Active Solvers + 1

600000Ø Improvements of transfer methods(with racing ramp-ups)

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

16

Runtime behavior: timtab2 (racing) – 4096 cores
1.8e+06

Incumbents
OptimalGlobal LBs

Objective Function Value

1.6e+06

1.4e+06

1.2e+06

1e+06

800000

0

500

1000

1500

2000

Computing Time (sec.)

1e+08

2500

3000

3500

15000

# nodes left
# active solvers + 1# nodes recevied/sec# nodes sent/sec

1e+07

14000
13000
12000

Number of Nodes

1e+06

11000
10000

100000

9000
8000

10000

7000
6000

1000

5000
4000

100

3000
2000

10

1000
1
0

500

1000

1500

2000

2500

0
3500

3000

Computing Time (sec.)
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

17

Number of Active Solvers + 1

600000Runtime behavior: timtab2 (racing) – 10000 cores
1.8e+06

Incumbents
OptimalGlobal LBs

Objective Function Value

1.6e+06

1.4e+06

1.2e+06

1e+06

800000

0

500

1000

1500

2000

2500

3000

Computing Time (sec.)

1e+08

3500

4000

15000

# nodes left
# active solvers + 1# nodes recevied/sec# nodes sent/sec

1e+07

14000
13000
12000

1e+06

Number of Nodes

11000
100000

10000
9000

10000

8000
7000

1000

6000
100

5000
4000

10

3000
2000

1

1000
0.1
0

500

1000

1500

2000

2500

3000

3500

Computing Time (sec.)
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

18

0
4000

Number of Active Solvers + 1

600000Outline
Ø Main computational results of ParaSCIP and ParaXpressl Solving previously unsolvable instances of MIP

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

19

Solving open instances from MIPLIB2003
ds, stp3d were solved
by ParaSCIP
Last instances solved.
Four instances arestill open.

6 instances have not been solved 7 Years• ds – 656 constraints, 67,732 binary variables• stp3d – 159,488 constraints, 204,880 binary variables
After applying SCIP presolving 9 times:
88,388 constraints, 123,637 binary variables
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

20

Solving open instances from MIPLIB2003
ds, stp3d were solved
by ParaSCIP
Last instances solved.
Four instances arestill open.

ds: Set partitioning problem originating from public transport service planning.
This instance was solved by a first implementation of ParaSCIP using up to 2048 cores of HLRNII(http://www.hlrn.de). ParaSCIP, mainly developed by Yuji Shinano, is an extension of SCIP and realizes aparallelization on a distributed memory computing environment. For being able to interrupt and warmstart thecomputations, ParaSCIP has a checkpoint mechanism. Therefore, selected subproblems are stored as warm
start information, which allows to virtually run ParaSCIP, although the HLRN-II environment imposes a time limitof 48 hours per run. It took approximately 86 hours to solve this instance.
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

21

Solving open instances from MIPLIB2003
ds, stp3d were solved
by ParaSCIP
Last instances solved.
Four instances arestill open.

stp3d: 3D Steiner Tree packing problem (VLSI routing problem in a multi-layer grid graph)
This instance was solved by a first implementation of ParaSCIP using up to 2048 cores of HLRN-II(http://www.hlrn.de).
ParaSCIP, mainly developed by Yuji Shinano, is an extension of SCIP and realizes a parallelization on a distributed
memory computing environment. For being able to interrupt and warmstart the computations, ParaSCIP has a checkpointmechanism. Therefore, selected subproblems are stored as warm start information, which allows to virtually run
ParaSCIP, although the HLRN-II environment imposes a time limit of 48 hours per run. The problem was presolved
several times with SCIP presolving techniques. After that, it took approximately 114 hours to solve this instance.
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

22Restarted runs vs. single run
run

cores

time[h]

1

512

4

2

1024

5

3

2048

10

4

2048

7

5

2048

4

6

2048

5

7

2048

4

8

2048

5

9

2048

5

10

2048

4

11

2048

4

12

2048

5

HLRN II supercomputer (SGI Altix ICE 8200EX)
maximum cores for a job: 4096

13

2048

10

14

2048

4

15

2048

4

Answer is “restarted runs”

16

2048

12

17

2048

4

Ø Which run was efficient froma view point of solving ds?
l restarted runs: [STAGE 1(old)]l approximated comp. time:
86 [h]
l real resource requested time:
96 [h]
l cumulative time:
181,248 [h]Ø single run: [STAGE 2(new)]l comp. time:
76[h]l cumulative time: 4096 x 76 = 311,296 [h]Summary
Accumulated time
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

23

96
181248FiberSCIP and its paperØ Preliminary results were presented in MIPLIB2010 paper(Started working in 2010)
Ø Computational results had been checked two years
l 87 instances of many different setttings with five repeated runsl All numbers in the supplement were checked carefully
Ø Submitted the paper in 2013
Ø Publish the paper in 201816.01.2019

First intenational UG workshop 2019, Berlin, Germany

24

# Nodes / # Active Solvers + 1

What does scale up do for a hard instance? (dano3mip)
1e+08

on HLRN III
by using 17,088 cores
starting from 33,332
branch-and-bound nodes

1e+07
1e+06
100000
10000
1000
100
10
1
0.1
0

10000 20000 30000 40000 50000 60000 70000 80000 90000

Computing Time (sec.)# Nodes / # Active Solvers + 1# nodes left
# active solvers + 1# nodes recevied/sec# nodes sent/sec
Ramp-upon Titanby using 35,200 cores
starting from 33,481
branch-and-bound nodes

1e+10
1e+08
1e+06
10000
100
1
0.01
0

5000

10000 15000 20000 25000 30000 35000 40000 45000

Computing Time (sec.)# nodes left
# active solvers + 1# nodes recevied/sec

16.01.2019# nodes sent/sec
Ramp-upFirst intenational UG workshop 2019, Berlin, Germany

Large scale canbreak down
problem intosolvable sub-MIPs
25

The biggest and the longest computation
Solving rmine10: 48 restarted runs with 6,144 to 80,000 cores
Incumbents
Global LBs-1912.5

Titan with 80,000 cores
The others: HLRN III-1913-1913.5-1914-1914.5-1915-1915.5
-1916
0

1x10

6

2x10

6

3x10

6

4x10

6

5x10

6

6x10

6

7x10

6

Computing Time (sec.)

How upper and lower bounds evolved

Number of Nodes

90000# nodes left
# active solvers# nodes in check-point file

1x1010

80000
70000

1x108
1x10

60000

6

50000
40000

10000

30000
20000

100

10000
1
0

1x106

2x106

3x106

4x106

5x106

6x106

It took about 75 days and5,660 years of CPU core
hours!
Number of Active Solvers + 1

Objective Function Value-1912

UG canhandle up
to 80,000
MPI process

0
7x106

Computing Time (sec.)

How open nodes and active solvers evolved
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

26

ParaXpress: Need to corporate with Xpress developers
TnOriginal min{c x : Ax  b, l  x  u, for all xj 2 Z , j 2 I}
0<latexit sha1_base64="zizyCePbNpR/n01lIWlRxUylmJQ=">AAACyHichVFNb9QwEJ2GAmX56EIvSFwsVkUcVqsJQgL1VOgFeurXthVNu4qNtzV1nCjxLrtYuXDsH+ihJ5AQQv0ZXOAHcOhPQBw4FAmQODCbREJQARPFfvM8b/xs80SrzCIejXmnxk+fOTtxrnb+wsVLk/XLV1azuJcK2RaxjtN1HmZSKyPbVlkt15NUhhHXco3vzo3W1/oyzVRsVuwwkZtRuG1UV4nQEtWpiyBSJnBiywVRaHeyrlvJ8wGbYfcGLNCS8SbTBSjTXpMFEY8HrhunLNSa5WzQecICZVih59w9yrecyZusZB+yIO/UG9jCIthJ4FegAVUsxPXXEMBjiEFADyKQYMAS1hBCRt8G+ICQELcJjriUkCrWJeRQI22PqiRVhMTu0rhN2UbFGspHPbNCLWgXTX9KSgbT+AHf4DG+w0P8iD/+2ssVPUZehjTzUiuTzuTe1eWv/1VFNFvY+aX6p2cLXbhbeFXkPSmY0SlEqe8/2z9enlmadjfwJX4i/y/wCN/SCUz/i3i1KJcOoEYP4P953SfB6q2Wjy1/8XZj9n71FBNwDa7DTbrvOzALD2AB2rTve/gM3+C7N+8l3lNvWJZ6Y5VmCn4L7/lPtGivDw==</latexit>

min{c0T x0 : A0 x0  b0 , l0  x0  u0 , for all x0 j 2 Zn , j 2 I 0 }LoadCoordinatorwaiting:running:<latexit sha1_base64="W8ZrOn3UyByfIjqz2nlFlRnGvrQ=">AAADpnichVHLbtQwFL1peJTh0SlskNhYjIq6QCOnQgJ1NcAGNqiv6VTUnSF2Pa2p40SJZ9Ri5Qf4ARasQEIV4jPYsGEJqJ+AWBaJDQvuZCIhaAZulPj63HNO7rV5olVmKT3ypvxTp8+cnT5XO3/h4qWZ+uzl9SwepEK2RazjdIOHmdTKyLZVVsuNJJVhxLXs8L37o3pnKNNMxWbNHiRyKwp3jOorEVqEerNei0XKMCe6zrHCzqVyO2dJqiKZOxaFdjfru7U8z/e7FQyySO5W4dVkpiXhVZWbRE8UTLYaVFuxiMf7rh+nJNSa5NUGvaeEKUOKATl3j/OuM1U89BszH1a3kffqDdqkRZCTSVAmDShjKa4fAoNtiEHAACKQYMBiriGEDJ9NCIBCgtgWOMRSzFRRl5BDDbUDZElkhIju4XcHd5slanA/8swKtcC/aHxTVBKYo5/oW3pMP9B39Cv9OdHLFR6jXg5w5WOtTHozz6+u/vivKsLVwu5v1T97ttCHO0WvCntPCmQ0hRjrh89eHK8ursy5G/Q1/Yb9v6JH9D1OYIbfxZtlufISangBwd/HfTJZX2gGtBks32q07pVXMQ3X4DrM43nfhhY8gCVog/AOvY/eZ++LP+8/8tt+Z0yd8krNFfgj/Ce/AHmdC80=</latexit>
sha1_base64="bs8QlLljyYde7WbNFuyzJJm+ZMk=">AAACVXichVG7SgNBFD1ZX3F9JMFGsAmGiFW4a6NYCTaWeZgHxBB2N6Mu2ewuu5tADP5AWgsLKwUR8TNs/AGL9DZiGcHGwrubgKiod5iZM2fm3DlzR3NMw/OJBhFpYnJqeiY6K8/NywuLsfh8ybPbri6Kum3abkVTPWEalij6hm+KiuMKtaWZoqw1d4P9cke4nmFb+37XEbWWemQZh4au+kxl6/EUZSiM5E+gjEEK47DjNzhAAzZ0tNGCgAWfsQkVHrcqFBAc5mroMecyMsJ9gVPIrG3zKcEnVGabPB7xqjpmLV4HOb1QrfMtJneXlUmk6ZFuaUgPdEfP9P5rrl6YI/DS5VkbaYVTj/WXC2//qlo8+zj+VP3p2cchtkKvBnt3QiZ4hT7Sd07Oh4XtfLq3Rlf0wv4vaUD3/AKr86pf50T+AjLXX/le7Z+gtJFRKKPkCFGsYBXrXOZN7GAPWRT5ugb6OIs8SbKUGP2TFBl/WAJfQlr6AAYJh7c=</latexit>
sha1_base64="8ov7DBxIpnGSfT7+D72nu94Lyfc=">AAADm3ichVFNb9QwEJ00fJSl0C0nJC4WVVEPaOVwadVTERd6Qf3abkXdXcWutzV1nMjJrlos/4H+AQ6cQEIV4mdw4cIRUH8C4lgkLhyYza6EoFmYKPH4zXsvMzbPtMoLSs+CifDS5StXJ6/Vrk/duDldn5naytOeFbIpUp3abR7nUisjm4UqtNzOrIwTrmWLHz4a1Ft9aXOVms3iOJO7SbxvVFeJuECoMxMss0QZ5kTbOVbaOSv3PMusSqR3LImLg7zrNr33R+0KBlkiD6vwajLTkvCqyn2ixwrGW/WqrVjC0yPXTS2JtSa+2qDzjDBlSDkg5+6pbztTxUO/IXOlug3fqc/SBi2DXEyiUTILo1hN66fAYA9SENCDBCQYKDDXEEOOzw5EQCFDbBccYhYzVdYleKihtocsiYwY0UP87uNuZ4Qa3A8881It8C8aX4tKAnP0E31Lz+kH+o5+pT/HernSY9DLMa58qJVZZ/rk9saP/6oSXAs4+K36Z88FdGGx7FVh71mJDKYQQ33/+YvzjaX1OXePvqbfsP9X9Iy+xwlM/7t4sybXX0INLyD6+7gvJlsPGhFtRGsUJuEO3IV5POYFWIbHsApNEMFp8DH4HHwJ58MnYXN4VRPB6M5uwR8Rtn4B7T0Kug==</latexit>
sha1_base64="WdRjzyQtY2jqLVwtqI9pxgCDbTA=">AAADpnichVE9b9RAEB3HQMLxkQs0SDQrTkEp0GlMA0p1gQYalK/LRWRzh9fZS5asP7T2nRJW/gP8AQoqkFCE+Bk0NJSA8hMQZZBoKJjzWUIQH4xl7+yb955ndkWiVZohHjtT7pmz56ZnztcuXLx0ebY+d2UjjQcmkO0g1rHZFH4qtYpkO1OZlpuJkX4otOyI/fujemcoTariaD07TOR26O9Gqq8CPyOoN+e0eKgiboOutbyws0bu5DwxKpS55aGf7aV9u57n+UG3gsEW2VIVXk3mWjJRVbnF9ETBZKtBtRUPRXxg+7FhvtYsrzboPWVcRawYUAj7OO/aqIpHfmPmw+o28l69gU0sgp1OvDJpQBnLcf0IOOxADAEMIAQJEWSUa/AhpWcLPEBICNsGS5ihTBV1CTnUSDsgliSGT+g+fXdpt1WiEe1HnmmhDugvml5DSgbz+Anf4gl+wHf4FX9O9LKFx6iXQ1rFWCuT3uzza2s//qsKac1g77fqnz1n0Ie7Ra+Kek8KZDRFMNYPn704WVtcnbc38TV+o/5f4TG+pwmi4ffgzYpcfQk1ugDv7+M+nWzcbnrY9Faw0bpXXsUMXIcbsEDnfQda8ACWoQ2Bc+R8dD47X9wF95Hbdjtj6pRTaq7CH+E++QV4XQvJ</latexit>

Base solver
I/O , presolve(l0 i , u0 i )<latexit sha1_base64="10xjq4eOhr7+RYqPaKofHT4jWfI=">AAACl3ichVHLLgRBFD3ae7wGG2IzMSEkMrktEmJDSMTSYJAYJt2tUNGvdPdMQmd+wA+QWJGIiH+wseAHLHyCWJLYWLjT04l4305XnTr3nlunqnTXlH5A9FCj1NbVNzQ2NSdaWtvaO5KdXSu+U/QMkTMc0/HWdM0XprRFLpCBKdZcT2iWbopVfW+2kl8tCc+Xjr0c7Ltiw9J2bLktDS1gqpAcHTI3w3zUJ/TEVjnvetIS5YIcSRV/TgwXkmnKUBSp70CNQRpxLDjJC+SxBQcGirAgYCNgbEKDz986VBBc5jYQMucxklFeoIwEa4tcJbhCY3aPxx1erceszetKTz9SG7yLyb/HyhQG6J4u6Znu6Ioe6e3XXmHUo+Jln2e9qhVuoeOwZ+n1X5XFc4DdD9WfngNsYyLyKtm7GzGVUxhVfeng6HlpcnEgHKQzemL/p/RAN3wCu/RinGfF4gkS/ADq1+v+DlZGMypl1OxYenomfoom9KEfQ3zf45jGPBaQ432PcY1b3Cm9ypQyp8xXS5WaWNONT6Fk3wGYB56k</latexit>

presolved
instancepresolved
instance

First: restrictedpresolved
instance
Current: presolved
instancepresolved
presolved
instance
instance
Presolve again with added
bound changes

00min{c00T x00 : A00 x00  b00 , l00  x00  u00 , for all x00 j 2 Zn , j 2 I 00 }<latexit sha1_base64="JMgJVJU5DukesAYgXcclOJbzq7g=">AAAD6HichVHLbtQwFL2T8CjDY6awKWJjMSpigUZOhQTqqpQN7PqatqLujBLX07p1Hko8o7ZWNixZsasQKypVFeIz2PADLPoJFcsisWHBnSQSgiqZa8W+Pveck2vbi5RMNKVnNcu+cvXa9Ykb9Zu3bt9pNCfvribhIOaiw0MVxuuemwglA9HRUiuxHsXC9T0l1ry9l6P62lDEiQyDFX0QiU3f3Q5kX3JXI9SbrL1lvgyY4V1jWGZnYrGVsiiWvsjn1DDf1TtJ36ykabrfLeWRWfKivFolZEoQr7z+hKgx4nHmgypz5nvhvumHMXGVImmVWW+XMBmQ7EI8z7xJuyYoZ6N3zn9d1V7aa7Zom2ZBLidOkbSgiIWweQoMtiAEDgPwQUAAGnMFLiQ4NsABChFim2AQizGTWV1ACnXUDpAlkOEiuofzNu42CjTA/cgzydQc/6Lwi1FJYJp+p5/pBf1Gv9Bz+rvUy2Qeo14OcPVyrYh6jXdTy7/GqnxcNez8VVX2rKEPz7NeJfYeZcjoFDzXDw+PLpZnl6bNI3pMf2D/n+gZ/YonCIY/+cmiWPoIdXwA5//rvpyszrQd2nYWn7bm5ounmIAH8BAe430/gzl4BQvQAV47txrWlHXf3rXf20f2h5xq1QrNPfgn7OM/yLsmlw==</latexit>

Solver 1

Solver 2

Solver 3

Solver n

Solver 4

All transfer data need to be converted back for the presolved instanceAll feasible solutions need to be converted back for the original instance
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

27

FiberXpress: UG Solver threads with Xpress threads
UG 4 Xpress 4
FiberXpress process
LoadCoordinator thread
UG
SolverthreadXpressUG
SolverthreadXpressUG
SolverthreadXpressXpressUG
SolverthreadXpressthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadShared Memory

Internal
Parallelization
Of Xpress
Berthold T., Farmer J., Heinz S.,
Perregaard M. (2016)
Parallelization of the FICO XpressOptimizer. In: Greuel GM., Koch T.,
Paule P., Sommese A. (eds)
Mathematical Software – ICMS
2016. ICMS 2016. Lecture Notes in
Computer Science, vol 9725.
Springer, Cham

: CPU core

Shared Memory Machine (PC)16.01.2019

First intenational UG workshop 2019, Berlin, Germany

28

ParaXpress: UG Solver processes with Xpress threads
ug[Xpress,MPI] : ParaXpressu A powerful massively parallel MIP solveru Can handle, hopefully efficiently, up to
80,000 (MPI processes ) x 24 (threads) = 1,920,000 (cores)

Connection network

ParaXpress
LoadCoordinator
Process
XpressUG
Solverprocess
XpressUG
Solverprocess
XpressUG
Solverprocess
XpressUG
Solverprocess
XpressUG
Solverprocess
XpressUG
Solverprocess
XpressUG
Solverprocess
XpressthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadthreadShared Memory

Shared Memory

Processing Element or Compute node

Processing Element or Compute node

: CPU core

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

29Computational results of FiberXpress# of solved instances

Computing Time (sec.)

37: Xpress 16

Xpress 16

time limit 7200 sec
Racing settings:
25 parameter settings+ random seed

Ø Xpress 8.3 and UG-0.8.4 – dev.
Ø 28 core Intel Xeon CPU E5-2690 v4 CPUs at 2.6 GHz with
35MB cache and 128GB memoryØ 52 instances from Tree test set from MIPLIB2010 (6 instances were solved at root by Xpress 16)
Ø Geometric mean (Time out is counted as 7200 sec.)

Price of externalization is dramatically decreased
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

30

Computational results of ParaXpress

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

Gap(%)

Computing Time (sec.)

Gap(%)

Computing Time (sec.)

Ø Solving timtab2 from MIPLIB2003
Ø The experimental implementation
Ø Xpress 7.9 and
UG-0.8.2
Ø HLRN III:
Cray XC30 with 24 coreIntel E5-2695 v2 CPUs
at 2.4GHz, 64GB Memory
per computing node
6144 cores are used
Ø New implementation
Ø Xpress 8.3 and
UG-0.8.4 – dev.
Ø ISM Supercomputer System "I”:
SGI ICE X with 12 cores Intel
Xeon E5-2697v2 at 2.7GHz(2CPUs), 128GB memory percomputing nodeØ 192 cores are used31

Solving open instances from MIPLIB2010
http://miplib2010.zib.de

MIPLIB2010
waspublished
HLRN II -> HLRN III
7,000 cores -> 43,000 cores

ParaXpress
started16.01.2019

First intenational UG workshop 2019, Berlin, Germany

New ParaXpress

32Solving open instances from MIPLIB2017
Ø Open instances which could not be generated any feasible
solution for all solvers

ISM (Institute of Statistical Mathematics) supercomputer, which is a HPE SGI 8600 with
384 compute nodes, each node has two Intel Xeon Gold 6154 3.0GHz CPUs (18cores×2) sharing 384GB of memory, by using ParaSCIP and ParaXpress
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

33

ParaXpress (= ug[Xpress, MPI]) statusØ ParaXpress can be upgraded new version of Xpress without UG codechangeØ ParaXpress is ready to run on over a million CPU cores!
l

We need an application in which the optimal solution is very important in
the research field

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

34

OutlineØ Some other projects with ParaSCIPl A new feature of SCIP is going to be parallelized

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

35

A new feature of SCIP (Added by Stephen J. Maher )16.01.2019

First intenational UG workshop 2019, Berlin, Germany36

A new feature of SCIP (Added by Stephen J. Maher )16.01.2019

First intenational UG workshop 2019, Berlin, Germany

37

Outlinel

An application of ug[SCIP,*] libraries

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

38

Overview

Developed by Keiji Kimura

Problems
AIC-based variable selection

in linear regression and logistic regression) mixed integer nonlinear programming problems (MINLP)

Algorithm proposed in [1, 2]
Branch-and-bound (B&B) algorithm using SCIP and UG
Developed additional plugins:
Relaxation handler (to compute lower bounds eﬃciently)
Primal heuristics (to ﬁnd good solutions early)
Branching rules (to reduce branch-and-bound nodes)[1] K. Kimura and H. Waki: Minimization of Akaikeʼs information criterion in linear regression analysis
via mixed integer nonlinear program. OMS, 33(3), 633‒649, 2018.
[2] K. Kimura: Applicationof a mixed
integerUG
nonlinearapproach to
16.01.2019
39 variable selection
First intenational
workshop 2019,programming
Berlin, Germany
in logistic regression. JORSJ, 62(1), to appear.

Problems

Developed by Keiji Kimura

Variable Selection

provides a simple statistical modelﬁnds a subset of relevant variables
improves prediction performance

Direct Objective Optimization in Variable Selection
f : the goodness-of-ﬁt (how well a model ﬁts a given dataset)Pzj ( > 0) : a penalty for the number of variables
The problems in [1, 2]
are of the following form

min f ( ) +
,z

s.t.

X

zj

j2J

zj = 0 ) j = 0 8j 2 J,
j 2 R, zj 2 {0, 1} 8j 2 J.

[1] K. Kimura and H. Waki: Minimization of Akaikeʼs information criterion in linear regression analysis
via mixed integer nonlinear program. OMS, 33(3), 633‒649, 2018.
[2] K. Kimura: Applicationof a mixed
integerUG
nonlinearapproach to
16.01.2019
40 variable selection
First intenational
workshop 2019,programming
Berlin, Germany
in logistic regression. JORSJ, 62(1), to appear.

Numerical Experiments in [2]Problem: AIC-based variable selection in logistic regression
Comparison of Approaches:

Customized B&B algorithm [2]- using SCIP and UG
Piecewise linear approximation approach [Sato, et al., 2016]- using CPLEX to solve MILP problems- employing existing heuristics for initial solutions

Benchmark datasets: UCI machine learning repository(https://archive.ics.uci.edu/ml/)[2] K. Kimura: Application of a mixed integer nonlinear programming approach to variable selection
in logistic regression.
JORSJ, 62(1),to appear.
16.01.2019
41
First intenational
UG workshop 2019, Berlin, Germany

Numerical Experiments in [2](16 threads)

Approach 1

Approach 2

Name

n

p

AIC

Time(s)AIC

Time(s)bumps
breast-P
biodegstat-G
madelon

2584
194
1055
1000
2000

22
34
42
62
500

1097.1
147.0
653.3
958.2
2502.1

20.0
25.8
221.5
>5000
>5000

1098.1
147.0
653.3
958.2
2504.0

41.5
112.4
>5000
>5000
>5000

Approach 1: Customized B&B algorithm [2] (SCIP and UG)

Approach 2: Piecewise linear approximation approach (CPLEX)
n: the number of observations
p : the number of candidates for variables[2] K. Kimura: Application of a mixed integer nonlinear programming approach to variable selection
in logistic regression.
JORSJ, 62(1),to appear.
16.01.2019
42
First intenational
UG workshop 2019, Berlin, Germany

OutlineØ How UG applications were developed

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

43Instantiated parallel solvers by UG
The following solvers have developed by Yuji Shinano
cooperated with each solver developers
Ø Single thread base solverlParaSCIP: ug[SCIP, MPI], FiberSCIP: ug[SCIP, Pthreads/C++11]Ø Multi-threaded base solver
ParaXpress: ug[Xpress, MPI], FiberXpress: ug[Xpress, Pthreads/C++11]
Ø Concorde: TSP solver
l ug[Concorde, MPI], ug[Concorde, Pthreds/C++11]
l ug[Concorde/MPI, MPI]
• Concorde/MPI has developed by Utz-Uwe Hausl16.01.2019

First intenational UG workshop 2019, Berlin, Germany

44Instantiated parallel solvers by UG
The following solvers have developedby each base solver developers.
Skelton code was distributed.
Design and coding together with Yuji Shinano
about one week in the beginningØ Multi-threaded base solverl

ParaNUOPT: ug[NUOPT, MPI], FiberNUOPT: ug[NUOPT, Pthreads/C++11]• Only tested with single thread NUOPTØ Distributed base solverlug[PIPS-SBB, MPI]
• PIPS-SBB: a distributed memory solver for Stochastic MIP

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

45

Skelton code

Rename: baseSolver->your_solver_name, Fill codes for all virtual functions
baseSolverParaCommPointHdlr.cpp: CommPoint is a callback of solver
to communicate with LoadCorrdinator16.01.2019

First intenational UG workshop 2019, Berlin, Germany

46

Built parallel solvers with ug[SCIP,*] libraries

The following solvers have developedby each SCIP plugins developers.
Debugged with Yuji ShinanoØ ug[SCIP-Jack,*]l Parallel solvers for solving Steiner Tree Problems
Ø ug[SCIP-SDP,*]l Parallel solvers for solving Mixed Integer Semidefinite Programs

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

47

OutlineØ Future plan

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

48

Plan for UG 1.0
Ø If you have your own state-of-the-art solver,
please try to parallelize it with UG
Ø If you have SCIP application,please try to parallelize it with ug[SCIP,*] libraries

We hope to have feedbacks from user sideØ Second UG workshop will be held in two years,
since “Sustainable Infrastructures for Archiving and Publishing HighPerformance Optimization Software” is three years projectl Right after the workshop, UG 1.0 would be released
16.01.2019

First intenational UG workshop 2019, Berlin, Germany

49

OutlineØ Concluding remarks

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

50

Concluding remarks
Ø A research platform for parallel branch-and-boundl Users can run all parallel solvers by themselves for fair directcomparison• source codes are publically available• test data are publically available

16.01.2019

First intenational UG workshop 2019, Berlin, Germany

51