A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions Article Swipe
Bilevel linear programs (BLPs) form a class of hierarchical decision-making problems in which both the upper-level and the lower-level decision-makers, known as the leader and the follower, respectively, solve linear optimization problems. It is well-known that general BLPs are strongly $NP$-hard, even when the leader's and the follower's objective functions are exact opposites. However, the complexity classification of BLPs remains incomplete when one of the decision-makers has a fixed number of variables or constraints. In particular, it has been shown that optimistic BLPs are polynomially solvable when the number of follower variables is fixed, whereas both optimistic and pessimistic BLPs remain $NP$-hard even with a single leader variable and no upper-level constraints. In this note, we close the remaining gap in this complexity landscape. Specifically, we prove that BLPs are polynomially solvable in both the optimistic and the pessimistic settings when the number of follower constraints is fixed. In contrast, we also show that the pessimistic problem with a fixed number of follower variables is strongly $NP$-hard. To the best of our knowledge, this is the first result demonstrating that, under comparable assumptions, the pessimistic formulation is one complexity class harder than its optimistic counterpart.
Related Topics
Concepts
Metadata
- Type
- article
- Landing Page
- http://arxiv.org/abs/2511.15592
- https://arxiv.org/pdf/2511.15592
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W7106475680
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W7106475680Canonical identifier for this work in OpenAlex
- Title
-
A Note on the Complexity of Bilevel Linear Programs in Fixed DimensionsWork title
- Type
-
articleOpenAlex work type
- Publication year
-
2025Year of publication
- Publication date
-
2025-11-19Full publication date if available
- Authors
-
Ketkov, Sergey S., Prokopyev, Oleg A.List of authors in order
- Landing page
-
https://arxiv.org/abs/2511.15592Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2511.15592Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2511.15592Direct OA link when available
- Concepts
-
Mathematics, Pessimism, Class (philosophy), Variable (mathematics), Mathematical optimization, Variables, Bilevel optimization, Time complexity, Binary number, A priori and a posterioriTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W7106475680 |
|---|---|
| doi | |
| ids.openalex | https://openalex.org/W7106475680 |
| fwci | 0.0 |
| type | article |
| title | A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10545 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.28450822830200195 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1703 |
| topics[0].subfield.display_name | Computational Theory and Mathematics |
| topics[0].display_name | Optimization and Variational Analysis |
| topics[1].id | https://openalex.org/T11413 |
| topics[1].field.id | https://openalex.org/fields/18 |
| topics[1].field.display_name | Decision Sciences |
| topics[1].score | 0.2560795247554779 |
| topics[1].domain.id | https://openalex.org/domains/2 |
| topics[1].domain.display_name | Social Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1803 |
| topics[1].subfield.display_name | Management Science and Operations Research |
| topics[1].display_name | Risk and Portfolio Optimization |
| topics[2].id | https://openalex.org/T10963 |
| topics[2].field.id | https://openalex.org/fields/26 |
| topics[2].field.display_name | Mathematics |
| topics[2].score | 0.219893679022789 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2612 |
| topics[2].subfield.display_name | Numerical Analysis |
| topics[2].display_name | Advanced Optimization Algorithms Research |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C33923547 |
| concepts[0].level | 0 |
| concepts[0].score | 0.7228258848190308 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[0].display_name | Mathematics |
| concepts[1].id | https://openalex.org/C9992130 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6212413907051086 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q484954 |
| concepts[1].display_name | Pessimism |
| concepts[2].id | https://openalex.org/C2777212361 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5819281935691833 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q5127848 |
| concepts[2].display_name | Class (philosophy) |
| concepts[3].id | https://openalex.org/C182365436 |
| concepts[3].level | 2 |
| concepts[3].score | 0.4378783702850342 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q50701 |
| concepts[3].display_name | Variable (mathematics) |
| concepts[4].id | https://openalex.org/C126255220 |
| concepts[4].level | 1 |
| concepts[4].score | 0.33142751455307007 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[4].display_name | Mathematical optimization |
| concepts[5].id | https://openalex.org/C27574286 |
| concepts[5].level | 2 |
| concepts[5].score | 0.2931404113769531 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q320723 |
| concepts[5].display_name | Variables |
| concepts[6].id | https://openalex.org/C3309286 |
| concepts[6].level | 3 |
| concepts[6].score | 0.2746867835521698 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q4907693 |
| concepts[6].display_name | Bilevel optimization |
| concepts[7].id | https://openalex.org/C311688 |
| concepts[7].level | 2 |
| concepts[7].score | 0.27460888028144836 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[7].display_name | Time complexity |
| concepts[8].id | https://openalex.org/C48372109 |
| concepts[8].level | 2 |
| concepts[8].score | 0.2683015465736389 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q3913 |
| concepts[8].display_name | Binary number |
| concepts[9].id | https://openalex.org/C75553542 |
| concepts[9].level | 2 |
| concepts[9].score | 0.2618306875228882 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q178161 |
| concepts[9].display_name | A priori and a posteriori |
| keywords[0].id | https://openalex.org/keywords/pessimism |
| keywords[0].score | 0.6212413907051086 |
| keywords[0].display_name | Pessimism |
| keywords[1].id | https://openalex.org/keywords/class |
| keywords[1].score | 0.5819281935691833 |
| keywords[1].display_name | Class (philosophy) |
| keywords[2].id | https://openalex.org/keywords/variable |
| keywords[2].score | 0.4378783702850342 |
| keywords[2].display_name | Variable (mathematics) |
| keywords[3].id | https://openalex.org/keywords/variables |
| keywords[3].score | 0.2931404113769531 |
| keywords[3].display_name | Variables |
| keywords[4].id | https://openalex.org/keywords/bilevel-optimization |
| keywords[4].score | 0.2746867835521698 |
| keywords[4].display_name | Bilevel optimization |
| language | |
| locations[0].id | pmh:oai:arXiv.org:2511.15592 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2511.15592 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2511.15592 |
| indexed_in | arxiv |
| authorships[0].author.id | https://openalex.org/A4281358242 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Ketkov, Sergey S. |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Ketkov, Sergey S. |
| authorships[0].is_corresponding | True |
| authorships[1].author.id | |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Prokopyev, Oleg A. |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Prokopyev, Oleg A. |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2511.15592 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-11-23T00:00:00 |
| display_name | A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-23T05:13:22.807545 |
| primary_topic.id | https://openalex.org/T10545 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.28450822830200195 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1703 |
| primary_topic.subfield.display_name | Computational Theory and Mathematics |
| primary_topic.display_name | Optimization and Variational Analysis |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:arXiv.org:2511.15592 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2511.15592 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2511.15592 |
| primary_location.id | pmh:oai:arXiv.org:2511.15592 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2511.15592 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2511.15592 |
| publication_date | 2025-11-19 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 5, 67, 104, 158 |
| abstract_inverted_index.In | 74, 112, 148 |
| abstract_inverted_index.It | 32 |
| abstract_inverted_index.To | 167 |
| abstract_inverted_index.as | 21 |
| abstract_inverted_index.in | 11, 120, 132 |
| abstract_inverted_index.is | 33, 92, 146, 164, 174, 186 |
| abstract_inverted_index.it | 76 |
| abstract_inverted_index.no | 109 |
| abstract_inverted_index.of | 7, 57, 63, 70, 89, 143, 161, 170 |
| abstract_inverted_index.or | 72 |
| abstract_inverted_index.we | 115, 125, 150 |
| abstract_inverted_index.and | 16, 24, 45, 97, 108, 136 |
| abstract_inverted_index.are | 38, 50, 83, 129 |
| abstract_inverted_index.gap | 119 |
| abstract_inverted_index.has | 66, 77 |
| abstract_inverted_index.its | 192 |
| abstract_inverted_index.one | 62, 187 |
| abstract_inverted_index.our | 171 |
| abstract_inverted_index.the | 14, 17, 22, 25, 43, 46, 54, 64, 87, 117, 134, 137, 141, 154, 168, 175, 183 |
| abstract_inverted_index.BLPs | 37, 58, 82, 99, 128 |
| abstract_inverted_index.also | 151 |
| abstract_inverted_index.been | 78 |
| abstract_inverted_index.best | 169 |
| abstract_inverted_index.both | 13, 95, 133 |
| abstract_inverted_index.even | 41, 102 |
| abstract_inverted_index.form | 4 |
| abstract_inverted_index.show | 152 |
| abstract_inverted_index.than | 191 |
| abstract_inverted_index.that | 35, 80, 127, 153 |
| abstract_inverted_index.this | 113, 121, 173 |
| abstract_inverted_index.when | 42, 61, 86, 140 |
| abstract_inverted_index.with | 103, 157 |
| abstract_inverted_index.class | 6, 189 |
| abstract_inverted_index.close | 116 |
| abstract_inverted_index.exact | 51 |
| abstract_inverted_index.first | 176 |
| abstract_inverted_index.fixed | 68, 159 |
| abstract_inverted_index.known | 20 |
| abstract_inverted_index.note, | 114 |
| abstract_inverted_index.prove | 126 |
| abstract_inverted_index.shown | 79 |
| abstract_inverted_index.solve | 28 |
| abstract_inverted_index.that, | 179 |
| abstract_inverted_index.under | 180 |
| abstract_inverted_index.which | 12 |
| abstract_inverted_index.(BLPs) | 3 |
| abstract_inverted_index.fixed, | 93 |
| abstract_inverted_index.fixed. | 147 |
| abstract_inverted_index.harder | 190 |
| abstract_inverted_index.leader | 23, 106 |
| abstract_inverted_index.linear | 1, 29 |
| abstract_inverted_index.number | 69, 88, 142, 160 |
| abstract_inverted_index.remain | 100 |
| abstract_inverted_index.result | 177 |
| abstract_inverted_index.single | 105 |
| abstract_inverted_index.Bilevel | 0 |
| abstract_inverted_index.general | 36 |
| abstract_inverted_index.problem | 156 |
| abstract_inverted_index.remains | 59 |
| abstract_inverted_index.whereas | 94 |
| abstract_inverted_index.However, | 53 |
| abstract_inverted_index.follower | 90, 144, 162 |
| abstract_inverted_index.leader's | 44 |
| abstract_inverted_index.problems | 10 |
| abstract_inverted_index.programs | 2 |
| abstract_inverted_index.settings | 139 |
| abstract_inverted_index.solvable | 85, 131 |
| abstract_inverted_index.strongly | 39, 165 |
| abstract_inverted_index.variable | 107 |
| abstract_inverted_index.$NP$-hard | 101 |
| abstract_inverted_index.contrast, | 149 |
| abstract_inverted_index.follower, | 26 |
| abstract_inverted_index.functions | 49 |
| abstract_inverted_index.objective | 48 |
| abstract_inverted_index.problems. | 31 |
| abstract_inverted_index.remaining | 118 |
| abstract_inverted_index.variables | 71, 91, 163 |
| abstract_inverted_index.$NP$-hard, | 40 |
| abstract_inverted_index.$NP$-hard. | 166 |
| abstract_inverted_index.comparable | 181 |
| abstract_inverted_index.complexity | 55, 122, 188 |
| abstract_inverted_index.follower's | 47 |
| abstract_inverted_index.incomplete | 60 |
| abstract_inverted_index.knowledge, | 172 |
| abstract_inverted_index.landscape. | 123 |
| abstract_inverted_index.opposites. | 52 |
| abstract_inverted_index.optimistic | 81, 96, 135, 193 |
| abstract_inverted_index.well-known | 34 |
| abstract_inverted_index.constraints | 145 |
| abstract_inverted_index.formulation | 185 |
| abstract_inverted_index.lower-level | 18 |
| abstract_inverted_index.particular, | 75 |
| abstract_inverted_index.pessimistic | 98, 138, 155, 184 |
| abstract_inverted_index.upper-level | 15, 110 |
| abstract_inverted_index.assumptions, | 182 |
| abstract_inverted_index.constraints. | 73, 111 |
| abstract_inverted_index.counterpart. | 194 |
| abstract_inverted_index.hierarchical | 8 |
| abstract_inverted_index.optimization | 30 |
| abstract_inverted_index.polynomially | 84, 130 |
| abstract_inverted_index.Specifically, | 124 |
| abstract_inverted_index.demonstrating | 178 |
| abstract_inverted_index.respectively, | 27 |
| abstract_inverted_index.classification | 56 |
| abstract_inverted_index.decision-makers | 65 |
| abstract_inverted_index.decision-making | 9 |
| abstract_inverted_index.decision-makers, | 19 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile.value | 0.81082091 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |