File Exchange

image thumbnail

NOREDUND - remove redundant linear constraints or inequalities

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

3 Downloads

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)

NOTES:
(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 (2020). NOREDUND - remove redundant linear constraints or inequalities (https://www.mathworks.com/matlabcentral/fileexchange/7897-noredund-remove-redundant-linear-constraints-or-inequalities), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (8)

This was exactly what I was looking for! Thank you!!

I get the following error in MATLAB 2017a:

```
Error using fminsearch (line 105)
Argument 3 must be an options structure.

Error in noredund (line 68)
[c,f,ef] = fminsearch(@obj,c,'params',{A,b});
```

Fei

D = A ./ repmat(b,[1 size(A,2)]);
k = convhulln(D);

This part of code doesn't work.

Fei

Thomas

Yields undefined results in case of infeasibility of the constraint set - am I right with that?

Thomas

Works exactly how it should + it's fast. Thanks a lot for this contribution!

Michael Kleder

Thanks, John. I've uploaded some more descriptive comments.

John D'Errico

A minor point - nowhere in the help does it tell you the direction of the inequality constraints. They are apparently defined as A*x<=b, but I only found this from an internal comment.

Updates

1.0.0.0

Improved commenting.

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