The Extended Linear Complementarity Problem

. In this paper we define the Extended Linear Complementarity Problem (ELCP), an extension of the well-known Linear Complementarity Problem (LCP). We study the general solution set of an ELCP and we present an algorithm to find all its solutions. Finally we show that the ELCP can be used to solve some important problems in the max algebra. 1 Introduction 1.1 Overview In this paper we propose the Extended Linear Complementarity Problem (ELCP), an extension of the Linear Complementarity Problem, which is one of the fundamental problems in mathematical programming. We shall present an algorithm to find all solutions of an ELCP. The core of this algorithm is formed by an adaptation of Motzkin's double description method for solving sets of linear inequalities [10]. Our algorithm yields a description of the complete solution set of an ELCP by central and extremal rays. In that way it provides a geometrical insight in the solution set of the ELCP and related problems. The formulation of th..