Skip to main content
SpringerLink
Log in

A Complementarity-based Partitioning and Disjunctive Cut Algorithm for Mathematical Programming Problems with Equilibrium Constraints

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

Abstract

In this paper a branch-and-bound algorithm is proposed for finding a global minimum to a Mathematical Programming Problem with Complementarity (or Equilibrium) Constraints (MPECs), which incorporates disjunctive cuts for computing lower bounds and employs a Complementarity Active-Set Algorithm for computing upper bounds. Computational results for solving MPECs associated with Bilivel Problems, NP-hard Linear Complementarity Problems, and Hinge Fitting Problems are presented to highlight the efficacy of the procedure in determining a global minimum for different classes of MPECs.

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

Access this article

Log in via an institution

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. Balas E. (1979), Disjunctive programming, Annals of Discrete Mathematics 5, 3–51

    Article  Google Scholar 

  2. Bard J., Moore J. (1990). A branch-and-bound algorithm for the bilevel linear program. SIAM Journal on Scientific and Statistical Computing 11:281–292

    Article  Google Scholar 

  3. Breiman L. (1993). Hinging hyperplanes for regression, classification and function approximation. IEEE Transactions on Information Theory 39:999–1013

    Article  Google Scholar 

  4. Calamai P. and Vicente L. (1993), Generating linear and linear-quadratic bilevel programming problems. SIAM Journal on Scientific Computing 14:770–782

    Article  Google Scholar 

  5. Calamai P. and Vicente L. (1994), Generating quadratic bilevel programming test problems. ACM Transactions on Mathematical Software 20:103–119

    Article  Google Scholar 

  6. Facchinei F., Jiang H. and Qi L. (1999), A smoothing method for mathematical programs with equilibrium constraints. Mathematical Programming 85:107–134

    Article  Google Scholar 

  7. Fletcher R., Leyffer S. and Toint P. (2002). On the global convergence of a filter-sqp algorithm. SIAM Journal on Optimization 13(1):44–59

    Article  Google Scholar 

  8. Fukushima M., Luo Z. and Pang J. (1998), A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints. Computational Optimization and Applications 10:5–34

    Article  Google Scholar 

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

    Article  Google Scholar 

  10. Jiang H. and Ralph D. (2000). Smooth sqp methods for mathematical programs with nonlinear complementarity constraints. SIAM Journal on Optimization 10(3):779–808

    Article  Google Scholar 

  11. Júdice J. and Faustino A. (1991), A computational analysis of lcp methods for bilinear and concave quadratic programming. Computers and Operations Research 18:645–654

    Article  Google Scholar 

  12. Júdice J. and Faustino A. (1992), A sequential lcp algorithm for bilevel linear programming. Annals of Operations Research 34: 89–106

    Article  Google Scholar 

  13. Júdice J., Faustino A. and Ribeiro I. (2002). On the solution of np-hard linear complementarity problems. TOP- Sociedad de Estatística e Investigacion Operativa 10(1):125–145

    Google Scholar 

  14. Júdice, J., Sherali, H., Ribeiro, I. and Faustino, A. (2005), A complementarity active-set algorithm for mathematical programming problems with equilibrium constraints, Working Paper.

  15. Júdice J. and Vicente L. (1994).On the solution and complexity of a generalized linear complementarity problem. Journal of Global Optimization 4: 415–424

    Article  Google Scholar 

  16. Luo Z., Pang J. and Ralph D. (1997). Mathematical Programs with Equilibrium Constraints. Cambridge University Press, New York

    Google Scholar 

  17. Murtagh, B. and Saunders, A. (1983), MINOS 5.0 User’s Guide, Technical Report SOL 83-20, Department of Operations Research, Stanford University.

  18. Nocedal J. and Wright S. (1999). Numerical Optimization. Springer-Verlag, New York, N.Y

    Google Scholar 

  19. Pucar P. and Sjoberg J. (1998), On the hinge finding algorithm for hinging hyperplanes. IEEE Transactions on Information Theory 44:1310–1318

    Article  Google Scholar 

  20. Queiroz M., Humes Jr C. and Júdice J. (2004). On finding global optima for the hinge fitting problem. Computers and Operations Research 31:101–122

    Article  Google Scholar 

  21. Ribeiro I. (2005). Global Optimization and Applications to Structural Engineering (in Portuguese). PhD thesis, University of Porto, Porto

    Google Scholar 

  22. Scholtes, S. (1999), Active set methods for inverse linear complementarity problems, Judge Institute of Management Research Paper Series No. 28/1999.

  23. Sherali, H. and Shetty, C. (1980), Optimization with disjunctive constraints, In: Beckman, M. and Künzi, H. (eds.), Lecture Notes in Economics and Mathematical Systems, Vol. 181, Springer-Verlag, New York, N.Y.

  24. White D. and Annandalingam G. (1993). A penalty function approach for solving bilevel linear programs. Journal of Global Optimization 3:397–419

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Matemática da Universidade de Coimbra and Instituto de Telecomunicações, Coimbra, Portugal

    Joaquim J. Júdice

  2. Grado Department of Industrial & Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, Virginia, United States

    Hanif D. Sherali

  3. Secção de Matemática do Departamento de Engenharia Civil, Faculdade de Engenharia da Universidade do Porto, Porto, Portugal

    Isabel M. Ribeiro & Ana M. Faustino

Authors
  1. Joaquim J. Júdice
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hanif D. Sherali
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Isabel M. Ribeiro
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ana M. Faustino
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joaquim J. Júdice.

Additional information

Joaquim J. Júdice: Support for this author was provided by Instituto de Telecomunicações and by FCT under grant POCTI/35059/MAT/2000.

Hanif D. Sherali: Support for this author was provided by the National Science Foundation under grant DMI-0094462.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Júdice, J.J., Sherali, H.D., Ribeiro, I.M. et al. A Complementarity-based Partitioning and Disjunctive Cut Algorithm for Mathematical Programming Problems with Equilibrium Constraints. J Glob Optim 36, 89–114 (2006). https://doi.org/10.1007/s10898-006-9001-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-006-9001-8

Keywords

Search

Navigation