Lp primal feasibility check

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

Check that a claimed LP point satisfies x >= 0 and Ax <= b exactly; report the first violated bound or row.

Use when you need to: check that an lp solution is feasible · verify x satisfies ax <= b and x >= 0 exactly · which constraint does this linear program point violate.

Decide before calling

Read the versioned contract and the supported scope below. Reuse lp-primal-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-primal-feasibility-check@1.0.0 for check that an lp solution is 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 that an lp solution is feasible
• verify x satisfies ax <= b and x >= 0 exactly
• which constraint does this linear program point violate
• validate a claimed primal feasible point with fractions
• check a linear programming solution against its constraints
• confirm the objective value of a feasible lp point

Not supported

• solving the linear program or finding an optimal point (this only checks a supplied x)
• other standard forms (minimization, equality rows, free variables): rewrite into max c.x, A.x <= b, x >= 0 first
• floating-point tolerances (all comparisons are exact)
• integer programming feasibility (integrality is not checked)

Behavior

• Standard form: maximize c.x subject to A.x <= b and x >= 0 (objective c of n <= 40 entries, matrix A of m <= 40 rows, rhs b). Reference: Schrijver 1986, Theory of Linear and Integer Programming, s7.4 (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: bounds x_j >= 0 for j ascending, then rows (A.x)_i <= b_i for i ascending, then (only if claimed_objective is given) c.x = claimed_objective. The first failure is returned as first_discrepancy {check, index, lhs, relation, rhs}.
• objective_value = c.x is always returned; a binding row ((A.x)_i = b_i) is feasible.

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]+)?$
• claimed_objective (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", "claimed_objective_mismatch", null, required)
• first_discrepancy (object or null, required)
• objective_value (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"
  ],
  "claimed_objective": "36"
}

Response:

{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "objective_value": "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-primal-feasibility-check",
  "version": "1.0.0",
  "input": {
    "objective": [
      "3",
      "5"
    ],
    "matrix": [
      [
        "1",
        "0"
      ],
      [
        "0",
        "2"
      ],
      [
        "3",
        "2"
      ]
    ],
    "rhs": [
      "4",
      "12",
      "18"
    ],
    "x": [
      "2",
      "6"
    ],
    "claimed_objective": "36"
  }
}

HTTP (no key)

curl -X POST https://computefirst.net/v1/tools/lp-primal-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"],"x":["2","6"],"claimed_objective":"36"}'

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

CLI

node cli.mjs run lp-primal-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 dual feasibility check: Check that LP dual multipliers satisfy y >= 0 and yA >= c exactly; return the proven upper bound y.b.
• 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).
• 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 solution check: Check that a proposed solution x satisfies A x = b exactly over the rationals and report the first row that fails.
• Maximum flow certificate check: Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.