{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T18:06:09Z","timestamp":1792865169086,"version":"4.5.0"},"reference-count":50,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>This paper presents a parameter-free integer-programming-based algorithm for the global resolution of a linear program with linear complementarity constraints (LPCCs). The cornerstone of the algorithm is a minimax integer program formulation that characterizes and provides certificates for the three outcomes\u2014infeasibility, unboundedness, or solvability\u2014of an LPCC. An extreme point\/ray generation scheme in the spirit of Benders decomposition is developed, from which valid inequalities in the form of satisfiability constraints are obtained. The feasibility problem of these inequalities and the carefully guided linear-programming relaxations of the LPCC are the workhorses of the algorithm, which also employs a specialized procedure for the sparsification of the satifiability cuts. We establish the finite termination of the algorithm and report computational results using the algorithm for solving randomly generated LPCCs of reasonable sizes. The results establish that the algorithm can handle infeasible, unbounded, and solvable LPCCs effectively.<\/jats:p>","DOI":"10.1137\/07068463x","type":"journal-article","created":{"date-parts":[[2008,5,12]],"date-time":"2008-05-12T09:53:13Z","timestamp":1210585993000},"page":"445-471","source":"Crossref","is-referenced-by-count":82,"title":["On the Global Solution of Linear Programs with Linear Complementarity Constraints"],"prefix":"10.1137","volume":"19","author":[{"given":"Jing","family":"Hu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John E.","family":"Mitchell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jong-Shi","family":"Pang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristin P.","family":"Bennett","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gautam","family":"Kunapuli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,5,9]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402401221"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/040606855"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0005-4"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022645805569"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-007-9263-4"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"K. Bennett, X. Ji, J. Hu, G. Kunapuli, and J.S. Pang,\n                      Model selection via bilevel programming\n                      , in Proceedings of the International Joint Conference on Neural Networks (IJCNN'06) Vancouver, B.C., Canada, IEEE Press, Piscataway, NJ, 2006.","DOI":"10.1109\/IJCNN.2006.246935"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009725216438"},{"key":"R8","unstructured":"L. Chen and D. Goldfarb,\n                      An Active-Set Method for Mathematical Programs with Linear Complementarity Constraints\n                      , SIAM J. Optim., submitted."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0286"},{"key":"R10","unstructured":"S. Dempe,\n                      Foundations of Bilevel Programming\n                      , Kluwer Academic, Dordrecht, 2002."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1080\/0233193031000149894"},{"key":"R12","unstructured":"S. Dempe, V.V. Kalashnikov, and N. Kalashnykova,\n                      Optimality conditions for bilevel programming problems\n                      , in Optimization with Multivalued Mappings: Theory, Applications and Algorithms, S. Dempe and N. Kalashnykova, eds., Springer-Verlag, New York, 2006, pp. 11\u201336."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1080\/02331930500342591"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1080\/10556780410001654241"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402407382"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0098-1354(90)80020-C"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF00939667"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S105262349731577X"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. Fukushima and J.S. Pang,\n                      Convergence of a smoothing continuation method for mathematical programs with complementarity constraints\n                      , in Ill-Posed Variational Problems and Regularization Techniques, Lecture Notes in Econom. and Math. Systems 477, M. Thera and R. Tichatschke, eds., Springer-Verlag, Berlin\/Heidelberg, 1999, pp. 99\u2013110.","DOI":"10.1007\/978-3-642-45780-7_7"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499363232"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0913069"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"J.N. Hooker,\n                      Logic-Based Methods for Optimization\n                      , Wiley, New York, 2000.","DOI":"10.1002\/9781118033036"},{"key":"R23","unstructured":"J.N. Hooker,\n                      Integrated Methods for Optimization\n                      , Springer-Verlag, New York, 2006."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0375-9"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-004-5154-0"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.6.1523"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.1.353"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1137\/0316005"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497332329"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022945316191"},{"key":"R31","unstructured":"S. Joy, J.E. Mitchell, and B. Borchers,\n                      A branch-and-cut algorithm for MAX-SAT and weighted MAX-SAT\n                      , Optim. Methods Softw., to appear."},{"key":"R32","unstructured":"G. Kunapuli, K. Bennett, J. Hu, and J.S. Pang,\n                      Classification model selection via bilevel programming\n                      , Optim. Methods Softw., to appear."},{"key":"R33","doi-asserted-by":"crossref","unstructured":"G. Kunapuli, K. Bennett, J. Hu, and J.S. Pang,\n                      Bilevel Model Selection for Support Vector Machines\n                      , manuscript, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY, 2007.","DOI":"10.1090\/crmp\/045\/07"},{"key":"R34","unstructured":"L. Lasdon,\n                      Optimization Theory of Large Systems\n                      , Dover, New York, 2002."},{"key":"R35","doi-asserted-by":"crossref","unstructured":"S. Leyffer,\n                      Complementarity constraints as nonlinear equations: Theory and numerical experience\n                      , in Optimization and Multivalued Mappings, S. Dempe and V. Kalashnikov, eds., Springer-Verlag, New York, 2006, pp. 169\u2013208.","DOI":"10.1007\/0-387-34221-4_9"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1137\/040621065"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"Z.Q. Luo, J.S. Pang, and D. Ralph,\n                      Mathematical Programs with Equilibrium Constraints\n                      , Cambridge University Press, Cambridge, 1996.","DOI":"10.1017\/CBO9780511983658"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.3.627"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"J. Outrata, M. Ko\u00e7vara, and J. Zowe,\n                      Nonsmooth Approach to Optimization Problems with Equilibrium Constraints\n                      , Kluwer Academic, Dordrecht, 1998.","DOI":"10.1007\/978-1-4757-2825-5"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008656806889"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1080\/10556780410001704911"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.1287\/moor.25.1.1.15213"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623499361233"},{"key":"R44","doi-asserted-by":"crossref","unstructured":"M. Tawarmalani and N.V. Sahinidis,\n                      Convexification and Global Optimization in Continuous and Mixed Integer Nonlinear Programming\n                      , Kluwer Academic, Dordrecht, 2002.","DOI":"10.1007\/978-1-4757-3532-1"},{"key":"R45","doi-asserted-by":"crossref","unstructured":"V. Visweswaran, C.A. Floudas, M.G. Ierapetritou, and E.N. Pistikopoulos,\n                      A decomposition based global optimization approach for solving bilevel linear and nonlinear quadratic programs\n                      , in State of the Art in Global Optimization: Computational Methods and Applications, Nonconvex Optim. Appl. 7, C.A. Floudas and P.M. Pardalos, eds., Kluwer Academic, Dordrecht, 1996, pp. 139\u2013162.","DOI":"10.1007\/978-1-4613-3437-8_10"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623497321882"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1137\/S105262349834847X"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2004.10.032"},{"key":"R49","unstructured":"http:\/\/www-neos.mcs.anl.gov\/neos\/solvers\/index.html."},{"key":"R50","unstructured":"http:\/\/www.rpi.edu\/~mitchj\/generators\/lpcc\/."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/07068463x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:19:57Z","timestamp":1787332797000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/07068463x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/07068463x"],"URL":"https:\/\/doi.org\/10.1137\/07068463x","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}