On the Problem of Detecting Superfluous and Inconsistent Linear Constraints

摘要

The report presents some recent results of an investigation aimed at developing efficient techniques for detecting and removing inconsistent and superfluous linear constraints. The presence of inconsistent or superfluous linear constraints in a linear programming problem may be the result of insufficient care in formulating the problem or of employing some automatic method of generating the constraints. The report describes two methods for detecting and removing such constraints. Method I is restricted to situations in which a linear constraint is made superfluous or inconsistent by a second linear constraint, or those in which the linear constraint is superfluous or inconsistent by itself. Method II can be used in situations where a linear constraint is made superfluous by a set of one or more linear constraints. The advantages and disadvantages of each of these methods are discussed. (Author)