Skip to main content
Log in

A hybrid Tabu-ascent algorithm for the linear Bilevel Programming Problem

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The linear Bilevel Programming Problem (BLP) is an instance of a linear hierarchical decision process where the lower level constraint set is dependent on decisions taken at the upper level. In this paper we propose to solve this NP-hard problem using an adaptive search method related to the Tabu Search metaheuristic. Numerical results on large scale linear BLPs are presented.

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. Anandalingam, G. and White, D.J., A solution method for the linear static Stackelberg problem using penalty functions, IEEE Transactions on Automatic Control, 35 (1990), pp. 1170–1173.

    Google Scholar 

  2. Bard, J.F. and Falk, J.E., An explicit solution to the multi-level programming problem, Computers and Operations Research, 9 (1982), pp. 77–100.

    Google Scholar 

  3. Bard, J. F., An efficient point algorithm for linear two-stage optimization problem, Operations Research, 31 (1983), pp. 670–684.

    Google Scholar 

  4. Bard, J. F. and Moore, J.T., A branch and bound algorithm for the bilevel programming problem, SIAM Journal on Scientific and Statistical Computing, 11(2) (1990), pp. 281–292.

    Google Scholar 

  5. Bialas, W.F. and Karwan, M.H., On two-level linear optimization, IEEE Transactions on Automatic Control, AC-27(1) (1982), pp. 211–214.

    Google Scholar 

  6. Candler, W. and Townsley, R., A linear two-level programming problem, Computers and Operations Research, 9 (1982), 59–76.

    Google Scholar 

  7. Glover, F., Tabu Search, Part I, ORSA Journal on Computing 1 (1990), pp. 190–206.

    Google Scholar 

  8. Glover, F., Tabu Search, Part II, ORSA Journal on Computing 2 (1990), pp. 4–32.

    Google Scholar 

  9. Hansen, P., The steepest ascent mildest descent heuristic for combinatorial programming, Congress on Numerical Methods in Combinatorial Optimization, Capri, 1986.

  10. Hansen, P., Jaumard, B. and Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM Journal on Scientific and Statistical Computing 13 (1992), pp. 1194–1217.

    Google Scholar 

  11. Haurie, A., Savard, G. and White, D. J., A note on: An efficient point algorithm for a linear two-stage optimization problem, Operations Research, 38 (1990), pp. 553–555.

    Google Scholar 

  12. Jeroslow, R.G., The polynomial hierarchy and a simple model for competitive analysis, Mathematical Programming, 32 (1985), pp. 146–164.

    Google Scholar 

  13. Júdice, J. and Faustino, A., A sequential LCP method for bilevel linear programming, Annals of Operations Research, 34 (1992), pp. 89–106.

    Google Scholar 

  14. Marsten, R.E., The design of the XMP linear programming library, Transactions on Mathematical Software, 7(4) (1981), pp. 481–497.

    Google Scholar 

  15. Mathieu, R., Pittard, L. and Anandalingam, G., Genetic algorithm based approach to bi-level linear programming, R.A.I.R.O. Recherche Opérationnelle, 28 (1994), pp. 1–21

    Google Scholar 

  16. Marcotte, P. and Savard, G., Novel approaches to the discrimination problem, Zeitschrift für Operations Research, 36 (1992), pp. 517–545.

    Google Scholar 

  17. Savard, G. and Gauvin, J., The steepest descent direction for the nonlinear bilevel programming Problem, Operations Research Letters, 15 (1994), pp. 265–272.

    Google Scholar 

  18. Vicente, L.N. and Calamai, P.H., Bilevel and multilevel programming: A bibliography review, forthcoming in Journal of Global Optimization.

  19. Vicente, L., Savard, G. and Júdice, J., Descent Approaches for Quadratic Bilevel Programming, Journal of Optimization Theory and Applications, 81 (1994), pp. 379–399.

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gendreau, M., Marcotte, P. & Savard, G. A hybrid Tabu-ascent algorithm for the linear Bilevel Programming Problem. J Glob Optim 8, 217–233 (1996). https://doi.org/10.1007/BF00121266

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00121266

Keywords

Navigation