# 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](/v1/tools/lp-dual-feasibility-check/versions/1.0.0) 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:

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

Response:

```json
{
  "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](/docs#connect)), then call `execute` with:

```json
{
  "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)

```sh
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](/v1/tools/lp-dual-feasibility-check/versions/1.0.0).

### CLI

```sh
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/](/clients/cli/).

## Related tools

- [Lp optimality certificate check](/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](/tools/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](/tools/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](/tools/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](/tools/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](/tools/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.