# Lp optimality certificate check

`lp-optimality-certificate-check` · version 1.0.0 · Numbers & math · free, no key needed

Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.

**Use when you need to: verify an lp optimal solution with a dual certificate · check complementary slackness for x and y · prove a linear program optimum by strong duality.**

## Decide before calling

Read the [versioned contract](/v1/tools/lp-optimality-certificate-check/versions/1.0.0) and the supported scope below. Reuse `lp-optimality-certificate-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-optimality-certificate-check@1.0.0` for verify an lp optimal solution with a dual certificate. 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

- verify an lp optimal solution with a dual certificate
- check complementary slackness for x and y
- prove a linear program optimum by strong duality
- is this claimed lp optimum really optimal
- check primal and dual objective values are equal
- validate a solver optimality certificate with exact fractions

## Not supported

- solving the linear program or producing the dual solution
- certifying infeasibility or unboundedness (Farkas rays are not accepted)
- 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, dual minimize y.b subject to y.A >= c, y >= 0 (Schrijver 1986, s7.4 Corollary 7.1g, s7.9 complementary slackness; 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: x_j >= 0 (j ascending); (A.x)_i <= b_i (i ascending); y_i >= 0 (i ascending); (y.A)_j >= c_j (j ascending); complementary slackness rows y_i * (b_i - (A.x)_i) = 0 (i ascending) then columns x_j * ((y.A)_j - c_j) = 0 (j ascending); then (only if claimed_optimum is given) c.x = claimed_optimum.
- primal_objective = c.x, dual_objective = y.b and duality_gap = y.b - c.x are always returned. The gap equals the sum of the slackness products, so after feasibility it is 0 exactly when slackness holds; valid true proves both x and y optimal with optimum value primal_objective.

## 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]+)?$`
- `x` (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]+)?$`
- `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_optimum` (string, optional): max length 40; pattern `^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\.[0-9]+)?$`

## Output

- `valid` (boolean, required)
- `reason` (one of "primal_bound_violated", "primal_constraint_violated", "dual_sign_violated", "dual_constraint_violated", "complementary_slackness_violated", "claimed_optimum_mismatch", null, required)
- `first_discrepancy` (object or null, required)
- `primal_objective` (string, required): pattern `^(0|-?[1-9][0-9]*(/[1-9][0-9]*)?)$`
- `dual_objective` (string, required): pattern `^(0|-?[1-9][0-9]*(/[1-9][0-9]*)?)$`
- `duality_gap` (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"
  ],
  "x": [
    "2",
    "6"
  ],
  "y": [
    "0",
    "3/2",
    "1"
  ],
  "claimed_optimum": "36"
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "primal_objective": "36",
    "dual_objective": "36",
    "duality_gap": "0",
    "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-optimality-certificate-check",
  "version": "1.0.0",
  "input": {
    "objective": [
      "3",
      "5"
    ],
    "matrix": [
      [
        "1",
        "0"
      ],
      [
        "0",
        "2"
      ],
      [
        "3",
        "2"
      ]
    ],
    "rhs": [
      "4",
      "12",
      "18"
    ],
    "x": [
      "2",
      "6"
    ],
    "y": [
      "0",
      "3/2",
      "1"
    ],
    "claimed_optimum": "36"
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/lp-optimality-certificate-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"],"x":["2","6"],"y":["0","3/2","1"],"claimed_optimum":"36"}'
```

The machine-readable contract is at [/v1/tools/lp-optimality-certificate-check/versions/1.0.0](/v1/tools/lp-optimality-certificate-check/versions/1.0.0).

### CLI

```sh
node cli.mjs run lp-optimality-certificate-check 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Lp dual feasibility check](/tools/lp-dual-feasibility-check): Check that LP dual multipliers satisfy y >= 0 and yA >= c exactly; return the proven upper bound y.b.
- [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 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.
- [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.
- [Chromatic certificate check](/tools/chromatic-certificate-check): Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.