Skip to content

[FEA] LP sensitivity ranging (RHS + objective-coefficient ranges) #1395

Closed as not planned

Description

@cafzal

Is your feature request related to a problem? Please describe.
cuOpt exposes shadow prices (duals) and reduced costs, but not their validity ranges — the rest of the classic LP sensitivity report:

  • RHS ranging — how far each constraint's right-hand side can move before its shadow price changes.
  • Objective-coefficient ranging — how far each cost coefficient can change before the current basis stops being optimal.

Duals give the marginal rate; ranging gives how far it holds — the "how much can I change this before the answer changes" companion that every LP sensitivity report provides (Excel Solver's sensitivity report; Gurobi SARHSLow/Up, SAObjLow/Up; HiGHS getRanging()). Surfaced in the same integration use as #1394.

Describe the solution you'd like
A public ranging API on the LP solution returning four arrays — objective-coefficient lower/upper per variable, and RHS lower/upper per constraint — computed from the optimal basis. The numerical primitives already exist in the dual simplex: factorize_basis, b_solve / b_transpose_solve (ftran/btran), and the ratio_test / bound_flipping_ratio_test machinery. So this is a new orchestration module (ranging ratio-tests over the existing factorization) + the public API + C API/bindings/tests — not a from-scratch solver.

Design questions:

  1. PDLP semantics — ranging needs a basis, so it applies to the dual-simplex (or post-crossover) path; PDLP-only returns unavailable. Define behavior.
  2. API shape — a single getRanging()-style struct vs. four accessors.
  3. Degeneracy — ranges are ill-defined / one-sided at degenerate vertices; the report should flag rather than mislead.

Describe alternatives you've considered

  • Approximating ranges by re-solving with perturbed RHS / cost (finite differences) — many extra solves, inexact, and it doesn't recover the exact breakpoints the basis gives for free.

Additional context

Related: the diet LP duals example — NVIDIA/cuopt-examples#154 — already adds shadow prices + reduced costs; ranging slots in here as their validity ranges.

Activity

  1. mlubin commented on Jun 22, 2026

    @mlubin
    Contributor

    My impression is that these ranging computations are nice in toy examples but don't really apply to industrial scale problems where degeneracy is the norm. Do you have experience otherwise?

  2. cafzal commented on Jun 23, 2026

    @cafzal
    ContributorAuthor

    Fair point @mlubin . That moves me toward basis status as the higher value addition. Happy to rescope this one to ranges-only-with-a-uniqueness-flag, or deprioritize it. Appreciate the feedback.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions