Looking for advice regarding Mixed Integer Programs for cvxpy>=1.1

[Robert Andrew Martin]

Hi all,

I'm the author of PyPortfolioOpt, a python portfolio optimisation package that uses cvxpy on the backend.  Apart from the standard portfolio optimisation functionality, I also have a function that uses linear programming to find the optimal discrete allocation of stocks (integer list), given a set of portfolio weights (float list). 

This was working fine until ECOS_BB was removed in cvxpy 1.1. I pinned my cvxpy dependency to 1.0.38, but this is clearly not a sustainable solution as my users are requesting cvxpy 1.1 support. I was wondering if you had any advice on how I should move forward – I am reluctant to increase PyPortfolioOpt's dependency footprint by requiring the separate installation of other solvers, but any thoughts are appreciated.

For context, the linear program looks like this – by all means if you see any improvements here, let me know:

p = self.latest_prices.values  # latest prices

n = len(p)

w = np.fromiter([i[1] for i in self.weights], dtype=float)

# Integer allocation

x = cp.Variable(n, integer=True)

# Remaining dollars

r = self.total_portfolio_value - p.T * x

# Objective function is remaining dollars + sum of absolute deviations from ideality.

objective = r + cp.norm(w * self.total_portfolio_value - cp.multiply(x, p), 1)

constraints = [r + p.T * x == self.total_portfolio_value, x >= 0, r >= 0]

opt = cp.Problem(cp.Minimize(objective), constraints)

opt.solve()

[Riley Murray]

If you only need mixed-integer linear programs, then adding CVXOPT as a dependency is a very good solution.

CVXOPT comes with GLPK, which is a very reliable mixed-integer solver. By contrast, ECOS_BB is not reliable. The "ECOS" part is great, but the "BB" part has implementation errors that result in returning incorrect solutions (either far-from optimal, or infeasible, or incorrect reports that a problem is infeasible). CVXOPT has even better packaging than CVXPY; in addition to all platforms on anaconda, CVXOPT also has "manylinux" wheels available via pip. CVXOPT, GLPK, and ECOS_BB all share the same GNU GPL license, so your users shouldn't be impacted by adding this dependency.

If you specifically needed mixed-integer nonlinear, and SCIP is not an option, then please post on CVXPY's GitHub page explaining the situation. We have internally discussed the option of adding ECOS_BB back as a solver, but one that you must call *explicitly*. I personally lean away from that option, but if it's really what people need, then it's good for us to know. 

[Robert Andrew Martin]

Really appreciate the input! My problem can be formulated as a MILP with a few variable transformations, so I guess I will try do that and require cvxopt as a dependency. My major concern is that cvxopt comes with a lot of other unnecessary baggage (other C++ libraries) and thus increases the "surface area" for thorny installation issues (particularly when it comes to conda).

Regarding ECOS_BB, it was working quite well for my particular type of problem (I verified the solutions against a less efficient greedy algorithm and there were rarely any problems), so I would definitely be in favour of having ECOS_BB as an explicit solver. Alternatively, has there been any discussion regarding including GLPK by default? I guess it would make sense to have at least one preinstalled mixed-integer solver – the docs say "For licencing reasons, CVXPY does not install any of these solvers by default" but if GLPK and ECOS_BB share the same license, then it should be fine? 

Thanks!
Robert

[Steven Diamond]

After internal discussion, we decided to add ECOS_BB back as a solver that you can call explicitly (but won't be chosen by default). I added it back to master. It'll go out in a patch once we decide how to document ECOS_BB and maybe add more warnings.