NOREDUND - remove redundant linear constraints or inequalities

version (1.35 KB) by Michael Kleder
Remove redundant inequalities from a set of inequalities ...


Updated 17 Feb 2006

No License

NOREDUND - Remove redundant linear inequalities from a set of inequalities; i.e., remove redundant linear constraints defining a feasible region. Note that the feasible region satisfies A*x <= b, where A is a fixed matrix, b is a fixed vector, and x is the vector of coordinates in your space; i.e., all values of x (or equivalently, all ordered n-tuples of coordinate numbers) which satisfy the inequality A*x <= b are inside the feasible region (or on its boundary). Removing redundant constraints means removing rows of A and the corresponding entries in b which are not necessary, which then leaves a new inequality An*x <= bn. Since the number of columns in A and An is the same (equal to the number of rows in x, or equivalently to the dimensionality of your space), the dimensionality of the problem is unchanged. Rather, the redundant constraints are simply removed.

[An,bn] = noredund(A,b)

For n variables:
A = m x n matrix, where m >= n (m constraints)
b = m x 1 vector (m constraints)
An = mm x n matrix, where mm >= n (mm nonredundant constraints)
bn = mm x 1 vector (mm nonredundant constraints)

(1) Unbounded feasible regions are permitted.
(2) This program requires that the feasible region have some finite extent in all dimensions. For example, the feasible region cannot be a line segment in 2-D space, or a plane in 3-D space.
(3) At least two dimensions are required.
(4) See function CON2VERT which is limited to bounded feasible regions but also outputs vertices for the region.
(5) Written by Michael Kleder, June 2005. Minor update, Feb 2006.

Cite As

Michael Kleder (2022). NOREDUND - remove redundant linear constraints or inequalities (, MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R14SP3
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!