MAINT: optimize: Additional linprog cleanup

[mdhaber]

Separate from the enhancements in #9269, I wanted to keep a list of deferred maintenance.

• copy linprog documentation descriptions into method-specific documentation (e.g. https://docs.scipy.org/doc/scipy/reference/optimize.linprog-interior-point.html) (ENH: optimize: add HiGHS methods to linprog - continued #12043)
• address two little comments in ENH: optimize: interpolative decomposition redundancy removal for linprog #11249 (see comment here)
• add highs method-specific option tests (see comment here)
• rename _T_o in linprog and all linprog methods, perhaps to _postsolve_args if that makes sense. Document it everywhere.
• Document **unknown_options (DOC: Add missing docs for linprog unknown_options #10099)
• clean _clean_inputs. Several have commented that it is too messy. (Clean _clean_inputs in optimize.linprog #10083)
• figure out what changes caused interior-point to report failure despite success on some Netlib benchmarks (BUG: optimize: tweaked linprog status 4 error message #10025)
• "We're often passing c, A_ub, b_ub, A_eq, b_eq, bounds, x0 between functions. Maybe this should be refactored into a container e.g. a namedtuple or dictionary?" - @Kai-Striega. Update: Done in MAINT: optimize: refactor common linprog arguments into namedtuple #10602.
• sym_pos=True to assume_a='pos'
• Simplify control over method='interior-point' solver: one option solver instead of separate boolean options cholesky, sym_pos, and lstsqr
• change bounds to NumPy arrays internally. Ensure that _check_result checks solution against original bounds.
• allow bounds to be specified as NumPy arrays
• allow bounds to be specified as Bounds objects (A 6 x 6 linprog testcase: 3 methods x sparse / dense give different results #10288)
• automatically remove constraints with infinite upper bound (A 6 x 6 linprog testcase: 3 methods x sparse / dense give different results #10288)
• loosen tolerance for linprog(method='simplex') as mentioned in ENH: linprog in SciPy 1.2+ discussion #9269
• add stacklevel argument to warnings
• _check_result should have relative tolerance
• clean up interior point display issues - see TST: optimize: fixed linprog "disp": True bug #10498. Why exactly is alpha sometimes an int? An array with one element? Fix at the source. Ensure that arguments to _get_step are always floats (not single-element arrays), and change 1 in _get_step to 1.0.
• expose control of conceptually distinct tolerances to user. (For instance, tolerance for pivot selection should be distinct from the tolerance for constraint satisfaction checks.)
• Revisit excepts with generic Exceptions (ENH: optimize: dense redundancy removal routine optimizations #11245)

[Kai-Striega]

I would also like to add changing the type of bounds to NumPy arrays, at a minimum for internal use in the solvers.

[mdhaber]

Re: "figure out what changes caused interior-point to report failure despite success on some Netlib benchmarks"
I've tracked this down to commit 7d1619be79c1fb75072e34e007d01d2d4190bb94 in BUG: optimize: partial fix to linprog fails to detect infeasibility #8664.
Makes sense. Probably just a tolerance issue in that check.

[mdhaber]

@Kai-Striega In #9636 I did a bunch of benchmarking and noticed that there were a lot of problems for which 'interior-point was reporting failure despite having an objective function value very close to the correct value. This wasn't something I had observed in the original benchmarking (#7123), so I wanted to find out when this changed. We discussed this at the end of #9636 and ruled out the linprog refactoring. Looks instead like it's in PR #8676 (this commit). This makes total sense, because that commit added a direct constraint check of the solution. Looks like it's just the inherent limited accuracy of interior-point. Nothing has changed about the solution it returns (I checked), but this constraint check reveals that the constraints are not satisfied to the target tolerance (which was somewhat arbitrary; currently it uses sqrt(tol)).

Proposed solution: The current status message in this case is:
The solution does not satisfy the constraints, yet no errors were raised and there is no certificate of infeasibility or unboundedness. This is known to occur if the presolve option is False and the problem is infeasible. If you encounter this under different circumstances, please submit a bug report. Otherwise, please enable presolve.
Perhaps I'll change it to also explain that interior-point is not perfectly accurate and that the user should check the constraint residuals. If they're acceptable, great, if not, they can try using revised simplex.

Does that sound good? Or can you think of a more appropriate tolerance to use in the constraint check?

[Kai-Striega]

@mdhaber sorry I missed this. I think updating the error message is a good fix. The tolerance used in the checks is arbitrary and the user may always specify a higher tolerance.

It may be worth noting somewhere how the tolerance from the tol parameter relates to the final tolerance used in the checks, although that should not be in the error message.