polytope
polytope copied to clipboard
tulip-control
improve polytope efficiency
Optimize the heavily used functions and methods in polytope.
Possibly by pushing some things to C using Cython (optional, i.e., installation shouldn't break in case compilation fails).
The profiler says:
ncalls tottime percall cumtime percall filename:lineno(function)
...
10492/7224 0.615 0.000 3.158 0.000 polytope.py:1041(bounding_box)
4158 1.008 0.000 20.218 0.005 polytope.py:1123(envelope)
5126/2873 0.081 0.000 22.546 0.008 polytope.py:1179(mldivide)
82571 8.334 0.000 10.122 0.000 polytope.py:120(__init__)
795/790 0.002 0.000 1.952 0.002 polytope.py:1220(intersect)
2601/2402 0.162 0.000 0.958 0.000 polytope.py:1242(volume)
452 0.001 0.000 0.007 0.000 polytope.py:1290(extreme)
442 0.031 0.000 2.131 0.005 polytope.py:1396(projection)
2 0.000 0.000 0.002 0.001 polytope.py:147(__str__)
2 0.000 0.000 0.006 0.003 polytope.py:1496(separate)
404/123 0.013 0.000 0.082 0.001 polytope.py:1533(is_adjacent)
410 0.045 0.000 1.652 0.004 polytope.py:1633(projection_fm)
4691 1.358 0.000 14.216 0.003 polytope.py:1855(region_diff)
250785 0.039 0.000 0.039 0.000 polytope.py:191(__len__)
6778 0.034 0.000 0.895 0.000 polytope.py:194(__copy__)
6 0.000 0.000 0.001 0.000 polytope.py:2054(box2poly)
10 0.001 0.000 0.013 0.001 polytope.py:2062(_get_patch)
10 0.000 0.000 0.003 0.000 polytope.py:2124(_plot_text)
2247 0.003 0.000 2.291 0.001 polytope.py:221(__eq__)
2247 0.007 0.000 2.288 0.001 polytope.py:227(__le__)
488 0.001 0.000 1.316 0.003 polytope.py:236(union)
3775 0.006 0.000 12.104 0.003 polytope.py:247(diff)
2586 0.035 0.000 2.435 0.001 polytope.py:256(intersect)
6778 0.011 0.000 0.906 0.000 polytope.py:280(copy)
6 0.000 0.000 0.001 0.000 polytope.py:285(from_box)
442 0.002 0.000 2.133 0.005 polytope.py:335(project)
1 0.000 0.000 0.000 0.000 polytope.py:343(scale)
6360 0.006 0.000 0.009 0.000 polytope.py:352(dim)
2306 0.005 0.000 0.806 0.000 polytope.py:361(volume)
1 0.000 0.000 0.000 0.000 polytope.py:367(chebR)
2224 0.003 0.000 0.148 0.000 polytope.py:377(cheby)
10 0.000 0.000 0.018 0.002 polytope.py:390(plot)
1 0.000 0.000 0.000 0.000 polytope.py:424(Region)
11745 0.056 0.000 0.108 0.000 polytope.py:443(__init__)
7591 0.006 0.000 0.008 0.000 polytope.py:474(__iter__)
30 0.000 0.000 0.000 0.000 polytope.py:477(__getitem__)
27866 0.013 0.000 0.017 0.000 polytope.py:492(__len__)
5 0.000 0.000 0.032 0.006 polytope.py:516(__le__)
386 0.007 0.000 33.698 0.087 polytope.py:538(union)
412 0.001 0.000 12.580 0.031 polytope.py:558(diff)
1444/1363 0.016 0.000 4.661 0.003 polytope.py:580(intersect)
1 0.002 0.002 0.254 0.254 polytope.py:59(<module>)
196 0.001 0.000 0.003 0.000 polytope.py:600(__copy__)
196 0.000 0.000 0.003 0.000 polytope.py:605(copy)
1805 0.002 0.000 0.003 0.000 polytope.py:609(dim)
96 0.000 0.000 0.157 0.002 polytope.py:615(volume)
50 0.000 0.000 0.000 0.000 polytope.py:631(cheby)
10 0.000 0.000 0.018 0.002 polytope.py:644(plot)
10 0.000 0.000 0.003 0.000 polytope.py:671(text)
121057/111800 0.154 0.000 0.480 0.000 polytope.py:676(is_empty)
32985 0.112 0.000 4.712 0.000 polytope.py:698(is_fulldim)
2281 0.086 0.000 26.889 0.012 polytope.py:728(is_convex)
2252 0.011 0.000 2.312 0.001 polytope.py:771(is_subset)
13086/13008 2.004 0.000 10.197 0.001 polytope.py:793(reduce)
4283/1311 0.070 0.000 40.449 0.031 polytope.py:897(union)
78070/77939 2.160 0.000 18.825 0.000 polytope.py:977(cheby_ball)
1 0.000 0.000 0.000 0.000 polytope.py:98(Polytope)
An interesting comparison of cvxopt with pulp, its default solver, and with glpk concludes:
The bottom line is:
cvxopt_glpk is 2 to 10 times faster than cvxopt,
cvxopt_glpk and cvxopt are 10 to 70 times faster than PuLP.
This difference is especially significant on small problems.
The last comment is of great interest to usage in tulip partitioning algorithms.
The comparison is relevant also to the branch pulp.