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.

1
15
7/24/2010 5:22:02 PM

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
8
6/15/2015 11:23:42 AM

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon