{"id":"arxiv/2609.10233","url":"https://arxiv.org/abs/2609.10233","tags":["cs.CC","math.OC"],"score":0,"title":"On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs","domain":"cs.CC","source":"arxiv","authors":["Sergey S. Ketkov","Oleg A. Prokopyev"],"reviews":0,"subject":"cs.CC","summary":"Exact algorithms for solving mixed-integer bilevel linear programs (MIBLPs) typically rely on sequences of lower and upper bounds that converge to the optimal value. These procedures are commonly initialized using the single-level relaxation (SLR), obtained by omitting the follower's optimality condition and solving the resulting single-level optimization problem. In this paper, we investigate whether, for broad classes of MIBLPs, the resulting standard bounds admit uniform improvements that can be computed within the same computational complexity regime. For pure continuous bilevel linear…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-09","reactions":{}}