Variable Elimination for Disequations in Generalized Linear Constraint Systems
J.-L. Imbert · The Computer Journal · 1993
This paper is concerned with the case of generalized linear constraint systems. A generalized linear constraints systems is the conjunction of a sub-system of equations E, a sub-system of inequations I (≤), an a sub-system of disequations D (≠). We first of all establish that the variable elimination operation on a generalized linear constraint system E, I, D has, as its result, a generalized linear constraint system E′, I′, D′. We then show that E′, I′ does not depend on D, and that the disequations of D are independent from one another for the variable elimination operation. Next, we present two algorithms for variable elimination in the disequation sub-system D. The first algorithm can be easily integrated into an algorithm dealing with variable elimination in inequation systems by the Fourier elimination method. The variables are eliminated one after another. The second algorithm assumes that the projection E′, I′ is known. It is based on new properties that we establish. It globally eliminates the variables in one single operation. The numerous independencies allow for a high degree of parallelism which we take advantage of.*