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

[Rob Falck]

Pauli,

My understanding is that the simplex algorithm is used in "real-world"
applications.  The other most-common linear-programming method is probably
the interior point method.  There is a package lpsolve, which is quite good
and has a python wrapper, but it is under the LGPL license.  At some point
in the future it would be nice to mimic the linprog capability of matlab,
which gives the user the option of which linear programming method to use.

The LP simplex method is different than COBYLA in that it ONLY solves
linear problems, whereas COBYLA is essentially a sequential linear
programming method for solving nonlinear problems.  My understanding is
that linear programming techniques are generally faster at solving linear
problems than nlp methods.  For instance, Excel's solver routine has an
"assume linear" option that lets it branch into a linear programming mode
for faster results. (
http://www.solver.com/standard-excel-solver-limitations-nonlinear-optimization
)

Personally I think it's good to have a suite of several "simple" solvers.
 There are times when nelder-mead is the perferable solution method, and
there are other times when BFGS or COBYLA are the preferable method.
 Having several relatively simple solvers lets the user better understand
the limitations of each rather than trying to figure out the logic of one
massive solver routine.  In fact, one of the reasons I'm interested in
getting a linear programming routine into Scipy is that so a new sequential
linear programming method can be built upon it.  COBYLA is essentially
doing that now, but having more control over bounds and constraints would
be nice.

-Rob


On Wed, Oct 23, 2013 at 1:38 PM, Pauli Virtanen <pav at iki.fi> wrote:

> Hi,
>
> 23.10.2013 04:35, Rob Falck kirjoitti:
> [clip]
> > 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.
>
> One important question: is this algorithm regarded as useful and robust
> enough by people in the know?
>
> Are there existing more sophisticated LP solver codes with compatible
> licences?
>
> Does the LP simplex method win over nonlinear solvers such as COBYLA?
>
> scipy.optimize currently contains many "naive" solvers, which is not a
> completely happy situation. Of course, something is better than nothing,
> but if possible, I'd prefer one sophisticated code over many naive
> methods. I'm not an expert in LP, so I can't judge very well myself here.
>
> --
> Pauli Virtanen
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-dev
>



-- 
- Rob Falck
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20131024/23d446c7/attachment.html>