Skip to content

Instantly share code, notes, and snippets.

@denis-bz

denis-bz/0-Mittelmann-ip-simplex.md

Last active January 26, 2021 16:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save denis-bz/aa5cafdd28448ec3349c7542a3246791 to your computer and use it in GitHub Desktop.
Save denis-bz/aa5cafdd28448ec3349c7542a3246791 to your computer and use it in GitHub Desktop.
Download ZIP
Mittelmann interior-point and simplex benchmarks 24 Jan 2021
Raw
0-Mittelmann-ip-simplex.md

Mittelmann interior-point and simplex benchmarks from http://plato.asu.edu/bench.html

Keywords, tags: linear programming, benchmark, Mittelmann, HiGHS, python, scipy, sparse-matrix

26jan-Mittelmann-ip-simplex

This plot shows the runtimes of various LP interior-point and simplex programs on Mittelmann's benchmark problems.

To plot similar rows / similar columns near each other, I sort rows and columns by their median times. (Medians are scale-invariant -- the sort order is the same for x, x^2, log x.) Comments on better ways of doing this would be welcome.

Notes

Everyone knows that commercial solvers such as Gurobi are waaay faster than any opensource solver. Mittelmann's data supports this. But I don't know which of these dozen solvers

  • are really opensource (not "academic opensource")
  • have doc and support that I like (subjective)
  • talk to python scipy.sparse .

In real-world optimization, an optimizer engine is part of a flow, a cycle, a process:

  • input: map a problem to a sea of numbers A b c ...
  • run the optimizer -> a sea of numbers x[...]
  • map back: make the solution x[...] understandable, with plots and talks
  • check that there are no mistakes along the way.

Amdahl's law certainly applies here.

See also

Interactive Visualizations of Mittelmann benchmarks
lpgen34.py generates LP problems 4n^3 x n^4, with 4 1s in each column and n in each row.

Comments welcome

cheers
-- denis 26 Jan 2021

Theory and practice are closer in theory than they are in practice.

Raw
23jan-Mittelmann-benchmarks-ip-simplex-minutes.csv
We can make this file beautiful and searchable if this error is corrected: It looks like row 2 should actually have 2 columns, instead of 1. in line 1.
# IP and Simplex runtimes from Mittelmann, http://plato.asu.edu/bench.html
# interior point SOLVERi: CLP COPT Gurobi KNITRO MATLAB MDOPT MOSEK TULIP
# from http://plato.asu.edu/ftp/lpbar.html (barrier)
# simplex SOLVERs: CLP COPT GLOP GLPK Gurobi HiGHS MATLAB MDOPT MOSEK SPLX
# from http://plato.asu.edu/ftp/lpsimp.html
# mnz: non-zeros / 1000000
# written 2021-01-23 Jan 11:55z bz merge-ip-simplex.py
problem Guri COPi MOSi MDOs MDOi COPs Gurs KNI MATi TUL CLPi CLPs MOSs MATs GLO HiG SPL GLP mnz
s250r10 0 0 0 0 0 0 0 88 1 _ 1 3 0 6 0 4 4 1 2
neos3 0 0 0 0 0 0 0 1 1 9 5 0 0 _ 7 24 78 53 2
cont1 0 0 6 0 0 0 1 0 0 0 10 5 11 _ 11 186 5 _ 0
qap15 0 0 0 0 0 0 0 1 1 2 2 0 16 9 4 15 172 6 0
fhnw-bin0 0 0 0 0 0 0 0 1 1 0 1 6 3 8 1 32 19 8 1
ex10 0 0 0 0 0 0 0 _ 1 36 _ 1 5 2 13 2 5 _ 1
support10 0 0 0 0 0 0 0 13 2 28 1 1 2 2 1 2 1 22 1
pds-100 0 1 1 0 1 0 0 23 84 _ 161 0 1 2 6 0 22 150 1
square41 0 0 0 0 0 0 0 1 4 1 3 6 110 2 33 1 3 183 14
neos5052403 0 0 0 1 0 0 1 0 1 3 9 4 1 225 8 2 8 78 5
fome13 0 0 0 0 0 0 0 1 3 4 3 1 2 3 4 1 4 54 0
neos 0 1 0 1 0 0 0 7 4 3 6 1 1 5 2 6 1 81 1
irish-e 0 0 0 2 0 0 2 0 1 0 2 8 3 2 _ _ 11 7 1
graph40-40 1 0 0 1 1 0 2 0 1 0 10 15 67 62 68 _ 212 121 1
s100 0 0 0 0 0 0 2 2 4 8 6 9 1 15 0 81 18 4 2
savsched1 1 2 1 0 1 0 8 1 1 1 3 11 18 43 14 10 62 _ 2
nug08-3rd 0 0 2 0 0 0 0 16 17 66 _ 2 17 5 _ 5 20 _ 0
scpm1 0 1 1 1 1 2 4 2 12 11 4 0 72 30 _ 18 14 _ 6
datt256 9 3 4 1 1 5 5 0 1 0 4 6 75 6 34 _ _ 217 2
psched3-3 0 2 1 1 0 1 1 4 8 117 42 16 5 _ 16 18 7 28 1
rmine15 1 1 1 1 1 5 6 39 8 57 _ 5 29 14 10 11 19 129 1
ns1687037 0 0 _ 10 0 14 14 0 3 0 88 6 39 205 25 9 8 47 1
s82 2 3 1 14 3 3 21 _ 100 _ 141 72 46 126 36 _ _ _ 7
Raw
23jan-Mittelmann-benchmarks-ip-simplex-sec.csv
We can make this file beautiful and searchable if this error is corrected: It looks like row 2 should actually have 2 columns, instead of 1. in line 1.
# IP and Simplex runtimes from Mittelmann, http://plato.asu.edu/bench.html
# interior point SOLVERi: CLP COPT Gurobi KNITRO MATLAB MDOPT MOSEK TULIP
# from http://plato.asu.edu/ftp/lpbar.html (barrier)
# simplex SOLVERs: CLP COPT GLOP GLPK Gurobi HiGHS MATLAB MDOPT MOSEK SPLX
# from http://plato.asu.edu/ftp/lpsimp.html
# mnz: non-zeros / 1000000
# written 2021-01-23 Jan 11:55z bz merge-ip-simplex.py
problem Guri COPi MOSi MDOs MDOi COPs Gurs KNI MATi TUL CLPi CLPs MOSs MATs GLO HiG SPL GLP mnz
s250r10 6 12 5 12 12 5 20 5262 54 _ 60 185 20 377 9 230 253 77 2
neos3 3 1 14 2 18 1 3 52 65 566 316 27 7 _ 404 1419 4691 3155 2
cont1 12 8 382 11 14 20 50 2 23 20 602 302 637 _ 656 11169 300 _ 0
qap15 1 1 5 3 4 7 12 41 35 144 95 11 949 550 212 923 10336 368 0
fhnw-bin0 7 2 27 6 20 1 1 48 37 28 48 359 173 456 86 1918 1132 472 1
ex10 10 2 14 3 6 2 5 _ 70 2144 _ 47 329 136 783 105 329 _ 1
support10 5 6 5 12 18 20 14 791 114 1708 53 61 96 116 46 125 49 1308 1
pds-100 25 70 31 19 53 13 12 1391 5022 _ 9661 22 33 143 345 28 1301 9030 1
square41 4 13 9 3 17 6 3 36 222 82 152 364 6586 124 1963 44 152 10955 14
neos5052403 5 12 6 62 11 27 45 28 58 193 538 263 70 13520 481 142 503 4675 5
fome13 2 2 7 6 3 2 5 68 182 252 158 50 123 175 232 65 217 3217 0
neos 8 37 10 32 23 18 9 426 222 173 350 32 70 301 105 357 66 4873 1
irish-e 5 13 7 94 7 29 148 19 47 22 142 450 151 140 _ _ 662 422 1
graph40-40 31 28 20 43 74 21 128 9 63 20 573 871 3991 3697 4102 _ 12737 7274 1
s100 8 11 6 25 15 25 103 112 256 462 355 565 41 889 16 4865 1101 258 2
savsched1 73 113 86 17 77 4 460 37 65 69 205 661 1085 2579 862 573 3736 _ 2
nug08-3rd 26 13 99 14 21 4 14 936 1012 3983 _ 121 1040 282 _ 274 1197 _ 0
scpm1 21 37 31 74 69 95 211 120 718 655 217 27 4305 1802 _ 1097 814 _ 6
datt256 514 168 255 38 46 321 314 18 61 24 238 374 4478 390 2040 _ _ 13013 2
psched3-3 22 105 36 68 24 45 69 238 473 7013 2514 972 287 _ 983 1109 427 1665 1
rmine15 70 59 53 82 41 316 359 2335 501 3422 _ 323 1736 833 593 684 1126 7717 1
ns1687037 23 12 _ 582 21 832 820 10 176 24 5281 343 2336 12297 1501 552 482 2801 1
s82 102 200 78 858 174 192 1251 _ 5986 _ 8488 4299 2746 7585 2143 _ _ _ 7
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment