{"id":"lp-dual-feasibility-check","version":"1.0.0","description":"Check that LP dual multipliers satisfy y >= 0 and yA >= c exactly; return the proven upper bound y.b.","supported_operations":["check lp dual multipliers are feasible","verify an upper bound certificate for a linear program","prove no lp solution exceeds a value with dual weights","check y >= 0 and y times a >= c exactly","validate shadow prices as a dual feasible solution","weak duality bound from claimed dual variables"],"unsupported_operations":["computing optimal dual values or shadow prices (this only checks a supplied y)","claiming the bound is the optimum (use lp-optimality-certificate-check with a primal point)","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; its dual is minimize y.b subject to y.A >= c, y >= 0 (Schrijver 1986, s7.4 Corollary 7.1g; 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: signs y_i >= 0 for i ascending, then columns (y.A)_j >= c_j for j ascending, then (only if claimed_bound is given) y.b = claimed_bound. The first failure is returned as first_discrepancy {check, index, lhs, relation, rhs}.","dual_objective = y.b is always returned; when valid it is a proven upper bound on c.x over the feasible region (weak duality), not a claim of optimality. With no rows, y is empty and y.A is the zero vector."],"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","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}},"y":{"type":"array","maxItems":40,"items":{"type":"string","pattern":"^-?(0|[1-9][0-9]*)(/[1-9][0-9]*|\\.[0-9]+)?$","maxLength":40}},"claimed_bound":{"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","dual_objective","form","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":["dual_sign_violated","dual_constraint_violated","claimed_bound_mismatch",null]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"required":["check","index","lhs","relation","rhs"],"properties":{"check":{"type":"string","enum":["dual_sign","dual_constraint","claimed_bound"]},"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]*)?)$"}}},"dual_objective":{"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"],"y":["0","3/2","1"],"claimed_bound":"36"},"output":{"valid":true,"reason":null,"first_discrepancy":null,"dual_objective":"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"],"y":["0","1","1"]},"output":{"valid":false,"reason":"dual_constraint_violated","first_discrepancy":{"check":"dual_constraint","index":1,"lhs":"4","relation":">=","rhs":"5"},"dual_objective":"30","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-dual-feasibility-check/versions/1.0.0/execute"}