Id: arxiv/2603.17107 Url: https://arxiv.org/abs/2603.17107 Tags: math.OC, cs.CC Score: 0 Title: On Big-M Reformulations of Bilevel Linear Programs: Hardness of A Posteriori Verification Domain: math.OC Source: arxiv Authors: Sergey S. Ketkov, Oleg A. Prokopyev Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-17 Page: https://delphi.science/r/arxiv/2603.17107 A standard approach to solving optimistic bilevel linear programs (BLPs) is to replace the lower-level problem with its Karush-Kuhn-Tucker (KKT) optimality conditions and reformulate the resulting complementarity constraints using auxiliary binary variables. This yields a single-level mixed-integer linear programming (MILP) model involving big-$M$ parameters. While sufficiently large and bilevel-correct big-$M$s can be computed in polynomial time, verifying a priori that given big-$M$s do not cut off any feasible or optimal lower-level solutions is known to be computationally difficult. In…