binary linear programming solver in Python

问题:

I have a Python script in which I need to solve a linear programming problem. The catch is that the solution must be binary. In other words, I need an equivalent of MATLAB's bintprog function. NumPy and SciPy do not seem to have such a procedure. Does anyone have suggestions on how I could do one of these three things:

• Find a Python library which includes such a function.

• Constrain the problem such that it can be solved by a more general linear programming solver.

• Interface Python with MATLAB so as to make direct use of bintprog.

回答1:

Just to be rigorous, if the problem is a binary programming problem, then it is not a linear program.

You can try CVXOPT. It has a integer programming function (see this). To make your problem a binary program, you need to add the constrain 0 <= x <= 1.

Edit: You can actually declare your variable as binary, so you don't need to add the constrain 0 <= x <= 1.

cvxopt.glpk.ilp = ilp(...)
Solves a mixed integer linear program using GLPK.

(status, x) = ilp(c, G, h, A, b, I, B)

PURPOSE
Solves the mixed integer linear programming problem

    minimize    c'*x
    subject to  G*x <= h
                A*x = b
                x[I] are all integer
                x[B] are all binary

回答2:

This is a half-answer, but you can use Python to interface with GLPK (through python-glpk). GLPK supports integer linear programs. (binary programs are just a subset of integer programs).

http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit

Or you could simply write your problem in Python and generate an MPS file (which most standard LP/MILP (CPLEX, Gurobi, GLPK) solvers will accept). This may be a good route to take, because as far as I am aware, there aren't any high quality MILP solvers that are native to Python (and there may never be). This will also allow you to try out different solvers.

http://code.google.com/p/pulp-or/

As for interfacing Python with MATLAB, I would just roll my own solution. You could generate a .m file and then run it from the command line

% matlab -nojava myopt.m

Notes:

1. If you're an academic user, you can get a free license to Gurobi, a high performance LP/MILP solver. It has a Python interface. http://www.gurobi.com/
2. OpenOpt is a Python optimization suite that interfaces with different solvers. http://en.wikipedia.org/wiki/OpenOpt