MAINT: Refactor _linprog.py and _linprog_ip.py to remove duplicate behaviour.

[Kai-Striega]

Problem

_linprog.py solves linear programming problems, originally via the simplex method. An implementation of the interior-point method was later added via _linprog_ip.py using the original _linprog.py as the top-level interface. The simplex and interior-point implementations duplicate similar behaviour and arguments especially to:

• Clean user input.
• Convert problem to standard equality form.
• Call-back functions (not (yet) implemented in IP)

Further _linprog_ip.py implements the _presolve(...) and _postprocess(...), which may also improve the simplex method.

Proposed changes

I'm proposing to refactor _linprog.py and _linprog_ip.py into three new files _linprog.py, _linprog_ip.py and _linprog_simplex.py

_linprog.py to be the top level linear programming interface and handle behaviour common to all linear programming methods:

• Validating and cleaning input.
• Conversion to standard form.
• Call-back functions.
• Pre-solving and post-processing.

_linprog_ip.py and _linprog_simplex.py to implement the specific methods.

Benefits

• Remove code implementing similar behaviour.
• Avoid calling more complex solvers if problem is trivially solved.
• Supply problem in standard equality form to all solvers.
• Reduce the complexity of _linprog_simplex(...) by reusing _clean_inputs(...) and _get_Abc(...) from the interior point method.
• Improve simplex method implementation by pre-solving and post-processing.

Would this be worth refactoring or are there any other suggestions? @rgommers @mdhaber

[mdhaber]

The ideas are great IMO and such refactoring should definitely be done before any new solver methods are added.

However, I think that fixing #5400, #7237, #8174 are higher priority than refactoring. The bugs have really limited the simplex solver's utility, so I think they need to be addressed before refactoring and extensions like the presolver will be beneficial.

After those are out of the way though, I do think we should come back to this. It sounds like @sschnug plans contribute a wrapper for HiGHS (see #8575), so there should be some coordination with that effort. Some questions about that before refactoring the existing methods independently:

• Is it convenient and desirable to use the preprocessing/presolving routines from HiGHS rather than the ones that were written for linprog-ip?
• Would the HiGHS solver support a callback function?
• Would we want to maintain the old simplex solver after a wrapper for a revised simplex solver is added?

Even if SciPy will get a fast, revised-simplex solver someday, it would be nice to have a more reliable simplex solver in the meantime, and there may be some benefit to having an all-python simplex solver after that. Would you be interested in taking a closer look at those, @Kai-Striega?

[Kai-Striega]

I agree that fixing the bugs should take priority. From what I can see many of the errors are cause by numerical or conditioning issues within the simplex method. Some possible causes to look at:

• The above errors in particular appear when there are many (very nearly) linearly independent rows, presolving to reduce the number of linearly independent rows will help with this.
• Possible improvements to the floating point arithmetic in performing the pivots.
• Add a check if the problem is poorly conditioned, this has already been discussed in NumPy issue #3775.

linprog's conversion to the standard form makes the code harder to read. Moving these into sperate functions will help with that. But then using linprog_ip's helper function would do the same job, even if they are only imported for now. As an extra If there is an improvement it will be applied to both

[mdhaber]

If you see some code restructuring as the best way to resolve bugs or if you think it will help you find the bugs, go for it. Just thought that restructuring with the primary purpose being cleaner code or improving simplex performance (without fixing bugs) was premature.

[Kai-Striega]

Closed with PR #9145

[mdhaber]

Agreed that this is closed.