Skip to main content
SpringerLink
Log in

Algorithms for linear programming with linear complementarity constraints

  • Invited Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

Linear programming with linear complementarity constraints (LPLCC) is an area of active research in Optimization, due to its many applications, algorithms, and theoretical existence results. In this paper, a number of formulations for important nonconvex optimization problems are first reviewed. The most relevant algorithms for computing a complementary feasible solution, a stationary point, and a global minimum for the LPLCC are also surveyed, together with some comments about their efficiency and efficacy in practice.

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

  • Al-Khayyal F (1987) An implicit enumeration procedure for the general linear complementarity problem. Math Program Stud 31:1–20

    Article  Google Scholar 

  • Anitescu M (2005) On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J Optim 15:1203–1236

    Article  Google Scholar 

  • Anitescu M, Tseng P, Wright SJ (2007) Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties. Math Program 110:337–371

    Article  Google Scholar 

  • Audet C, Hansen P, Jaumard B, Savard G (1999) A symmetrical linear maxmin approach to disjoint bilinear programming. Math Program 85:573–592

    Article  Google Scholar 

  • Audet C, Savard G, Zghal W (2007) New branch-and-cut algorithm for bilevel linear programming. J Optim Theory Appl 134:353–370

    Article  Google Scholar 

  • Bard J (1999) Practical bilevel optimization: algorithms and applications. Kluwer Academic, Dordrecht

    Google Scholar 

  • Bard J, Moore J (1990) A branch and bound algorithm for the bilevel programming problem. SIAM J Sci Stat Comput 11:281–292

    Article  Google Scholar 

  • Bazaraa M, Sherali H, Shetty C (2006) Nonlinear programming: theory and algorithms, 3rd edn. Wiley, New York

    Book  Google Scholar 

  • Benson H, Sen A, Shanno D, Vanderbei R (2005) Interior-point algorithms, penalty methods and equilibrium problems. Comput Optim Appl 34:155–182

    Article  Google Scholar 

  • Burer S, Vandenbussche D (2008) A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math Program, Ser A 113:259–282

    Article  Google Scholar 

  • Colson B, Marcotte P, Savard G (2005) Bilevel programming: a survey. 4OR 3:87–107

    Article  Google Scholar 

  • Cottle R, Pang J-S, Stone R (1992) The linear complementarity problem. Academic Press, New York

    Google Scholar 

  • de Sabóia CHM, Campêlo M, Scheimberg S (2004) A computational study of global algorithms for linear bilevel programming. Numer Algorithms 35:155–173

    Article  Google Scholar 

  • Dempe S (2002) Foundations of bilevel programming. Kluwer Academic, Dordrecht

    Google Scholar 

  • Dirkse S, Ferris M, Meeraus A (2005) Mathematical programs with equilibrium constraints: automatic reformulation and solution via constrained optimization. In: Kehoe T, Srinivasan T, Whalley J (eds) Frontiers in applied general equilibrium modeling. Cambridge University Press, Cambridge, pp 67–93

    Google Scholar 

  • Facchinei F, Jiang H, Qi L (1999) A smoothing method for mathematical programs with equilibrium constraints. Math Program 85:107–134

    Article  Google Scholar 

  • Fang HR, Leyffer S, Munson T (2009) A pivoting algorithm for linear programming with linear complementarity constraints. Optim Methods Softw (to appear). http://www.mcs.anl.gov/uploads/cels/papers/P1680.pdf

  • Fernandes L, Friedlander A, Guedes MC, Júdice J (2001) Solution of a general linear complementarity problem using smooth optimization and its application to bilinear programming and LCP. Appl Math Optim 43:1–19

    Article  Google Scholar 

  • Fletcher R, Leyffer S (2004) Solving mathematical programs with complementarity constraints as nonlinear programs. Optim Methods Softw 19:15–40

    Article  Google Scholar 

  • Fletcher R, Leyffer S, Ralph D, Scholtes S (2006) Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J Optim 17:259–286

    Article  Google Scholar 

  • Fukushima M, Tseng P (2002) An implementable active-set algorithm for computing a B-stationary point of the mathematical program with linear complementarity constraints. SIAM J Optim 12:724–739

    Article  Google Scholar 

  • Fukushima M, Luo Z-Q, Pang J-S (1998) A globally convergent sequential quadratic programming algorithm for mathematical programs with linear complementarity constraints. Comput Optim Appl 10:5–34

    Article  Google Scholar 

  • Gill P, Murray W, Wright M (1981) Practical optimization. Academic Press, London

    Google Scholar 

  • Gümüz ZH, Floudas CA (2005) Global optimization of mixed-integer bilevel programming problems. Comput Manag Sci 2:181–212

    Article  Google Scholar 

  • Hansen P, Jaumard B, Savard G (1992) New branch-and-bound rules for linear bilevel programming. SIAM J Sci Stat Comput 13:1194–1217

    Article  Google Scholar 

  • Hu XM, Ralph D (2004) Convergence of a penalty method for mathematical programming with complementarity constraints. J Optim Theory Appl 123:365–390

    Article  Google Scholar 

  • Hu J, Mitchell JE, Pang J-S, Bennett KP, Kunapuli G (2008) On the global solution of linear programs with linear complementarity constraints. SIAM J Optim 19:445–471

    Article  Google Scholar 

  • Hu J, Mitchell J, Pang J-S (2010) An LPCC approach to nonconvex quadratic programs. Math. Program. (to appear). doi:10.1007/s10107-010-0426-y

  • Ibaraki T (1971) Complementary programming. Oper Res 19:1523–1529

    Article  Google Scholar 

  • Jeroslow RG (1978) Cutting-planes for complementarity constraints. SIAM J Control Optim 16:56–62

    Article  Google Scholar 

  • Jiang H, Ralph D (1999) Smooth SQP methods for mathematical programs with nonlinear complementarity constraints. SIAM J Optim 10:779–808

    Article  Google Scholar 

  • Jiang H, Ralph D (2003) Extension of quasi-Newton methods to mathematical programs with complementarity constraints Comput Optim Appl 25:123–150

    Article  Google Scholar 

  • Júdice J, Faustino A (1988) An experimental investigation of enumerative methods for the linear complementarity problem. Comput Oper Res 15:417–426

    Article  Google Scholar 

  • Júdice J, Faustino A (1991) A computational analysis of LCP methods for bilinear and concave quadratic programming. Comput Oper Res 18:645–654

    Article  Google Scholar 

  • Júdice J, Faustino A (1992) A SLCP method for bilevel linear programming. Ann Oper Res 34:89–106

    Article  Google Scholar 

  • Júdice J, Faustino A (1994) The linear-quadratic bilevel programming problem. Inf Syst Oper Res 32:87–98

    Google Scholar 

  • Júdice JJ, Vicente LN (1994) On the solution and complexity of a generalized linear complementarity problem. J Glob Optim 4:415–424

    Article  Google Scholar 

  • Júdice J, Sherali H, Ribeiro I, Faustino A (2006) A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints. J Glob Optim 136:89–114

    Article  Google Scholar 

  • Júdice J, Sherali H, Ribeiro I, Faustino A (2007) A complementarity active-set algorithm for mathematical programming problems with equilibrium constraints. J Optim Theory Appl 136:467–481

    Article  Google Scholar 

  • Konno H (1971) Bilinear programming: Part II—applications of bilinear programming. Technical Report, Department of Operations Research, Stanford University

  • Le Thi H, Pham Dinh T (2005) The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann Oper Res 133:23–46

    Article  Google Scholar 

  • Le Thi H, Pham Dinh T (2011) On solving linear complementarity problems by DC programming and DCA. Comput Optim Appl (to appear). doi:10.1007/s10589-011-9398-y

  • Leyffer S, López-calva G, Nocedal J (2004) Interior methods for mathematical programs with complementarity constraints. SIAM J Optim 17:52–77

    Article  Google Scholar 

  • Luo Z, Pang J-S, Ralph D (1997) Mathematical programs with equilibrium constraints. Cambridge University Press, New York

    Google Scholar 

  • Mangasarian OL (1995) The linear complementarity problem as a separable bilinear program. J Glob Optim 6:153–161

    Article  Google Scholar 

  • Mangasarian OL (2007) Absolute value programming. Comput Optim Appl 36:43–53

    Article  Google Scholar 

  • Murtagh B, Saunders A (1983) MINOS 5.0 user’s guide. Technical Report SOL 83-20, Department of Operations Research, Stanford University

  • Murty K (1976) Linear and combinatorial programming. Wiley, New York

    Google Scholar 

  • Murty K (1988) Linear complementarity, linear and nonlinear programming. Heldermann, Berlin

    Google Scholar 

  • Nocedal J, Wright SJ (2006) Numerical optimization. Springer, Berlin

    Google Scholar 

  • Outrata J, Kocvara M, Zowe J (1998) Nonsmooth approach to optimization problems with equilibrium constraints: theory, applications and numerical results. Kluwer Academic, Boston

    Google Scholar 

  • Pang J-S, Fukushima M (1999) Complementarity constraint qualifications and simplified B-stationarity conditions for mathematical programs with equilibrium constraints. Comput Optim Appl 13:111–136

    Article  Google Scholar 

  • Ralph D (2008) Nonlinear programming advances in mathematical programming with complementarity constraints. R Soc (submitted). http://www.eng.cam.ac.uk/wdr241/Papers/MPCC-review.pdf

  • Sahinidis NV, Tawarmalani M (2005) BARON 7.2.5: global optimization of mixed-integer nonlinear programs. User’s Manual

  • Scheel H, Scholtes S (2000) Mathematical programs with complementarity constraints: stationarity, optimality and sensitivity. Math Oper Res 25:1–22

    Article  Google Scholar 

  • Scholtes S (1999) Active set methods for inverse linear complementarity problems. Technical Report, Judge Institute of Management Research

  • Scholtes S (2000) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J Optim 11:918–936

    Article  Google Scholar 

  • Sherali HD, Adams WP (1999) A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Kluwer Academic, Dordrecht

    Google Scholar 

  • Sherali HD, Krishnamurthy RS, Al-Khayyal FA (1998) Enumeration approach for linear complementarity problems based on a reformulation-linearization technique. J Optim Theory Appl 99:481–507

    Article  Google Scholar 

  • Tawarmalani M, Sahinidis NV (2004) Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math Program 99:563–591

    Article  Google Scholar 

  • Vandenbussche D, Nemhauser G (2005) A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math Program, Ser A 102:559–575

    Article  Google Scholar 

  • Ye JJ (1999) Optimality conditions for optimization problems with complementarity constraints. SIAM J Optim 9:374–387

    Article  Google Scholar 

  • Ye JJ (2005) Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. J Math Anal Appl 307:350–369

    Article  Google Scholar 

  • Ye Y (1993) A fully polynomial-time approximation algorithm for computing a stationary point of the general linear complementarity problem. Math Oper Res 18:334–345

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

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

    Joaquim J. Júdice

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

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joaquim J. Júdice.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Júdice, J.J. Algorithms for linear programming with linear complementarity constraints. TOP 20, 4–25 (2012). https://doi.org/10.1007/s11750-011-0228-2

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-011-0228-2

Keywords

Mathematics Subject Classification (2000)

Search

Navigation