×

Identifying minimally infeasible subsystems of inequalities. (English) Zbl 0752.90050

Summary: Given an infeasible system of linear inequalities, we show that the problem of identifying all minimally infeasible subsystems can be reduced to the problem of finding all vertices of a related polyhedron. This results in a shorter enumeration than that performed by a previous method to solve this problem.

MSC:

90C10 Integer programming
15A39 Linear inequalities of matrices
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
Full Text: DOI