# [SciPy-User] Linear Programming via Simplex Algorithm Classic List Threaded 4 messages Open this post in threaded view
|

## [SciPy-User] Linear Programming via Simplex Algorithm

 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 + 2*xSubject to:  2*x + 1*x <= 10                  1*x + 1*x <= 8                   1*x + 0*x <= 4where: 0 <= x <= inf          0 <= x <= infThe 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: 3I'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 _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user
Open this post in threaded view
|

## Re: Linear Programming via Simplex Algorithm

 On Mon, Oct 21, 2013 at 3:59 AM, Rob Falck wrote: 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. Hi Rob, I assume you have seen https://github.com/scipy/scipy/pull/218 then? Looks like it's functionality that we'd like to see in scipy.optimize but needs some more effort than anyone has been willing to spend so far.   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). A generic `linprog` interface sounds like a good idea. It looks like the API and the current implementation are fairly specific to your lpsimplex algorithm however. Compare how little minimize() does to the 400 LoC in linprog(). If you want to make linprog() generic maybe it would help if you would consider how you could integrate the algorithm of https://github.com/scipy/scipy/pull/218 into it without changing the API besides adding a "method" keyword. For example, consider a relatively simple problem:Maximize:  f = 3*x + 2*xSubject to:  2*x + 1*x <= 10                  1*x + 1*x <= 8                   1*x + 0*x <= 4where: 0 <= x <= inf          0 <= x <= infThe 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: 3I'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. Do the callbacks need to be separate public functions? My impression is no. And what about lpsimplex()? If linprog() is the generic interface maybe lpsimplex can be private?  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) This looks pretty good from a quick browse (disclaimer: I haven't tried to understand your algorithm in detail).  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. Have you benchmarked your algorithm against other implementations? And/or checked the efficiency (typical should be 2N to 3N iterations, with N the size of the constraint matrix)?   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) Sounds good to me!In terms of completing the cleanup, I think fixing line length to 80 chars and breaking up linprog() into smaller logical units would be good to before submitting imho. Also, linprog.py should be renamed to _linprog.py. Cheers,Ralf _______________________________________________ SciPy-User mailing list [hidden email] http://mail.scipy.org/mailman/listinfo/scipy-user