{"id":"lp-optimality-certificate-check","version":"1.0.0","description":"Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.","supported_operations":["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"],"unsupported_operations":["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)"],"semantics":["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."],"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","y"],"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}},"y":{"type":"array","maxItems":40,"items":{"type":"string","pattern":"^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\\.[0-9]+)?$","maxLength":40}},"claimed_optimum":{"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","primal_objective","dual_objective","duality_gap","form","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":["primal_bound_violated","primal_constraint_violated","dual_sign_violated","dual_constraint_violated","complementary_slackness_violated","claimed_optimum_mismatch",null]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["check","index","lhs","relation","rhs"],"properties":{"check":{"type":"string","enum":["primal_bound","primal_constraint","dual_sign","dual_constraint","complementary_slackness_row","complementary_slackness_column","claimed_optimum"]},"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]*)?)$"}}},"primal_objective":{"type":"string","pattern":"^(0|-?[1-9][0-9]*(/[1-9][0-9]*)?)$"},"dual_objective":{"type":"string","pattern":"^(0|-?[1-9][0-9]*(/[1-9][0-9]*)?)$"},"duality_gap":{"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"],"y":["0","3/2","1"],"claimed_optimum":"36"},"output":{"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"}},{"input":{"objective":["3","5"],"matrix":[["1","0"],["0","2"],["3","2"]],"rhs":["4","12","18"],"x":["2","6"],"y":["0","5/2","1"]},"output":{"valid":false,"reason":"complementary_slackness_violated","first_discrepancy":{"check":"complementary_slackness_column","index":1,"lhs":"12","relation":"=","rhs":"0"},"primal_objective":"36","dual_objective":"48","duality_gap":"12","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-optimality-certificate-check/versions/1.0.0/execute"}