improve polytope efficiency

[johnyf]

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)

[johnyf]

For memory profiling one candidate to consider using is memprof.

[johnyf]

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.