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 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:

{
  "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:

{
  "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), then call execute with:

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

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.

CLI

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/.

Related 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: Check that a claimed LP point satisfies x >= 0 and Ax <= b exactly; report the first violated bound or row.
• 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: 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.
• Chromatic certificate check: Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.