Skip to main content
Log in

Links Between Linear Bilevel and Mixed 0–1 Programming Problems

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

We study links between the linear bilevel and linear mixed 0–1 programming problems. A new reformulation of the linear mixed 0–1 programming problem into a linear bilevel programming one, which does not require the introduction of a large finite constant, is presented. We show that solving a linear mixed 0–1 problem by a classical branch-and-bound algorithm is equivalent in a strong sense to solving its bilevel reformulation by a bilevel branch-and-bound algorithm. The mixed 0–1 algorithm is embedded in the bilevel algorithm through the aforementioned reformulation; i.e., when applied to any mixed 0–1 instance and its bilevel reformulation, they generate sequences of subproblems which are identical via the reformulation.

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

Access this article

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Vicente, L. N., Savard, G., and JÚdice, J. J., Discrete Linear Bilevel Programming Problem, Journal of Optimization Theory and Application, Vol. 89, pp. 597–614, 1996.

    Google Scholar 

  2. Fortuny-Amat, J., and Mc Carl, B., A Representation and Economic Interpretation of a Two-Level Programming Problem, Journal of the Operational Research Society, Vol. 32, pp. 783–792, 1981

    Google Scholar 

  3. JÚdice, J. J., and Mitra, G., Reformulations of Mathematical Programming Problems as Linear Complementary Problems and Investigation of Their Solution Methods, Journal of Optimization Theory and Applications, Vol. 57, pp. 123–149, 1988.

    Google Scholar 

  4. Hansen, P., Jaumard, B., and Savard, G., New Branch-and-Bound Rules for Linear Bilevel Programming, SIAM Journal on Scientific and Statistical Computing, Vol. 13, pp. 1194–1217, 1992.

    Google Scholar 

  5. JÚdice, J. J., and Faustino, A. M., A Sequential LCP Method for Bilevel Linear Programming, Annals of Operations Research, Vol. 34, pp. 89–106, 1992.

    Google Scholar 

  6. Bard, J. F., and Moore, J. T., A Branch-and-Bound Algorithm for the Bilevel Linear Programming Problem, SIAM Journal on Scientific and Statistical Computing, Vol. 11, pp. 281–292, 1990.

    Google Scholar 

  7. Beale, E. M. L., and Small, R. E., Mixed Integer Programming by a Branch-and-Bound Technique, Proceedings of the 3rd IFIP Congress 1965, Vol. 2, pp. 450–451, 1965.

    Google Scholar 

  8. Ben-Ayed, O., Bilevel Linear Programming, Computers and Operations Research, Vol. 20, pp. 485–501, 1993.

    Google Scholar 

  9. Vicente, L. N., and Calamai, P. H., Bilevel and Multilevel Programming: A Bibliography Review, Journal of Global Optimization, Vol. 5, pp. 291–306, 1994.

    Google Scholar 

  10. Falk, J. E., A Linear Max-Min Problem, Mathematical Programming, Vol. 5, pp. 169–188, 1973.

    Google Scholar 

  11. Audet, C., Jaumard, B., and Savard, G., Concavity Cuts for the Linear Maxmin Problem, Report G-94-52, Les Cahiers du GERAD, 1994.

  12. Jeroslow, R. G., The Polynomial Hierarchy and a Simple Model for Competitive Analysis, Mathematical Programming, Vol. 32, pp. 146–164, 1985.

    Google Scholar 

  13. Ben-Ayed, O., and Blair, C. E., Computational Difficulties of Bilevel Linear Programming, Operations Research, Vol. 38, pp. 556–559, 1990

    Google Scholar 

  14. Bard, J. F., Some Properties of the Bilevel Programming Problem, Journal of Optimization Theory and Applications, Vol. 68, pp. 371–378, 1991.

    Google Scholar 

  15. Bialas, W., and Karwan, M., On Two-Level Optimization, IEEE Transactions on Automatic Control, Vol. 27, pp. 211–214, 1982.

    Google Scholar 

  16. Candler, W., and Townsley, R., A Linear Two-Level Linear Programming Problem, Computers and Operations Research, Vol. 9, pp. 59–76, 1982.

    Google Scholar 

  17. Benson, H. P., On the Structure and Properties of a Linear Multilevel Programming Problem, Journal of Optimization Theory and Applications, Vol. 60, pp. 353–373, 1989.

    Google Scholar 

  18. Savard, G., Contributions à la Programmation Mathématique à Deux Niveaux, Thèse de Doctorat, École Polytechnique de Montréal, 1989.

  19. Wen, U. P., and Yang, Y. H., Algorithms for Solving the Mixed Integer Two-Level Linear Programming Problem, Computers and Operations Research, Vol. 17, pp. 133–142, 1990.

    Google Scholar 

  20. Audet, C., Hansen, P., Jaumard, B., and Savard, G., Links between the Linear Bilevel and Mixed 0–1 Programming Problems, Report G-95-20, Les Cahiers du GERAD, 1995.

  21. Garey, M. R., and Johnson, D. S., Computers and Intractability, W. H. Freeman and Company, New York, New York, 1979.

    Google Scholar 

  22. Balas, E., Ceria, S., and CornuÉjols, G., A Lift-and-Project Cutting Plane Algorithm for Mixed 0–1 Programs, Mathematical Programming, Vol. 58, pp. 295–324, 1993.

    Google Scholar 

  23. LovÁsz, L., and Schrijver, A., Cones of Matrices and Set-Functions and 0–1 Optimization, SIAM Journal on Optimization, Vol. 1, pp. 166–190, 1991.

    Google Scholar 

  24. Sherali, H. D., and Adams, W. P., A Hierarchy of Relations between the Continuous and Convex Hull Representations for Zero–One Programming Problems, SIAM Journal on Discrete Mathematics, Vol. 3, pp. 411–430, 1990.

    Google Scholar 

  25. Bard, J. F., An Investigation of the Linear Three-Level Programming Problem, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 14, pp. 711–717, 1984.

    Google Scholar 

  26. Wen, U., and Bialas, W., The Hybrid Algorithm for Solving the Three-Level Linear Programming Problem, Computers and Operations Research, Vol. 13, pp. 367–377, 1986.

    Google Scholar 

  27. Blair, C. E., The Computational Complexity of Multi-Level Linear Programs, Annals of Operations Research, Vol. 34, pp. 13–19, 1992.

    Google Scholar 

  28. Bard, J. F., and Falk, J., An Explicit Solution to the Multi-Level Programming Problem, Computers and Operations Research, Vol. 9, pp. 77–100, 1982.

    Google Scholar 

  29. Tomlin, J. A., An Improved Branch-and-Bound Method for Integer Programming, Operations Research, Vol. 19, pp. 1070–1075, 1971.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Audet, C., Hansen, P., Jaumard, B. et al. Links Between Linear Bilevel and Mixed 0–1 Programming Problems. Journal of Optimization Theory and Applications 93, 273–300 (1997). https://doi.org/10.1023/A:1022645805569

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1022645805569

Navigation