A New Computational Approach for Solving Linear Bilevel Programs Based on Parameter-Free Disjunctive Decomposition
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929386781933568 |
|---|---|
| author | Mohammadi, Saeed Hesamzadeh, Mohammad Reza Gabriel, Steven A. Khastieva, Dina |
| author_facet | Mohammadi, Saeed Hesamzadeh, Mohammad Reza Gabriel, Steven A. Khastieva, Dina |
| contents | Linear bilevel programs (linear BLPs) have been widely used in computational mathematics and optimization in several applications. Single-level reformulation for linear BLPs replaces the lower-level linear program with its Karush-Kuhn-Tucker optimality conditions and linearizes the complementary slackness conditions using the big-M technique. Although the approach is straightforward, it requires finding the big-M whose computation is recently shown to be NP-hard. This paper presents a disjunctive-based decomposition algorithm which does not need finding the big-Ms whereas guaranteeing that obtained solution is optimal. Our experience shows promising performance of our algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_06069 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A New Computational Approach for Solving Linear Bilevel Programs Based on Parameter-Free Disjunctive Decomposition Mohammadi, Saeed Hesamzadeh, Mohammad Reza Gabriel, Steven A. Khastieva, Dina Systems and Control Optimization and Control Linear bilevel programs (linear BLPs) have been widely used in computational mathematics and optimization in several applications. Single-level reformulation for linear BLPs replaces the lower-level linear program with its Karush-Kuhn-Tucker optimality conditions and linearizes the complementary slackness conditions using the big-M technique. Although the approach is straightforward, it requires finding the big-M whose computation is recently shown to be NP-hard. This paper presents a disjunctive-based decomposition algorithm which does not need finding the big-Ms whereas guaranteeing that obtained solution is optimal. Our experience shows promising performance of our algorithm. |
| title | A New Computational Approach for Solving Linear Bilevel Programs Based on Parameter-Free Disjunctive Decomposition |
| topic | Systems and Control Optimization and Control |
| url | https://arxiv.org/abs/2203.06069 |