Abstract
The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n 4) is observed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Y.M. Bershchanskii andM.V. Meerov, The complementarity problem: Theory and methods of solution,Automat. Remote Control 44(6) (1983) 687–710.
S.J. Chung andK.G. Murty, Polynomially bounded ellipsoid algorithm for convex quadratic programming, in:Nonlinear Programming 4: Proc. Nonlinear Symposium 4, 1980, ed.O.L. Mangasarian, R.R. Meyer andS.M. Robinson (Academic Press, New York, 1981), p. 439–485.
R.W. Cottle andG.B. Dantzig, Complementary pivot theory of mathematical programming,Linear Algebra Appl. 1 (1968) 103–125.
R.W. Cottle, Some recent developments in linear complementarity theory, in:Variational Inequalities and Complementarity problems: Theory and Applications, ed.R.W. Cottle, F. Gianessi andJ.L. Lions, (Wiley, New York, 1980) 97–104.
CRAY RESEARCH INC. A Multitasking User Guide,CRAY Computer Systems Techn. Note (1985) SN-0222.
C.E. Lemke, Bimatrix equilibrium points and mathematical programming,Management Sci. 11 (1965) 681–689.
C.E. Lemke, A survey of complementarity theory, in:Variational Inequalities and Complementarity Problems: Theory and Applications, ed.R.W. Cottle, F. Giannessi andJ.L. Lions (Wiley, New York, 1980) 213–239.
O.L. Mangasarian, Characterization of linear complementarity problems as linear programs,Math. Program. Study 7 (1978) 74–87.
B.A. Murtagh andM.A. Saunders, MINOS 5.0 User's Guide, Systems Optimization Laboratory (Department of Operations Research, Stanford University, Stanford, CA).
K.G. Murty, Note on a Bard-type scheme for solving the complementarity problem,Opsearch 11 (1974) 123–130.
K.G. Murty,Linear and Combinatorial Programming, (Wiley, New York, 1985).
P.M. Pardalos andJ.B. Rosen, Global optimization approach to the linear complementarity problem,SIAM J. Sci. Statist. Computing 9 (1988) 341–353.
J.B. Rosen, Minimum norm solution to the linear complementarity problem,Tech. Rept. VMSI 87/42, University of Minnesota Supercomputer Institute, July, 1987.
L. Van der Heyden, A variable dimension algorithm for the linear complementarity problem,Math. Program. 19 (1980) 328–346.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Phillips, A.T., Rosen, J.B. A parallel algorithm for solving the linear complementarity problem. Ann Oper Res 14, 77–104 (1988). https://doi.org/10.1007/BF02186475
Issue Date:
DOI: https://doi.org/10.1007/BF02186475