Paper

{
  "raw_xml": "<entry>\n    <id>http://arxiv.org/abs/2603.17107v1</id>\n    <title>On Big-M Reformulations of Bilevel Linear Programs: Hardness of A Posteriori Verification</title>\n    <updated>2026-03-17T19:57:57Z</updated>\n    <link href='https://arxiv.org/abs/2603.17107v1' rel='alternate' type='text/html'/>\n    <link href='https://arxiv.org/pdf/2603.17107v1' rel='related' title='pdf' type='application/pdf'/>\n    <summary>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 this paper, we establish two complementary hardness results. First, we show that, even with a single potentially incorrect big-$M$ parameter, it is $coNP$-complete to verify a posteriori whether the optimal solution of the resulting MILP model is bilevel optimal. In particular, this negative result persists for min-max problems without coupling constraints and applies to strong-duality-based reformulations of mixed-integer BLPs. Second, we show that verifying global big-$M$ correctness remains computationally difficult a posteriori, even when an optimal solution of the MILP model is available.</summary>\n    <category scheme='http://arxiv.org/schemas/atom' term='math.OC'/>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.CC'/>\n    <published>2026-03-17T19:57:57Z</published>\n    <arxiv:primary_category term='math.OC'/>\n    <author>\n      <name>Sergey S. Ketkov</name>\n    </author>\n    <author>\n      <name>Oleg A. Prokopyev</name>\n    </author>\n  </entry>"
}