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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Balas E. (1979), Disjunctive programming, Annals of Discrete Mathematics 5, 3–51
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
Breiman L. (1993). Hinging hyperplanes for regression, classification and function approximation. IEEE Transactions on Information Theory 39:999–1013
Calamai P. and Vicente L. (1993), Generating linear and linear-quadratic bilevel programming problems. SIAM Journal on Scientific Computing 14:770–782
Calamai P. and Vicente L. (1994), Generating quadratic bilevel programming test problems. ACM Transactions on Mathematical Software 20:103–119
Facchinei F., Jiang H. and Qi L. (1999), A smoothing method for mathematical programs with equilibrium constraints. Mathematical Programming 85:107–134
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
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
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
Jiang H. and Ralph D. (2000). Smooth sqp methods for mathematical programs with nonlinear complementarity constraints. SIAM Journal on Optimization 10(3):779–808
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
Júdice J. and Faustino A. (1992), A sequential lcp algorithm for bilevel linear programming. Annals of Operations Research 34: 89–106
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
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.
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
Luo Z., Pang J. and Ralph D. (1997). Mathematical Programs with Equilibrium Constraints. Cambridge University Press, New York
Murtagh, B. and Saunders, A. (1983), MINOS 5.0 User’s Guide, Technical Report SOL 83-20, Department of Operations Research, Stanford University.
Nocedal J. and Wright S. (1999). Numerical Optimization. Springer-Verlag, New York, N.Y
Pucar P. and Sjoberg J. (1998), On the hinge finding algorithm for hinging hyperplanes. IEEE Transactions on Information Theory 44:1310–1318
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
Ribeiro I. (2005). Global Optimization and Applications to Structural Engineering (in Portuguese). PhD thesis, University of Porto, Porto
Scholtes, S. (1999), Active set methods for inverse linear complementarity problems, Judge Institute of Management Research Paper Series No. 28/1999.
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.
White D. and Annandalingam G. (1993). A penalty function approach for solving bilevel linear programs. Journal of Global Optimization 3:397–419
Author information
Authors and Affiliations
Corresponding author
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
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-006-9001-8