<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>264</id>
    <completedYear>2019</completedYear>
    <publishedYear/>
    <thesisYearAccepted>2020</thesisYearAccepted>
    <language>eng</language>
    <pageFirst>1716</pageFirst>
    <pageLast>1721</pageLast>
    <pageNumber>6</pageNumber>
    <edition/>
    <issue>68(6)</issue>
    <volume/>
    <type>preprint</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>1</belongsToBibliography>
    <completedDate>2019-04-23</completedDate>
    <publishedDate>2019-04-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">There's No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization</title>
    <abstract language="eng">One of the most frequently used approaches to solve linear bilevel optimization problems consists in replacing the lower-level problem with its Karush-Kuhn-Tucker (KKT) conditions and by reformulating the KKT complementarity conditions using techniques from mixed-integer linear optimization. The latter step requires to determine some big-M constant in order to bound the lower level's dual feasible set such that no bilevel-optimal solution is cut off. In practice, heuristics are often used to find a big-M although it is known that these approaches may fail. In this paper, we consider the hardness of two proxies for the above mentioned concept of a bilevel-correct big-M. First, we prove that verifying that a given big-M does not cut off any feasible vertex of the lower level's dual polyhedron cannot be done in polynomial time unless P=NP. Second, we show that verifying that a given big-M does not cut off any optimal point of the lower level's dual problem (for any point in the projection of the high-point relaxation onto the leader's decision space) is as hard as solving the original bilevel problem.</abstract>
    <parentTitle language="deu">Operations Research</parentTitle>
    <enrichment key="review.accepted_by">2</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>Thomas Kleinert</author>
    <author>Martine Labbé</author>
    <author>Fränk Plein</author>
    <author>Martin Schmidt</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bilevel optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Mathematical programs with complementarity constraints (MPCC)</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bounding polyhedra</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Big-M</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Hardness</value>
    </subject>
    <collection role="institutes" number="">Friedrich-Alexander-Universität Erlangen-Nürnberg</collection>
    <collection role="subprojects" number="">A05</collection>
    <collection role="subprojects" number="">Z01</collection>
    <collection role="subprojects" number="">B08</collection>
    <collection role="institutes" number="">Universität Trier</collection>
    <file>https://opus4.kobv.de/opus4-trr154/files/264/bilevel-lp-lp-bigm-hardness_preprint.pdf</file>
  </doc>
</export-example>
