File Exchange

## NOREDUND - remove redundant linear constraints or inequalities

version 1.0.0.0 (1.35 KB) by Michael Kleder

### Michael Kleder (view profile)

Remove redundant inequalities from a set of inequalities ...

Updated 17 Feb 2006

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 .

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

Pantelis Sopasakis

### Pantelis Sopasakis (view profile)

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

### Fei (view profile)

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

This part of code doesn't work.

Fei

Thomas

### Thomas (view profile)

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

Thomas

### Thomas (view profile)

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

Michael Kleder

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.