Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Mixed-integer bilevel representability

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We study the representability of sets by extended formulations using mixed-integer bilevel programs. We show that feasible regions modeled by continuous bilevel constraints (with no integer variables), complementarity constraints, and polyhedral reverse convex constraints are all finite unions of polyhedra. Conversely, any finite union of polyhedra can be represented using any one of these three paradigms. We then prove that the feasible region of bilevel problems with integer variables exclusively in the upper level is a finite union of sets representable by mixed-integer programs and vice versa. Further, we prove that, up to topological closures, we do not get additional modeling power by allowing integer variables in the lower level as well. To establish the last statement, we prove that the family of sets that are finite unions of mixed-integer representable sets (up to topological closures) forms an algebra of sets; i.e., this family is closed under finite unions, intersections and complementation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. We never refer to non-rational linear transforms of rational sets, nor to rational linear transforms of sets in a family \({\mathcal {T}}\) that are not rational. Accordingly, we do not introduce any notation for these contingencies.

  2. The definition in [5] used \(\left\lceil \cdot \right\rceil \) as opposed to \(\left\lfloor \cdot \right\rfloor \). We make this change in this paper to be consistent with Jeroslow and Blair’s notation.

  3. The “order” of a Chvátal function’s representation is called its “ceiling count” in [5].

References

  1. Audet, C., Haddad, J., Savard, G.: Disjunctive cuts for continuous linear bilevel programming. Optim. Lett. 1(3), 259–267 (2007)

    Article  MathSciNet  Google Scholar 

  2. Audet, C., Hansen, P., Jaumard, B., Savard, G.: Links between linear bilevel and mixed 0–1 programming problems. J. Optim. Theory Appl. 93(2), 273–300 (1997)

    Article  MathSciNet  Google Scholar 

  3. Bard, J.F., Moore, J.T.: An algorithm for the discrete bilevel programming problem. Nav. Res. Logist. 39(3), 419–435 (1992)

    Article  MathSciNet  Google Scholar 

  4. Barvinok, A.: A Course in Convexity. American Mathematical Society, Providence (2002)

    Book  Google Scholar 

  5. Basu, A., Martin, K., Ryan, C.T., Wang, G.: Mixed-integer linear representability, disjunctions, and variable elimination. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 75–85. Springer (2017)

  6. Blair, C.E., Jeroslow, R.G.: The value function of a mixed integer program: I. Discrete Math. 19(2), 121–138 (1977)

    Article  MathSciNet  Google Scholar 

  7. Blair, C.E., Jeroslow, R.G.: The value function of a mixed integer program: II. Discrete Math. 25(1), 7–19 (1979)

    Article  MathSciNet  Google Scholar 

  8. Blair, C.: A closed-form representation of mixed-integer program value functions. Math. Program. 71(2), 127–136 (1995)

    Article  MathSciNet  Google Scholar 

  9. Blair, C.E., Jeroslow, R.G.: The value function of an integer program. Math. Program. 23(1), 237–273 (1982)

    Article  MathSciNet  Google Scholar 

  10. Candler, W., Townsley, R.: A linear two-level programming problem. Comput. Oper. Res. 9(1), 59–76 (1982)

    Article  MathSciNet  Google Scholar 

  11. Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2), 823–838 (2014)

    Article  MathSciNet  Google Scholar 

  12. Caramia, M., Mari, R.: Enhanced exact algorithms for discrete bilevel linear problems. Optim. Lett. 9(7), 1447–1468 (2015)

    Article  MathSciNet  Google Scholar 

  13. Conforti, M., Cornuéjols, G., Zambelli, G.: Integer Programming. Springer, Berlin (2014)

    MATH  Google Scholar 

  14. Cottle, R., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. SIAM, Philadelphia (2009)

    Book  Google Scholar 

  15. Dempe, S., Kue, F.M.: Solving discrete linear bilevel optimization problems using the optimal value reformulation. J. Glob. Optim. 68(2), 255–277 (2017)

    Article  MathSciNet  Google Scholar 

  16. Deng, X.: Complexity issues in bilevel linear programming. In: Migdalas, A., Pardalos, P., Värbrand, P. (eds.) Multilevel Optimization: Algorithms and Applications, pp. 149–164. Springer, New York (1998)

    Chapter  Google Scholar 

  17. Dey, S., Morán, S.D.A.: Some properties of convex hulls of integer points contained in general convex sets. Math. Program. 141((1–2)), 507–526 (2013)

    Article  MathSciNet  Google Scholar 

  18. Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: A new general-purpose algorithm for mixed-integer bilevel linear programs. Oper. Res. 65(6), 1615–1637 (2017)

    Article  MathSciNet  Google Scholar 

  19. Fischetti, M., Ljubić, I., Monaci, M., Sinnl, M.: On the use of intersection cuts for bilevel optimization. Math. Program. (Ser. B) 172, 77–103 (2017)

    Article  MathSciNet  Google Scholar 

  20. Jeroslow, R.G., Lowe, J.K.: Modelling with integer variables. In: Korte, B., Ritter, K. (eds.) Mathematical Programming at Oberwolfach II, pp. 167–184. Springer, Berlin (1984)

    Chapter  Google Scholar 

  21. Jeroslow, R.G.: Some basis theorems for integral monoids. Math. Oper. Res. 3(2), 145–154 (1978)

    Article  MathSciNet  Google Scholar 

  22. Jeroslow, R.G.: The polynomial hierarchy and a simple model for competitive analysis. Math. Program. 32(2), 146–164 (1985)

    Article  MathSciNet  Google Scholar 

  23. Köppe, M., Queyranne, M., Ryan, C.T.: Parametric integer programming algorithm for bilevel mixed integer programs. J. Optim. Theory Appl. 146(1), 137–150 (2010)

    Article  MathSciNet  Google Scholar 

  24. Lodi, A., Ralphs, T.K., Woeginger, G.J.: Bilevel programming and the separation problem. Math. Program. 146((1–2)), 437–458 (2014)

    Article  MathSciNet  Google Scholar 

  25. Lozano, L., Smith, J.C.: A value-function-based exact approach for the bilevel mixed-integer programming problem. Oper. Res. 65(3), 768–786 (2017)

    Article  MathSciNet  Google Scholar 

  26. Lubin, M., Yamangil, E., Bent, R., Vielma, J.P.: Extended formulations in mixed-integer convex programming. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 102–113. Springer (2016)

  27. Lubin, M., Zadik, I., Vielma, J.P.: Mixed-integer convex representability. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 392–404. Springer (2017)

  28. Lubin, M., Zadik, I., Vielma, J.P.: Regularity in mixed-integer convex representability (2017). arXiv preprint arXiv:1706.05135

  29. Mirrlees, J.A.: The theory of moral hazard and unobservable behaviour: part I. Rev. Econ. Stud. 66(1), 3–21 (1999)

    Article  Google Scholar 

  30. Moore, J.T., Bard, J.F.: The mixed integer linear bilevel programming problem. Oper. Res. 38(5), 911–921 (1990)

    Article  MathSciNet  Google Scholar 

  31. Tyrrell Rockafellar, R.: Convex Analysis. Princeton University Press, Princeton (1970)

    Book  Google Scholar 

  32. Sankaranarayanan, S.: Optimization with mixed-integer, complementarity, and bilevel constraints with applications to energy and food markets. Ph.D. Thesis, Johns Hopkins University (2018)

  33. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, Hoboken (1998)

    MATH  Google Scholar 

  34. Tahernejad, S., Ralphs, T.K., DeNegre, S.T.: A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation. Technical Report 16T-015-R3, Lehigh University (2016)

  35. Tavaslioglu, O., Prokopyev, O.A., Schaefer, A.J.: Solving stochastic and bilevel mixed-integer programs via a generalized value function. Optimization Online preprint (2018)

  36. Vicente, L., Savard, G., Judice, J.: Discrete linear bilevel programming problem. J. Optim. Theory Appl. 89(3), 597–614 (1996)

    Article  MathSciNet  Google Scholar 

  37. Vielma, J.P.: Mixed integer linear programming formulation techniques. SIAM Rev. 57(1), 3–57 (2015)

    Article  MathSciNet  Google Scholar 

  38. Wang, L., Pan, X.: The watermelon algorithm for the bilevel integer linear programming problem. SIAM J. Optim. 27(3), 1403–1430 (2017)

    Article  MathSciNet  Google Scholar 

  39. Ye, J.J., Zhu, D.: New necessary optimality conditions for bilevel programs by combining the MPEC and value function approaches. SIAM J. Optim. 20(4), 1885–1905 (2010)

    Article  MathSciNet  Google Scholar 

  40. Yue, D., Gao, J., Zeng, B., You, F.: A projection-based reformulation and decomposition algorithm for global optimization of a class of mixed integer bilevel linear programs. J. Glob. Optim. 73(1), 27–57 (2019)

    Article  MathSciNet  Google Scholar 

  41. Zhang, J., Ozaltın, O.Y.: A branch-and-cut algorithm for discrete bilevel linear programs. Optimization Online preprint (2017)

Download references

Acknowledgements

The authors are immensely grateful to the Associate Editor and 3 reviewers for their insightful and meticulous comments. The notational suggestions from the AE and several other valuable suggestions from the AE and the reviewers went a long way in improving the readability of the paper. The first and third authors were supported by NSF Grant CMMI1452820 and ONR Grant N000141812096. The second author thanks the University of Chicago Booth School of Business for its generous financial support.

Author information

Authors and Affiliations

  1. Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, USA

    Amitabh Basu

  2. Booth School of Business, University of Chicago, Chicago, USA

    Christopher Thomas Ryan

  3. Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montreal, Canada

    Sriram Sankaranarayanan

Authors
  1. Amitabh Basu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christopher Thomas Ryan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sriram Sankaranarayanan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sriram Sankaranarayanan.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 226 KB)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Basu, A., Ryan, C.T. & Sankaranarayanan, S. Mixed-integer bilevel representability. Math. Program. 185, 163–197 (2021). https://doi.org/10.1007/s10107-019-01424-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-019-01424-w

Keywords

Mathematics Subject Classification

Search

Navigation