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.
Similar content being viewed by others
References
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.
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
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.
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.
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.
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.
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.
Ben-Ayed, O., Bilevel Linear Programming, Computers and Operations Research, Vol. 20, pp. 485–501, 1993.
Vicente, L. N., and Calamai, P. H., Bilevel and Multilevel Programming: A Bibliography Review, Journal of Global Optimization, Vol. 5, pp. 291–306, 1994.
Falk, J. E., A Linear Max-Min Problem, Mathematical Programming, Vol. 5, pp. 169–188, 1973.
Audet, C., Jaumard, B., and Savard, G., Concavity Cuts for the Linear Maxmin Problem, Report G-94-52, Les Cahiers du GERAD, 1994.
Jeroslow, R. G., The Polynomial Hierarchy and a Simple Model for Competitive Analysis, Mathematical Programming, Vol. 32, pp. 146–164, 1985.
Ben-Ayed, O., and Blair, C. E., Computational Difficulties of Bilevel Linear Programming, Operations Research, Vol. 38, pp. 556–559, 1990
Bard, J. F., Some Properties of the Bilevel Programming Problem, Journal of Optimization Theory and Applications, Vol. 68, pp. 371–378, 1991.
Bialas, W., and Karwan, M., On Two-Level Optimization, IEEE Transactions on Automatic Control, Vol. 27, pp. 211–214, 1982.
Candler, W., and Townsley, R., A Linear Two-Level Linear Programming Problem, Computers and Operations Research, Vol. 9, pp. 59–76, 1982.
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.
Savard, G., Contributions à la Programmation Mathématique à Deux Niveaux, Thèse de Doctorat, École Polytechnique de Montréal, 1989.
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.
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.
Garey, M. R., and Johnson, D. S., Computers and Intractability, W. H. Freeman and Company, New York, New York, 1979.
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.
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.
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.
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.
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.
Blair, C. E., The Computational Complexity of Multi-Level Linear Programs, Annals of Operations Research, Vol. 34, pp. 13–19, 1992.
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.
Tomlin, J. A., An Improved Branch-and-Bound Method for Integer Programming, Operations Research, Vol. 19, pp. 1070–1075, 1971.
Author information
Authors and Affiliations
Rights 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
Issue Date:
DOI: https://doi.org/10.1023/A:1022645805569