Variable elimination in linear constraints

Chandru, V. (1993) Variable elimination in linear constraints Computer Journal, 36 (5). pp. 463-472. ISSN 0010-4620

Full text not available from this repository.

Official URL:

Related URL:


Gauss and Fourier have together provided us with the essential techniques for symbolic computation with linear arithmetic constraints over the reals and the rationals. These variable elimination techniques for linear constraints have particular significance in the context of constraint logic programming languages that have been developed in recent years. Variable elimination in linear equations (Guassian Elimination) is a fundamental technique in computational linear algebra and is therefore quite familiar to most of us. Elimination in linear inequalities (Fourier Elimination), on the other hand, is intimately related to polyhedral theory and aspects of linear programming that are not quite as familiar. In addition, the high complexity of elimination in inequalities has forces the consideration of intricate specializations of Fourier's original method. The intent of this survey article is to acquaint the reader with these connections and developments. The latter part of the article dwells on the thesis that variable elimination in linear constraints over the reals extends quite naturally to constraints in certain discrete domains.

Item Type:Article
Source:Copyright of this article belongs to Oxford University Press.
ID Code:5467
Deposited On:19 Oct 2010 12:12
Last Modified:28 May 2011 07:13

Repository Staff Only: item control page