cvxopt should be an optional dependency

[slivingston]

cvxopt is a notorious dependency, both in terms of installing and using it. We should aspire to regarding it as optional because

• polytope can still be useful without having an optimization package available, and
• a long-term goal is to create a generic interface to several different optimization packages, and infrastructure to make cvxopt optional is some progress in that direction.

An example of how to achieve this is being considered for introduction into Tulip. The relevant pull request there is 122.

[necozay]

We have replaced all of the cvxopt functionality in polytope using SciPy's LP solver. It is slower than cvxopt with glpk but much faster than cvxopt's native solver. Also it seems numerically stable. Quoting some timing reports on TuLiP examples from Andrew Wagenmaker:

"I was able to run the ‘continuous.py’ script with an input bound of 1.0 in 11:42 using scipy. This is is still much slower than using cvxopt with glpk, which solved it in 1:47, but is much better than cvxopt without glpk. I found a similar result when running ‘pwa.py’ (input bound of 0.4). Scipy ran it in 85.0 seconds and cvxopt with glpk ran it in 17.41 seconds—both better than cvxopt without glpk."

Note that the first example above stalls when using cvxopt native solver (see TuLiP issue #82). More benchmark results using just polytope are available.

I suggest the following changes that will render cvxopt an optional dependency without compromising functionality:

• Make Scipy's LP solver the default option in polytope.
• Keep cvxopt as an optional solver by introducing a flag in appropriate functions (or some other mechanism closer to a generic interface for different optimization packages).

Let me know if you have any suggestions. Andrew can create a pull-request that implements the suggested changes if it sounds OK for everyone.

[johnyf]

I think this is a good option. It can be achieved by trying to use cvxopt.glpk, and falling back to scipy otherwise:

try:
    import cvxopt.glpk
    solver = 'glpk'
except ImportError:
    import scipy._....
    solver = 'scipy'

[johnyf]

On PyPI there are cvxopt == 1.1.9 wheels for all major platforms (manylinux, OS X, and Windows). I was able to install cvxopt with pip install cvxopt in a Python 3 virtualenv on a Debian and have cvxopt.glpk import successfully (and tests pass). This suggests that cvxopt may have reached a better level of installation ease.

This is not to recommend changing install_requires. I think that scipy as the default suffices. But it points out that expanding a current installation to include cvxopt may have become near-trivial.