[SciPy-User] Linear Programming via Simplex Algorithm

[Rob Falck]

Hello,

I've spent some time recently polishing a simplex-based linear programming
function.  I've seen traffic from time to time about including such
functionality in scipy.optimize but it always seems to have been closed
without inclusion.

My intent was to develop a linear-programming routine that, given a
non-standard linear programming problem, generates a canonical tableau and
solves it using the simplex algorithm. By nonstandard I mean that variables
may have negative values, and three types of constraints are supported
(lower-bound, upper-bound, and equality).

I've named a top-level routine "linprog".  I suspect in the future that
scipy may include other algorithms besides the simplex to solve linear
programming problems, in which case linprog would serve as the main
function (similarly to the way minimize serves as the interfact to all nlp
routines).

For example, consider a relatively simple problem:

Maximize:  f = 3*x[0] + 2*x[1]
Subject to:  2*x[0] + 1*x[1] <= 10
                  1*x[0] + 1*x[1] <= 8
                  1*x[0] + 0*x[1] <= 4

where: 0 <= x[0] <= inf
          0 <= x[1] <= inf

The inputs are such that the objective is specified by array c where f =
dot(c,x).
We have three upper-bound constraints, which we define using dot(A_ub,x) <=
b_ub

>>>c = [3,2]
>>>b_ub = [10,8,4]
>>>A_ub = [[2,1],
>>>            [1,1],
>>>            [1,0]]
>>>res=linprog(c=c,A_ub=A_ub,b_ub=b_ub,objtype='max',disp=True)
Optimization terminated successfully.
         Current function value: 18.000000
         Iterations: 3

I've written a suite of unit tests and have documented all functions.  It's
somewhat non-standard but I've also included two callback functions.
 linprog_verbose_callback prints the simplex tableau, pivot element, and
basic variables at each iteration of the simplex method.
linprog_terse_callback simply prints the value of the solution vector x at
each iteration.

The code is currently in the linprog branch at
https://github.com/robfalck/scipy/tree/linprog/scipy
(relevant files are scipy/optimize/linprog.py, scipy/optimize/__init__.py,
and scipy/optimize/tests/test_linprog.py)

I welcome constructive criticism of the algorithm.  It's been designed to
detect degenerate cases due to unbounded problems, and it has a relatively
basic way to avoid cycling in the simplex solution.

If there's interest in including this I'd be happy to proceed with
submitting a PR.  I still have a bit of cleanup to perform but it's
relatively close to being ready (pep8 compliance, etc)

Thanks,

Rob Falck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20131020/67e5c9ca/attachment.html>