On Coupling Constraints in Linear Bilevel Optimization

Jointly with Dorothee Henke, Martin Schmidt, Johannes Thürauf

Year: 2024

Abstract: It is well-known that coupling constraints in linear bilevel optimization can lead to disconnected feasible sets, which is not possible without coupling constraints. However, there is no difference between linear bilevel problems with and without coupling constraints w.r.t. their complexity-theoretical hardness. In this note, we prove that, although there is a clear difference between these two classes of problems in terms of their feasible sets, the classes are equivalent on the level of optimal solutions. To this end, given a general linear bilevel problem with coupling constraints, we derive a respective problem without coupling constraints and prove that it has the same optimal solutions (when projected back to the original variable space).

Cite as:

@article{Henke2024,
  title = {On coupling constraints in linear bilevel optimization},
  volume = {19},
  ISSN = {1862-4480},
  DOI = {10.1007/s11590-024-02156-3},
  number = {3},
  journal = {Optimization Letters},
  publisher = {Springer Science and Business Media LLC},
  author = {Henke,  Dorothee and Lefebvre,  Henri and Schmidt,  Martin and Th\"{u}rauf,  Johannes},
  year = {2024},
  X_month = dec,
  pages = {689--697}
}

Open Access

Optimization Online - arXiv

Open Data

We did not use any data.

Open Methodology

We did not do data manipulation.

Open Source

We did not use any code.

Open Educational Resources