<p dir="auto">numpy.distutils.system_info.NotFoundError: No BLAS/LAPACK libraries found. Note: Accelerate is no longer supported.<br>
To build Scipy from sources, BLAS &amp; LAPACK libraries need to be installed.</p>
<p dir="auto">How can i build source on mac m1?</p>
<p dir="auto">As Matt suggested (issue <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="564578793" data-permission-text="Title is private" data-url="https://github.com/scipy/scipy/issues/11515" data-hovercard-type="issue" data-hovercard-url="/scipy/scipy/issues/11515/hovercard" href="https://github.com/scipy/scipy/issues/11515">#11515</a>) I've been taking a look at the presolve routine and its reference, the Andersen &amp; Andersen paper.</p>
<p dir="auto">A&amp;A describes a set of options for trivial simplifications of the problem (some not too trivial, though), numbered (i) - (xvii). The current <code class="notranslate">_presolve</code> function handles just a couple of them:</p>
<ul dir="auto">
<li>zero row in equality constraints (i)</li>
<li>zero row in inequality constraints (i)</li>
<li>zero column in both constraints (ii)</li>
<li>row singleton in equality constraints (v)</li>
<li>row singleton in inequality constraints (v)</li>
<li>identical bounds (iv)</li>
</ul>
<p dir="auto">A&amp;A also suggest some of these options should be repeated. That currently doesn't happen either. The variables <code class="notranslate">bounds</code> and <code class="notranslate">undo</code> contain the information for reversing the simplification in <code class="notranslate">_postsolve</code>. <code class="notranslate">_postsolve</code> als reverses the problem standardization of <code class="notranslate">_get_Abc</code> using <code class="notranslate">bounds</code>.</p>
<p dir="auto">I have a couple of considerations and questions with respect to updating <code class="notranslate">_presolve</code>:</p>
<ol dir="auto">
<li>It would be good to redesign the presolve routine in such a way that we can add options one at a time, in a modular way. Right?</li>
<li>A&amp;A warn that some options may be computationally heavy, so it may be good to modify the solver option 'presolve'. Instead of just <code class="notranslate">True</code> or <code class="notranslate">False</code>, we may introduce a numeric level which in- or excludes specific presolve options. Can we do that?</li>
<li>Do we know if we can 'match' presolve efforts to an actual solver? What presolve activity is always advantageous? What presolve activities make sense for specific solvers only?</li>
<li>I think we should not use <code class="notranslate">bounds</code> as carrier of information for reversing <code class="notranslate">_presolve</code> (in <code class="notranslate">_postsolve</code>). For some A&amp;A options the <code class="notranslate">bounds</code>/<code class="notranslate">undo</code> implementation will not work anyway. But it is also not elegant to use a problem parameter for this.</li>
<li>Where in the process should presolve take place? In the current implementation, it is the first step, but the A&amp;A-options relate to the standard form. That means that we have to 'translate' their options, e.g. to include <code class="notranslate">A_ub</code> and <code class="notranslate">b_ub</code>. Would it be better to presolve after the standardization?</li>
<li>Some A&amp;A options refer to the dual problem - that is not available at the presolve level. (Is it even used? I did not check the specific <code class="notranslate">linprog</code> solvers). What to do with these A&amp;A-options?</li>
<li>The final A&amp;A options (xiv - xvii) address rank deficiency, but in a rather ad-hoc way it seems to me. Linprog currently implements a more thorough procedure to remove redundant equations, but I have also read the comment in <code class="notranslate">_remove_redundancy</code>. What is the proper location to address/check linear dependencies? Immediately before the solver is called? Or can it be done before the standardization in <code class="notranslate">_get_Abc</code>? Is there proof that the standardization never introduces linear dependencies?</li>
<li>Analyzing matrix rank (or doing a SVD) is necessary, but it also takes time. Are the solver algorithms able to detect (and perhaps repair) linear dependencies in the course of their process more 'cheaply'? I see quite a bit of literature on this subject, which suggests it is a topic worth exploring, but it is outside of my area of expertise.</li>
<li>Am I missing something?</li>
</ol>
<p dir="auto">Regarding <code class="notranslate">bounds</code>: I'm confused about the use of <code class="notranslate">None</code> and <code class="notranslate">np.inf</code> at various locations in the code. Do they have different meanings? Perhaps related to the <code class="notranslate">_postsolve</code> process? See 4 above: I would prefer to standardize the use of <code class="notranslate">(-)np.inf</code> for an absent bound.</p>
<p dir="auto">What do you think of this presolve framework?:</p>
<p dir="auto">Code each A&amp;A option as a separate function <code class="notranslate">PR</code>, with:</p>
<ul dir="auto">
<li>1 input: current values of the problem parameters <code class="notranslate">pp</code> = <code class="notranslate">(c, A_eq, b_eq, A_ub, b_ub, u, l, x0)</code></li>
<li>3 outputs: modified values of the problem parameters <code class="notranslate">pp</code> = <code class="notranslate">(c, A_eq, b_eq, A_ub, b_ub, u, l, x0)</code>, a function <code class="notranslate">REV</code> to undo this specific modification and a <code class="notranslate">status</code> flag (0 : Modification made, 1 : No modification made, 2 : Problem appears to be infeasible, 3 : Problem appears to be unbounded)</li>
</ul>
<p dir="auto">The function <code class="notranslate">REV</code> is pre-parametrized to carry out the restauration. It has:</p>
<ul dir="auto">
<li>1 input: current values of the criterion vector, solution, and initial guess <code class="notranslate">cp</code> = <code class="notranslate">(c, x, x0)</code></li>
<li>1 output: restored values of the criterion vector, solution, and initial guess <code class="notranslate">cp</code> = <code class="notranslate">(c, x, x0)</code></li>
</ul>
<p dir="auto">The <code class="notranslate">REV</code>-functions can be put on a stack for reversing the modifications, as A&amp;A suggest.</p>
<p dir="auto">Presolve would now work as follows:</p>
<ol dir="auto">
<li>input: current values of the problem parameters <code class="notranslate">pp = (c, A_e, b_e, A_f, b_f, u, l, x0)</code></li>
<li></li>
</ol>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="REVstack = []"><pre class="notranslate"><code class="notranslate">REVstack = []
</code></pre></div>
<ol start="3" dir="auto">
<li>Perform initial presolve routines</li>
</ol>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="(pp, REV, status) = PR_1(pp)
if status == 0: REVstack.append(REV)
if status == 2 or 3: raise error infeasible or unbound"><pre class="notranslate"><code class="notranslate">(pp, REV, status) = PR_1(pp)
if status == 0: REVstack.append(REV)
if status == 2 or 3: raise error infeasible or unbound
</code></pre></div>
<p dir="auto">... and other initial presolve routines in the same way</p>
<ol start="4" dir="auto">
<li>Perform the looped presolve routines</li>
</ol>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="while modifications:
    modifications = False
    (pp, REV, status) = PR_2(pp)
    if status == 0: REVstack.append(REV), modifiations = True
    if status == 2 or 3: raise error infeasible or unbound"><pre lang="modifications" class="notranslate"><code class="notranslate">while modifications:
    modifications = False
    (pp, REV, status) = PR_2(pp)
    if status == 0: REVstack.append(REV), modifiations = True
    if status == 2 or 3: raise error infeasible or unbound
</code></pre></div>
<p dir="auto">... and other presolve routine which must be repeated</p>
<ol start="5" dir="auto">
<li>Perform final presolve routines</li>
</ol>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="(pp, REV, status) = PR_3(pp)
if status == 0: REVstack.append(REV)
if status == 2 or 3: raise error infeasible or unbound"><pre class="notranslate"><code class="notranslate">(pp, REV, status) = PR_3(pp)
if status == 0: REVstack.append(REV)
if status == 2 or 3: raise error infeasible or unbound
</code></pre></div>
<p dir="auto">... and other final presolve routines in the same way</p>
<ol start="6" dir="auto">
<li>output: modified values of the problem parameters <code class="notranslate">pp = (c, A_e, b_e, A_f, b_f, u, l, x0)</code></li>
<li>output: <code class="notranslate">REVstack</code> containing the functions to reverse the modifications</li>
</ol>
<p dir="auto">Postsolve would work like this:</p>
<ol dir="auto">
<li>input: criterion vector, solution and initial values of the modified problem <code class="notranslate">cp = (c, x, x0)</code></li>
<li>apply functions in <code class="notranslate">REVstack</code>, last one first</li>
</ol>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="for i in range(len(REVstack),-1,-1):
    cp = REVstack[i](cp)"><pre class="notranslate"><code class="notranslate">for i in range(len(REVstack),-1,-1):
    cp = REVstack[i](cp)
</code></pre></div>
<ol start="3" dir="auto">
<li>output: criterion vector, solution and initial guess <code class="notranslate">cp = (c, x, x0)</code> in their original context</li>
</ol>