Scarf’s generalization of linear complementarity problem revisited

In this paper, we revisit Scarf’s generalization of the linear complementarity problem, formulate this as a vertical linear complementarity problem and obtain some new results on this generalization. Also, a neural network model for solving Scarf’s generalized complementarity problems is proposed. Numerical simulation results show that the proposed model is feasible and efficient. | Yugoslav Journal of Operations Research 23 (2013) Number 2, 143-161 DOI: SCARF’S GENERALIZATION OF LINEAR COMPLEMENTARITY PROBLEM REVISITED Samir Kumar NEOGY Indian Statistical Institute 7, . Sansanwal Marg New Delhi-110016, India skn@ Sagnik SINHA Jadavpur University Kolkata-700032, India sagnik62@ Arup Kumar DAS Indian Statistical Institute 203, B. T. Road Kolkata-700108, India akdas@ Abhijit GUPTA Indian Statistical Institute 203, B. T. Road Kolkata-700108, India agupta@ Received: February 2013/ Accepted: June 2013 Abstract: In this paper, we revisit Scarf’s generalization of the linear complementarity problem, formulate this as a vertical linear complementarity problem and obtain some new results on this generalization. Also, a neural network model for solving Scarf’s generalized complementarity problems is proposed. Numerical simulation results show that the proposed model is feasible and efficient. Keywords: Scarf’s complementarity problem, Vertical linear complementarity problem, CottleDantzig’s algorithm, Lemke’s algorithm, Neural network approach. MSC: 90C33, 92B20. 144 S. K. Neogy, S. Sinha, A. K. Das and A. Gupta / Scarf’s Generalization 1. INTRODUCTION Given a matrix M ∈ R n× n and a vector q ∈ R n , the linear complementarity problem denoted by LCP (q, M ) , is to find w ∈ R n and z ∈ R n such that w − Mz = q, w ≥ 0, z ≥ 0 () wt z = 0 . () LCP is normally identified as a problem of mathematical programming and provides a unifying framework for several optimization problems. For recent books on this problem and applications see Cottle, Pang and Stone [3] and the references cited therein. Scarf [23] introduced a generalization of the linear complementarity problem to accomodate more complicated real life problems as well as to diversify the field of applications. In this paper, we consider a generalization by Scarf, known as Scarf’s generalized linear .