{"id":"lp-primal-feasibility-check","version":"1.0.0","description":"Check that a claimed LP point satisfies x >= 0 and Ax <= b exactly; report the first violated bound or row.","supported_operations":["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"],"unsupported_operations":["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)"],"semantics":["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."],"limits":{"max_variables":40,"max_constraints":40,"max_number_chars":40},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["objective","matrix","rhs","x"],"properties":{"objective":{"type":"array","minItems":1,"maxItems":40,"items":{"type":"string","pattern":"^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\\.[0-9]+)?$","maxLength":40}},"matrix":{"type":"array","maxItems":40,"items":{"type":"array","minItems":1,"maxItems":40,"items":{"type":"string","pattern":"^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\\.[0-9]+)?$","maxLength":40}}},"rhs":{"type":"array","maxItems":40,"items":{"type":"string","pattern":"^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\\.[0-9]+)?$","maxLength":40}},"x":{"type":"array","minItems":1,"maxItems":40,"items":{"type":"string","pattern":"^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\\.[0-9]+)?$","maxLength":40}},"claimed_objective":{"type":"string","pattern":"^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\\.[0-9]+)?$","maxLength":40}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","objective_value","form","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":["primal_bound_violated","primal_constraint_violated","claimed_objective_mismatch",null]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["check","index","lhs","relation","rhs"],"properties":{"check":{"type":"string","enum":["primal_bound","primal_constraint","claimed_objective"]},"index":{"type":["integer","null"],"minimum":0},"lhs":{"type":"string","pattern":"^(0|-?[1-9][0-9]*(/[1-9][0-9]*)?)$"},"relation":{"type":"string","enum":[">=","<=","="]},"rhs":{"type":"string","pattern":"^(0|-?[1-9][0-9]*(/[1-9][0-9]*)?)$"}}},"objective_value":{"type":"string","pattern":"^(0|-?[1-9][0-9]*(/[1-9][0-9]*)?)$"},"form":{"type":"string","const":"max c.x subject to A.x <= b, x >= 0"},"reference_version":{"type":"string","const":"schrijver-1986-tlip-s7.4-s7.9"}}},"examples":[{"input":{"objective":["3","5"],"matrix":[["1","0"],["0","2"],["3","2"]],"rhs":["4","12","18"],"x":["2","6"],"claimed_objective":"36"},"output":{"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"}},{"input":{"objective":["3","5"],"matrix":[["1","0"],["0","2"],["3","2"]],"rhs":["4","12","18"],"x":["4","6"]},"output":{"valid":false,"reason":"primal_constraint_violated","first_discrepancy":{"check":"primal_constraint","index":2,"lhs":"24","relation":"<=","rhs":"18"},"objective_value":"42","form":"max c.x subject to A.x <= b, x >= 0","reference_version":"schrijver-1986-tlip-s7.4-s7.9"}}],"execute_url":"/v1/tools/lp-primal-feasibility-check/versions/1.0.0/execute"}