binary linear programming solver in Python

Question

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.

Answer 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

Answer 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

Answer 3

I develop a package called gekko (pip install gekko) that solves large-scale problems with linear, quadratic, nonlinear, and mixed integer programming (LP, QP, NLP, MILP, MINLP) and is released under the MIT License. A binary variable is declared as an integer variable type with lower bound 0 and upper bound 1 as b=m.Var(integer=True,lb=0,ub=1). Here is a more complete problem with the use of m.Array() to define multiple binary variables:

from gekko import GEKKO
m = GEKKO()
x,y = m.Array(m.Var,2,integer=True,lb=0,ub=1) 
m.Maximize(y)
m.Equations([-x+y<=1,
             3*x+2*y<=12,
             2*x+3*y<=12])
m.options.SOLVER = 1
m.solve()
print('Objective: ', -m.options.OBJFCNVAL)
print('x: ', x.value[0])
print('y: ', y.value[0])