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.

Paraboloid

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

Fecit

adding the constraint 0 <= x <= 1 does not make a binary program. it is merely the LP relaxation of the binary program, and can be used as part of a binary program solution method. – Antifouling

I am saying add the constrain 0 <= x <= 1 to the Integer Program (that you can solve with CVXOPT as pointed above), to transform the Integer Program, into a binary program. – Fecit

Well.... yes and no. A linear program with binary/integer variables only is called an ILP (integer linear program). A linear program with both binary/integer variables AND continuous variables is called an MILP (Mixed Integer Linear Program). The terms "integer" and "binary" are used interchangeably in this context, because any integer variable can be represented using multiple binary variables (i.e. SOS type 1). But you are correct in saying one should impose 0 <= x <= 1 if x is declared as an general integer variable. However, in most cases, x can be directly declared as a binary variable. – Gens

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

Gens

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])

Cosma