Lp dual feasibility check

lp-dual-feasibility-check · version 1.0.0 · Numbers & math · free, no key needed

Check that LP dual multipliers satisfy y >= 0 and yA >= c exactly; return the proven upper bound y.b.

Use when you need to: check lp dual multipliers are feasible · verify an upper bound certificate for a linear program · prove no lp solution exceeds a value with dual weights.

Decide before calling

Read the versioned contract and the supported scope below. Reuse lp-dual-feasibility-check@1.0.0 when your input, required output and limits match it. Choose another approach for an unsupported operation.

Explain the choice

"I can use lp-dual-feasibility-check@1.0.0 for check lp dual multipliers are feasible. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured."

Supported

• check lp dual multipliers are feasible
• verify an upper bound certificate for a linear program
• prove no lp solution exceeds a value with dual weights
• check y >= 0 and y times a >= c exactly
• validate shadow prices as a dual feasible solution
• weak duality bound from claimed dual variables

Not supported

• computing optimal dual values or shadow prices (this only checks a supplied y)
• claiming the bound is the optimum (use lp-optimality-certificate-check with a primal point)
• other standard forms (minimization, equality rows, free variables) without rewriting first
• floating-point tolerances (all comparisons are exact)

Behavior

• Standard form: maximize c.x subject to A.x <= b, x >= 0; its dual is minimize y.b subject to y.A >= c, y >= 0 (Schrijver 1986, s7.4 Corollary 7.1g; reference_version schrijver-1986-tlip-s7.4-s7.9).
• Numbers are exact rational strings (integer, p/q, or finite decimal; at most 40 characters); output rationals are reduced and canonical, zero is "0".
• Check order: signs y_i >= 0 for i ascending, then columns (y.A)_j >= c_j for j ascending, then (only if claimed_bound is given) y.b = claimed_bound. The first failure is returned as first_discrepancy {check, index, lhs, relation, rhs}.
• dual_objective = y.b is always returned; when valid it is a proven upper bound on c.x over the feasible region (weak duality), not a claim of optimality. With no rows, y is empty and y.A is the zero vector.

Input

• objective (array of string, required): min items 1; max items 40; each max length 40; each pattern ^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$
• matrix (array of array of string, required): max items 40; each min items 1; each max items 40; each each max length 40; each each pattern ^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$
• rhs (array of string, required): max items 40; each max length 40; each pattern ^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$
• y (array of string, required): max items 40; each max length 40; each pattern ^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$
• claimed_bound (string, optional): max length 40; pattern ^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$

Output

• valid (boolean, required)
• reason (one of "dual_sign_violated", "dual_constraint_violated", "claimed_bound_mismatch", null, required)
• first_discrepancy (object or null, required)
• dual_objective (string, required): pattern ^(0|-?[1-9][0-9]*(/[1-9][0-9]*)?)$
• form (constant "max c.x subject to A.x <= b, x >= 0", required)
• reference_version (constant "schrijver-1986-tlip-s7.4-s7.9", required)

Limits

• max variables: 40
• max constraints: 40
• max number chars: 40

Example

Request input:

{
  "objective": [
    "3",
    "5"
  ],
  "matrix": [
    [
      "1",
      "0"
    ],
    [
      "0",
      "2"
    ],
    [
      "3",
      "2"
    ]
  ],
  "rhs": [
    "4",
    "12",
    "18"
  ],
  "y": [
    "0",
    "3/2",
    "1"
  ],
  "claimed_bound": "36"
}

Response:

{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "dual_objective": "36",
    "form": "max c.x subject to A.x <= b, x >= 0",
    "reference_version": "schrijver-1986-tlip-s7.4-s7.9"
  }
}

How to call it

MCP

Connect https://computefirst.net/mcp (setup), then call execute with:

{
  "id": "lp-dual-feasibility-check",
  "version": "1.0.0",
  "input": {
    "objective": [
      "3",
      "5"
    ],
    "matrix": [
      [
        "1",
        "0"
      ],
      [
        "0",
        "2"
      ],
      [
        "3",
        "2"
      ]
    ],
    "rhs": [
      "4",
      "12",
      "18"
    ],
    "y": [
      "0",
      "3/2",
      "1"
    ],
    "claimed_bound": "36"
  }
}

HTTP (no key)

curl -X POST https://computefirst.net/v1/tools/lp-dual-feasibility-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"objective":["3","5"],"matrix":[["1","0"],["0","2"],["3","2"]],"rhs":["4","12","18"],"y":["0","3/2","1"],"claimed_bound":"36"}'

The machine-readable contract is at /v1/tools/lp-dual-feasibility-check/versions/1.0.0.

CLI

node cli.mjs run lp-dual-feasibility-check 1.0.0 --input input.json --base-url https://computefirst.net

Get the client at /clients/cli/.

Related tools

• Lp optimality certificate check: Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.
• Lp primal feasibility check: Check that a claimed LP point satisfies x >= 0 and Ax <= b exactly; report the first violated bound or row.
• Linear inconsistency certificate check: Check a witness y that A x = b has no solution (yA = 0, yb != 0) or no x >= 0 solution (Farkas: yA >= 0, yb < 0).
• Maximum flow certificate check: Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.
• Linear residual check: Check a claimed residual r = b - A x (per component and/or its max norm) exactly for an approximate solution x.
• Network flow feasibility check: Check a claimed s-t flow for capacity bounds and conservation with exact integers; returns the first bad edge or node.