Tech Report CS-92-11

A Note on Redundant Linear Constraints

Pascal Van Hentenryck and Jean-Louis Imbert

March 1992

Abstract:

Much research on redundancy has focused on identifying syntactic properties of redundant and non-redundant constraints to avoid resorting to costly semantic methods (e.g.{} optimization). In this paper, we study the detection of redundant linear constraints using a lexicographic solved form. The lexicographic solved form is the basis of an incremental decision procedure, based on the simplex algorithm, for systems of equations, inequalities, and disequations. It enjoys the two important properties of (1) precluding syntactically the presence of implicit equalities and (2) being preserved by pivoting under a lexicographic pivoting rule. We show that the lexicographic solved form helps to identify new syntactic criteria for detectping redundant and non-redundant constraints. These criteria generalize and amplify existing results. In addition, we present a syntactic method to reduce a system of linear constraints that can be used before further applications of syntactic criteria or possibly semantic methods.

(complete text in pdf)