[SciPy-Dev] Marginals/sensitivity analysis for linprog HiGHS

[Nicholas McKibben]

Hi all,

gh-13893 <https://github.com/scipy/scipy/pull/13893>is under review and
provides sensitivity analysis for the SciPy HiGHS LP solvers.

For each of the three constraint types -- equality constraints, inequality
constraints, and lower/upper bounds -- we want to convey three pieces of
information: marginals (also commonly referred to as "Lagrange
multipliers", "dual values", or "shadow prices"), ranging information (to
be added in a future PR), as well as some measure of the distance between
the solution and the constraints.

Many LP solvers return this information but unfortunately there is little
agreement in the field on how it should be labeled or presented.  This
comment <https://github.com/mckib2/scipy/pull/10#issuecomment-782120346>
gives a brief overview of the different conventions other popular LP
solvers follow.  For SciPy, we have settled on organizing the
OptimizeResult object in the following way according to the right-hand
diagram in this file
<https://www.dropbox.com/s/8j27rgdc2hp79o8/OptimizeResult.pptx?dl=0>.
Specifically:
- "slack" and "con" fields are doc-deprecated
- new nested OptimizeResults objects "ineqlin" (corresponding to inequality
constraints), "eqlin" (equality constraints), "lower", and "upper" (bound
constraints) are added, containing:
    - "ineqlin": "slack", "marginals"
    - "eqlin": "violation", "marginals"
    - "lower": "freedom", "marginals"
    - "upper": "freedom", "marginals"

Notes:
- "marginals" is chosen over e.g. "shadow price" to avoid jargon that is
associated with a particular field
- "slack" is obvious
- "freedom" was suggested by Julian Hall, creator and maintainer of HiGHS
- "violation", "eqlin", "ineqlin" are inspired by Matlab's result interface
- the new nested OptimizeResult objects will also house future ranging
sensitivity information
- this functionality is only available for the HiGHS solvers, i.e.
method='highs', 'highs-ds', or 'highs-ipm'

Please join us in the discussion on the PR or send feedback here.

Thanks,
Nicholas
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.python.org/pipermail/scipy-dev/attachments/20210517/70a07d5e/attachment.html>