cvxpy
Using python-mip library with cvxpy syntax
I need to use CBC solver for mixed integer optimization problem, however in the target environment I cannot use CBC solver installed as an outsource software, it has to be a part of the python library. To overcome this problem I found mip library https://pypi.org/project/mip/ https://docs.python-mip.com/en/latest/index.html which comes with build-in CBC solver, which can be used only having this library imported, with no need for CBC solver installed separately. My problem is, I already have tons of code written with cvxpy (using this separate CBC solver). Now the question is, is there any possibility to use CBC built in mip library, but use it from regular cvxpy interface? Without changing the code, rewriting everything to mip sytax etc.
Sample code I would need to rewrite to mip syntax:
import numpy as np
import cvxpy as cp
import cvxopt
import mip
def run_sample_optimization():
demand = np.array([[100, 500, 30], [20, 200, 50], [150, 15, 35], [10, 5, 25]])
product_supply = np.array([550, 200, 170, 40])
allocation = cp.Variable(demand.shape, integer=True)
objective = cp.Maximize(cp.sum(allocation/demand))
constraints =[cp.sum(allocation, axis=1) <= product_supply,
allocation <= demand,
allocation >= 0]
problem = cp.Problem(objective, constraints)
optimal_value = problem.solve(solver=cp.GLPK_MI) # <-- it would be perfect to link somehow from this place to CBC implemented in mip library
print('product supply:', product_supply)
print('demand:\n', demand)
print('allocation:\n', allocation.value)
print('calculated score:', optimal_value)
return product_supply, demand, allocation.value, optimal_value
Many thanks in advance!
This is very interesting. I didn't know there was a python package that included CBC. If you're up for it, you can try modifying the CBC interface to use this new library: https://github.com/cvxgrp/cvxpy/blob/master/cvxpy/reductions/solvers/conic_solvers/cbc_conif.py
Guidance on writing interfaces is here: https://www.cvxpy.org/contributing/index.html#solver-interfaces
If you end up doing this, please make a PR! It would be a very helpful contribution.
Thanks for suggestions @SteveDiamond. Parallel I posted the same question on python-mip community https://github.com/coin-or/python-mip/issues/182 and indeed thanks to @jurasofish I have now a custom solver interface built and it looks like that:
# mip_conif.py
"""
Based on
https://github.com/cvxgrp/cvxpy/
blob/5d5c7d606e39b3ea4b54391f772c7e3dc38ede20/cvxpy/reductions/
solvers/conic_solvers/cbc_conif.py
Copyright 2016 Sascha-Dominic Schnug
Copyright 2021 Michael Jurasovic
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
"""
import cvxpy.settings as s
from cvxpy.reductions.solvers.conic_solvers.cbc_conif import (
CBC,
dims_to_solver_dict,
)
from cvxpy.reductions.solvers.conic_solvers.conic_solver import ConicSolver
from cvxpy.reductions.solution import Solution, failure_solution
import numpy as np
class PYTHON_MIP(CBC): # uppercase consistent with cvxopt
""" An interface to the python-mip solver
"""
# Solver capabilities.
MIP_CAPABLE = True
SUPPORTED_CONSTRAINTS = ConicSolver.SUPPORTED_CONSTRAINTS
def name(self):
"""The name of the solver.
"""
return "PYTHON_MIP"
def import_solver(self):
"""Imports the solver.
"""
import mip
_ = mip # For flake8
def accepts(self, problem):
"""Can python-mip solve the problem?
"""
# TODO check if is matrix stuffed.
if not problem.objective.args[0].is_affine():
return False
for constr in problem.constraints:
if type(constr) not in self.SUPPORTED_CONSTRAINTS:
return False
for arg in constr.args:
if not arg.is_affine():
return False
return True
def apply(self, problem):
"""Returns a new problem and data for inverting the new solution.
Returns
-------
tuple
(dict of arguments needed for the solver, inverse data)
"""
data, inv_data = super(PYTHON_MIP, self).apply(problem)
variables = problem.x
data[s.BOOL_IDX] = [int(t[0]) for t in variables.boolean_idx]
data[s.INT_IDX] = [int(t[0]) for t in variables.integer_idx]
return data, inv_data
def invert(self, solution, inverse_data):
"""Returns the solution to the original problem given the inverse_data.
"""
status = solution['status']
if status in s.SOLUTION_PRESENT:
opt_val = solution['value'] + inverse_data[s.OFFSET]
primal_vars = {inverse_data[self.VAR_ID]: solution['primal']}
return Solution(status, opt_val, primal_vars, None, {})
else:
return failure_solution(status)
def solve_via_data(self, data, warm_start, verbose, solver_opts, solver_cache=None):
# Import basic modelling tools of cylp
import mip
c = data[s.C]
b = data[s.B]
A = data[s.A]
dims = dims_to_solver_dict(data[s.DIMS])
n = c.shape[0]
# Problem
model = mip.Model(solver_name=mip.CBC)
# Variables
x = []
bool_idxs = set(data[s.BOOL_IDX])
int_idxs = set(data[s.INT_IDX])
for i in range(n):
if i in bool_idxs:
x.append(model.add_var(var_type=mip.BINARY))
elif i in int_idxs:
x.append(model.add_var(var_type=mip.INTEGER))
else:
x.append(model.add_var())
# Constraints
# eq
def add_eq_constraints(_model):
coeffs = A[0:dims[s.EQ_DIM], :]
vals = b[0:dims[s.EQ_DIM]]
for i in range(coeffs.shape[0]):
coeff_list = np.squeeze(np.array(coeffs[i].todense())).tolist()
expr = mip.LinExpr(variables=x, coeffs=coeff_list)
_model += expr == vals[i]
add_eq_constraints(model)
# leq
def add_leq_constraints(_model):
leq_start = dims[s.EQ_DIM]
leq_end = dims[s.EQ_DIM] + dims[s.LEQ_DIM]
coeffs = A[leq_start:leq_end, :]
vals = b[leq_start:leq_end]
for i in range(coeffs.shape[0]):
coeff_list = np.squeeze(np.array(coeffs[i].todense())).tolist()
expr = mip.LinExpr(variables=x, coeffs=coeff_list)
_model += expr <= vals[i]
add_leq_constraints(model)
# Objective
model.objective = mip.minimize(mip.LinExpr(variables=x, coeffs=c.tolist()))
model.verbose = verbose
status = model.optimize()
status_map = {
mip.OptimizationStatus.OPTIMAL: s.OPTIMAL,
mip.OptimizationStatus.INFEASIBLE: s.INFEASIBLE,
mip.OptimizationStatus.INT_INFEASIBLE: s.INFEASIBLE,
mip.OptimizationStatus.NO_SOLUTION_FOUND: s.INFEASIBLE,
mip.OptimizationStatus.ERROR: s.SOLVER_ERROR,
mip.OptimizationStatus.UNBOUNDED: s.UNBOUNDED,
mip.OptimizationStatus.CUTOFF: s.INFEASIBLE,
mip.OptimizationStatus.FEASIBLE: s.OPTIMAL_INACCURATE,
mip.OptimizationStatus.LOADED: s.SOLVER_ERROR, # No match really
}
solution = {
"status": status_map[status],
"primal": [var.x for var in x],
"value": model.objective_value,
}
return solution
At this moment I have one more question, because the interface itself is working, it is possible to solve simple optimization problem with cvxpy syntax using mip CBC. However, when I run it on a real, more complex optimization problem it freezes and I am wondering, may it be because of the interface itself? (I will add that the same problem is solved in a couple of minutes using binaries of CBC and cvxpy itself, so it definitely should be possible for mip CBC to solve it as well.)
Could you please take a look on prepared interface and let me know if there are any additional steps that can be performed? I mean registering this interface somewhere in cvxpy or correcting anything for better performance? Any additional comment and suggestion will be appreciated. Thanks!
python-mip really is quite a bit slower at model construction than cylp, plus the interface I've written here hasn't had any effort put into efficiency. If you can post a code example I might be able to help out.
Honestly, it would be quite difficult and problematic for me to share this real optimization program due to data privacy issues. Is there any chance that you guys could give me some more advices how to speed up this interface without seeing the exact optimization problem?
@jurasofish we'd welcome a PR! This case is a little weird because we already have an interface to this solver. @rileyjmurray any ideas on what we should do here?
@Joanna-Wojdylo without a minimal example that demonstrates the problem there isn't much I can help you with. Without that the advice you get, if any, will probably be very generic.
I have some new observations regarding program freezing when using mip-python CBC and our custom mip_conif() interface, maybe you would be able to help here without a demonstrating example. So, when debugging the real oprimization program, I found out, that the problem lies in this method from mip_conif():
def add_leq_constraints(_model):
leq_start = dims[s.EQ_DIM]
leq_end = dims[s.EQ_DIM] + dims[s.LEQ_DIM]
coeffs = A[leq_start:leq_end, :]
vals = b[leq_start:leq_end]
for i in range(coeffs.shape[0]):
coeff_list = np.squeeze(np.array(coeffs[i].todense())).tolist()
expr = mip.LinExpr(variables=x, coeffs=coeff_list)
_model += expr <= vals[i]
add_leq_constraints(model)
I noticed, that when we're solving simple program it goes smoothly, but on the real optimization problem this range(coeffs.shape[0]) reaches almost 370 000, at this is not the most complicated task this optimization program will have to solve in the future. I observed, that in 1 minute for loop did about 1110 iterations, which means that it would take almost 6h for this loop to finalize. Unfortunately, this is definitely not acceptable from the business perspective and now I am searching for any possibility to optimize this part of code, maybe rewrite it without for loop if this is possible or anything else to make it faster.
@jurasofish, @SteveDiamond and @tkralphs I am very grateful for you help and it would be great if you have any further suggestions. Thanks!
PS. This issue is related with https://github.com/coin-or/Cbc/issues/371 and https://github.com/coin-or/python-mip/issues/182.
haha yeah that sounds about right. like I said, cylp is much faster than python-mip for model construction, and cylp has the massive advantage of being able to vectorise things, and I think it works natively with sparse arrays.
I might have a play with it and see if I can make it faster, but likely it'll never be as fast as cylp.
Good news - I made it 6,666x times faster. Now it adds ~60 thousand <= constraints per second rather than ~9 per second that it was doing before... I wasn't kidding when I said that this thing wasn't optimised. At least, that's based on a super sparse example
PR welcome if you want to do the same thing for the add_eq_constraints function
see code at https://github.com/jurasofish/mip_cvxpy
@SteveDiamond the last time I tried, I was unable to install cylp to test our cbc interface. It seems that to install cylp you need to install cbc from source. By contrast, the mip package comes with pre-built versions of cbc (for all major operating systems on Intel platforms). I think there is value in having an interface to cbc that doesn't require so much overhead in installing a solver.
My suggestion would be that we see if the current cbc interface even works with cylp (it seems the mip website also has instructions for installing cbc from source, https://docs.python-mip.com/en/latest/install.html). If our cylp interface doesn't work, then I'd be okay with replacing it by a cbc interface through mip (particularly the interface written by @jurasofish). Regardless of how we proceed, I think this is something that should go in cvxpy 1.2 (we created confusion with changes to solver interfaces with ECOS_BB in the 1.1.x series and I'd like to avoid similar issues).
A couple of comments.
- The method that is being used for packaging Cbc in python-mip can easily be used with CyLP. Basically, they are just packaging binaries from the COIN-OR bintray. There are some reasons (besides lack of bandwidth) why I haven't worked on this yet. For one thing, it can only be done easily with the Cbc in
masterfor some technical reasons having to do with the build system. python-mip is being pretty aggressive in packaging a version of Cbc which is a moving target (not a release version) and I would rather not do that. An option, though, would be to do a beta like I did initially with the Python 3 conversion of CyLP. If someone wants to look at how to do that, I would be happy to support it. - On the other hand, Cbc 2.10.5 can be installed easily on Linux and OS X by either conda (https://github.com/conda-forge/coin-or-cbc-feedstock), homebrew (https://github.com/coin-or-tools/homebrew-coinor), or coinbrew (https://github.com/coin-or/coinbrew). On Windows, there is a binary wheel for CyLP, so there is no issue. All in all, it seems that there is a pretty straightforward route to installation on all platforms without having to directly touch source.
If you haven't tried installing CyLP lately, give it another try. As far as I know, it installs pretty smoothly on all platforms (including the Cbc install).
I don't think replacing the cylp interface with python-mip is a feasible option - cylp has various advantages over python-mip, and there are likely many people who wouldn't tolerate the loss of performance and the new bugs that would be introduced by python-mip.
But I think it would be worthwhile to have a python-mip interface in cvxpy as a secondary easier to install interface to CBC.
Thank you @jurasofish so much! Now it works so much better, I did the same for == constraints as well.
@tkralphs Of course you're right with using CyLP, and locally I was using let's say 'original approach' so cvxpy and it's interface to CyLP+installed CBC, there are no problems in there. This whole issue came out because Azure specialists told me that this is not possible to somehow install CBC binaries on Azure Function, which is the target environment and there the whole story with pre-built CBC from MIP begun.
Anyway, I think that would be really great to have such additional CBC interface as a part of cvxpy library from the user's perspective and once again, huge thanks to you guys for your help!
@Joanna-Wojdylo could you not include CBC binaries in the deployment package? e.g. the bin folder like here or in a docker file like here. just asking out of curiosity - if it's anything like aws lambda it should be fairly straightforward. But still, I guess that would be more hassle that just pip install mip
Hmm, I contacted our Azure specialist and we'll try your idea (zip deployment), we had docker option already discussed so we're aware but that's another story :) I am just wondering, because usually when using CBC on windows we are connecting form python uisng environmen variable, right? Should I then change this part in the CyLP library (I guess it's somewhere over there, please correct me if I'm wrong) and set it to this exemplary bin folder with binaries and that would work?
As long as Cbc gets unpacked somewhere with the expected directory structure (subdirectories named bin, include, lib containing the expected files) and COIN_INSTALL_DIR points to where those directories live, CyLP should be happy. I don't see why you couldn't also just build Cbc in the target environment or just install it with conda. The CI for conda-forge is running on Azure (see https://github.com/conda-forge/coin-or-cbc-feedstock).
Re-joining this conversation a little late. First, thanks @tkralphs for your comment a few days ago. I didn't realize CBC had a conda-forge distribution. That's about as user-friendly as it gets for projects with C dependencies!
Although I should say that on my machine (Ubuntu 20.04, Conda 4.9.2) I was able to install CBC and other packages through conda, but pip install cylp still fails. I know pip and conda sometimes don't play nice so I'm not sure if that comes as a surprise to you. I suspect setting environment variables properly can fix this, but I haven't had time to investigate in detail. If you'd like more info on this install strategy (conda-forge for cbc then pip for cylp) let me know I can open a GitHub issue for this on the CyLP repo.
@rileyjmurray Thanks for the report on using the Cbc installed by conda-forge with CyLP. I wouldn't say it is exactly a surprise that it doesn't work yet, as I haven't actually have a chance to try it since finalizing the conda-forge installation process. I suspect it will be a pretty easy fix, but I'm not sure how to get CyLP to look in the right place to find a possible conda install. Why don't you open an issue (or just add a comment if there is an appropriate existing issue, which I think there might be), so we can have some discussion about it over there. Hopefully, some conda expert will be able to easily say how this should be done. I guess it's a pretty standard thing. Actually, the easiest would probably be just to have a conda-force recipe for CyLP as well. Maybe someone wants to take that one now that the heavy lifting is done.
I turned this into an installable package - on pypi with code here. @Joanna-Wojdylo you should use this as it fixes variables having a default lower bound of 0.
To include this in CVXPY would pretty much be a copy paste type operation, plus documentation.
Thanks for the pointer to the modified pypi package, @jurasofish. That's a great use of CVXPY's custom solver feature! We might reach out for you to add it to CVXPY as a native solver, but nothing's decided on that for now.
@tkralphs I've created a GitHub issue for CyLP installation and linked it to some possibly-related issues.
Since we haven't heard more on this issue, I think it's safe to close. Installing CBC is no longer difficult in my experience (we manage to run CBC tests even in GitHub Actions continuous integration). There is also @jurasofish's nice auxiliary/wrapper package for those that need it.
If anyone else has problems and benefits from @jurasofish's package, please let us know here. We could consider updating our documentation to make note of it. (I just hesitate to do that if we don't officially support it.)
If anyone else has problems and benefits from @jurasofish's package, please let us know here. We could consider updating our documentation to make note of it.
+1
Reopening because I think linking to https://github.com/jurasofish/mip_cvxpy in our custom solver documentation would be worthwhile.