<div dir="ltr">Thanks for pointing out the more restrictive license of cvxopt, <span style="font-size:12.8px">Gaël. Along those lines:</span><div><span style="font-size:12.8px"><a href="http://lpsolve.sourceforge.net/5.5/LGPL.htm" target="_blank">lp_solve</a> is Lesser GPL.<br></span><div><span style="font-size:12.8px"><a href="https://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit" target="_blank">GLPK</a> is GPLv3 (as one would expect)</span></div></div><div><span style="font-size:12.8px"><a href="https://www.coin-or.org/Clp/faq.html" target="_blank">COIN-OR</a> is CPL.</span></div><div><span style="font-size:12.8px"><a href="http://www.math.uwaterloo.ca/~bico/qsopt/ex/" target="_blank">QSOPT</a> is GPLv2.1+ or for research use one (user's choice).</span></div><div><span style="font-size:12.8px">The rest of the codes are commercial, I believe.</span></div><div><br></div><div>As mentioned in my last email, I wanted to compare the performance of <font face="monospace, monospace">linprog</font> and the interior point code, which I'll refer to as <font face="monospace, monospace">linprog_ip</font>. The benchmark problems used were scalable and typically randomly-generated. They were selected purely for their availability/ease of implementation (except for the Klee-Minty Hypercube, which is the bane of simplex solvers. It is possible that many of these tests are particularly challenging to simplex solvers, but the only one I know to punish simplex is the Klee-Minty hypercube.) I'd love to test with the more practical <a href="http://www.cuter.rl.ac.uk/Problems/netlib.shtml" target="_blank">NETLIB</a> benchmarks but these are in MPS format and I haven't looked into how to convert yet. </div><div><br></div><div>The results are available at: </div><div><a href="https://www.dropbox.com/s/8vfye61kvn9h3zg/linprog_benchmarks.pdf?dl=0" target="_blank">https://www.dropbox.com/s/<wbr>8vfye61kvn9h3zg/linprog_<wbr>benchmarks.pdf?dl=0</a><br></div><div>and details about the tests are in the postscript.</div><div><br></div><div>In summary, <font face="monospace, monospace">linprog_ip </font>is significantly faster for all but the smallest problems (those that are solved in hundredths of a second), and is more reliable at finding solutions when they exist.. As problem size increases, the performance gap tends to increase. For sparse problems, the ability of <font face="monospace, monospace">linprog_ip</font> to leverage <font face="monospace, monospace">scipy.sparse</font> linear algebra yields great improvement. For certain types of problems, <font face="monospace, monospace">linprog</font> has difficulty finding a starting point, and takes longer to fail than <font face="monospace, monospace">linprog_ip</font> does to return the optimal solution.</div><div><br></div><div>Besides the test results, please also see all open <font face="monospace, monospace">linprog</font> bug reports: <a href="https://github.com/scipy/scipy/issues/5400" target="_blank">5400</a>, <a href="https://github.com/scipy/scipy/issues/6139" target="_blank">6139</a>, <a href="https://github.com/scipy/scipy/issues/6690" target="_blank">6690</a>, <a href="https://github.com/scipy/scipy/issues/7044" target="_blank">704<wbr>4</a>. <font face="monospace, monospace">linprog_ip</font> suffers from none of these. Of course, it also passes all the <font face="monospace, monospace">linprog </font>unit tests and many more I have written.<br></div><div><br></div><div>I attribute the success of <span style="font-family:monospace,monospace">linprog_ip </span>to the algorithm it implements and the suitability of the algorithm to NumPy/SciPy. For instance, for <font face="monospace, monospace">lpgen_2D</font> with 60 constraints and 60 variables, <font face="monospace, monospace">linprog </font>reports about 140 iterations whereas <font face="monospace, monospace">linprog_ip</font> finishes in 9. Each of <font face="monospace, monospace">linprog</font>'s iterations has loops that do one elementary row operations per loop iteration, whereas at the heart of a <font face="monospace, monospace">linprog_ip</font> iteration is the Cholesky factorization of a matrix and back/forward substitution for four different right hand sides (all LAPACK via <font face="monospace, monospace">scipy.linalg.solve</font>). Consequently, <font face="monospace, monospace">linprog_ip</font> spends larger chunks of time in compiled code with far fewer loops/function calls in Python.</div><div><br></div><div>Please let me know if you'd like to see the interior point code included in SciPy, and I'll integrate with linprog and figure out the submission process. (If you are familiar with compiling from source on Windows, please shoot me an email. After pushing through a few roadblocks, I'm stuck with a very vague error message.)</div><div><br></div><div>Matt</div><div><br></div><div><br></div><div>-----</div><div> </div><div><br></div><div>All tests were performed on a Dell XPS 13, IntelCore i5-4200 CPU at 1.6-2.3 GHz, 8GB RAM, and Windows 10 64-bit. Tests were timed using <font face="monospace, monospace">line_profiler</font> (<font face="monospace, monospace">kernprof</font>). For randomized problems, each of N problems of arbitrary size (m constraints, n variables) were generated and solved by <font face="monospace, monospace">linprog</font> and <font face="monospace, monospace">linprog_ip</font> in either (random) order. For non-random problems, the same problem of a given dimension was solved by <font face="monospace, monospace">linprog</font> and <font face="monospace, monospace">linprog_ip</font> in either (random) order N times. Unless otherwise noted, the consistency of the solutions returned by <font face="monospace, monospace">linprog</font> and <font face="monospace, monospace">linprog_ip</font> was checked by comparing the objective function value using <font face="monospace, monospace">numpy.allclose</font> with default tolerances. Times reported are the average per hit (call to <font face="monospace, monospace">linprog</font> or <font face="monospace, monospace">linprog_ip</font> ) in units of 4.46E-07 s and also as normalized by the faster of the two times (1 is better; the other number indicates how many times longer it took). </div><div><br></div><div>1. <a href="https://gist.github.com/denis-bz/8647461" target="_blank">lpgen_2D</a>, the randomized test case currently part of the <span style="font-family:monospace,monospace">linprog</span> unit tests. </div><div><i>Note that in these tests there are actually m*n variables and m+n constraints. For example, in the last test there are 800 constraints and 160000 variables.</i></div><div>(Unfortunately, I realized after testing that I left <font face="monospace, monospace">np.random.seed(0)</font> in the code, and thus the same problem was solved N times per test. However, unreported testing after fixing this yielded similar results.)</div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">2. <span id="m_-7635458066601837616gmail-m_-7160675335607538107m_-7452773260004098788gmail-goog_700313160"></span><a href="http://onlinelibrary.wiley.com/doi/10.1111/1475-3995.00392/abstract" target="_blank">zionts1</a><span id="m_-7635458066601837616gmail-m_-7160675335607538107m_-7452773260004098788gmail-goog_700313161"></span>, a randomized test with inequality constraints originally used by Zionts to compare the performance of his criss-cross algorithm to the simplex. Occasionally, <font face="monospace, monospace">linprog </font>fails to find a feasible initial point, even where a solution exist, as reported in <a href="https://github.com/scipy/scipy/issues/6139" target="_blank">Issue 6139</a>.</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">3. </span><span id="m_-7635458066601837616gmail-m_-7160675335607538107m_-7452773260004098788gmail-goog_700313160" style="font-size:12.8px"></span><a href="http://onlinelibrary.wiley.com/doi/10.1111/1475-3995.00392/abstract" target="_blank"><span style="font-size:12.8px">zionts</span>2</a><span style="font-size:12.8px">, a randomized test with both equality and inequality constraints originally used by Zionts to compare the performance of his criss-cross algorithm to the simplex. </span><span style="font-size:12.8px">For problems of moderate size, </span><font face="monospace, monospace" style="font-size:12.8px">linprog </font><span style="font-size:12.8px">fails to find a feasible initial point, even where a solution exist, as reported in </span><a href="https://github.com/scipy/scipy/issues/6139" style="font-size:12.8px" target="_blank">Issue 6139</a><span style="font-size:12.8px">.</span><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">4. </span><span id="m_-7635458066601837616gmail-m_-7160675335607538107m_-7452773260004098788gmail-goog_700313160" style="font-size:12.8px"></span><a href="http://onlinelibrary.wiley.com/doi/10.1111/1475-3995.00392/abstract" target="_blank"><span style="font-size:12.8px">b</span><span id="m_-7635458066601837616gmail-m_-7160675335607538107m_-7452773260004098788gmail-goog_700313161" style="font-size:12.8px"></span>onates</a><span style="font-size:12.8px">, a sparse, randomized test used in "Performance evaluation of a family of criss–cross algorithms for linear programming". Here, percentage of nonzeros (density) is reported as p (the sparsity is 1-p). </span><span style="font-size:12.8px">The solutions are typically infeasible or unbounded; the time reported is that required for the solver to reach this conclusion.</span><span style="font-size:12.8px"> </span><span style="font-family:monospace,monospace">linprog</span><span style="font-size:12.8px"> always terminates when it fails to find a feasible initial point. <font face="monospace, monospace">linprog_ip</font> reports whether the problem is infeasible or unbounded.</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">5. magic_square, an LP-relaxed version of a binary integer linear program designed to find a <a href="https://en.wikipedia.org/wiki/Magic_square" target="_blank">magic square</a> of size D. The cost vector is random; any feasible solution represents a magic square. The problem includes equality constraints and simple bounds (0, 1). As formulated, the problem's equality constraint matrix is rank deficient (in a non-obvious way), causing </span><span style="font-family:monospace,monospace">linprog</span><span style="font-size:12.8px"> to report success despite the fact that the returned solution is infeasible and the objective value is inconsistent with the solution, as reported in <a href="https://github.com/scipy/scipy/issues/6690" target="_blank">Issue 6690</a>. To enable performance comparison, I've lent <font face="monospace, monospace">linprog</font> the use of <font face="monospace, monospace">linprog_ip</font>'s presolve routine, which removes redundant rows such that <font face="monospace, monospace">linprog</font> is able to solve the problem correctly.</span></div><div><br></div><div><span style="font-size:12.8px">6. <a href="https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_cube" target="_blank">klee_minty</a>, a problem that elicits the worst-case performance of Dantzig's original simplex method. Here, Bland's rule is used by <font face="monospace, monospace">linprog</font>. (Its runtime is far worse with the default pivoting rule.)</span></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Feb 21, 2017 at 11:07 PM, Gael Varoquaux <span dir="ltr"><<a href="mailto:gael.varoquaux@normalesup.org" target="_blank">gael.varoquaux@normalesup.org</a><wbr>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span>> On Tue, Feb 14, 2017 at 1:15 AM, Ralf Gommers <<a href="mailto:ralf.gommers@gmail.com" target="_blank">ralf.gommers@gmail.com</a>> wrote:<br>
</span><span>>     There's an argument to be made for having a consistent set of well-known<br>
>     algorithms in SciPy, but knowing the boundary of the scope here is helpful<br>
>     especially if there are more powerful solutions like cvxopt that could<br>
>     become easy to install soon.<br>
<br>
</span>cvxopt is GPLv3 and scipy is BSD, so cvxopt cannot be a supplement of<br>
scipy for everybody.<br>
<br>
Gaël<br>
<div class="m_-7635458066601837616HOEnZb"><div class="m_-7635458066601837616h5">______________________________<wbr>_________________<br>
SciPy-Dev mailing list<br>
<a href="mailto:SciPy-Dev@scipy.org" target="_blank">SciPy-Dev@scipy.org</a><br>
<a href="https://mail.scipy.org/mailman/listinfo/scipy-dev" rel="noreferrer" target="_blank">https://mail.scipy.org/mailman<wbr>/listinfo/scipy-dev</a><br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="m_-7635458066601837616gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">Matt Haberland<div>Assistant Adjunct Professor in the Program in Computing</div><div>Department of Mathematics</div><div>7620E Math Sciences Building, UCLA</div></div></div>
</div></div>