redund and minrep are aliases to lrs which is part of
redund
H-representation:
redundant inequalities in an input H-representation are removed and
the remaining inequalities output.
Hidden linearities
are not detected unless the testlin option is included,
in which case the output is a minimum representation
and the dimension is reported.
V-representation:
outputs all extreme points and extreme rays, often called the
convex hull problem.
The testlin option cause linearities to be detected and explicitly
output.
Outputs can be piped directly into lrs.
redund is a link to lrs which can also perform these functions via
the testlin, redund and redund_list options.
mplrs -redund always sets the testlin option, so always produces
minimum representations.
minrep
Equivalent to redund with the testlin option.
With no options minrep|redund will process the entire input file.
redund start end
Check input lines with line numbers from start to end and remove any redundant lines.
redund 0 0 will check all input lines.
redund_list k i_1 i_2 ... i_k
Check the k input line numbers with indices i_1 i_2 ... i_k
and remove any redundant lines.
testlin (before the begin line only) (new 7.3)
An LP test will be made for hidden linearities at the beginning of the run and is reported.
If there are no hidden linearities
one LP per constraint tests for redundancy. (mplrs can be run with no verification step.)
If hidden linearities exist two LPs per constraint search for hidden linearities and remove redundancies.
In both cases
the run ends with a minimum set of linearities and inequalities (ie. no hidden inequalities or duplicates)
and the dimension is reported.
(mplrs will find all linearities but some non redundant inequalities may be eliminated, so a second run is required.)
verbose
As each input line is checked a message is printed telling its status
*nr :non-redundant
*re :redundant
*sr :strongly redundant
For an H-representation strongly redundant means the feasible
region lies in its open half-space. For a V-representation it means that the point
lies in the (relative) interior of the convex hull.
In addition minrep may report
*li :linearity
(1) Remove hidden linearities and minimum representation of an H-representation.
% cat cube.ine
H-representation
begin
7 4 rational
0 1 0 0
0 0 1 0
0 0 0 1
1 -1 0 0
1 0 -1 0
1 0 0 -1
-1 0 0 1
end
verbose
% minrep cube.ine
minrep:lrslib_v.7.3_2024.1.10(64bit,lrslong.h,hybrid_arithmetic)
*Input taken from cube.ine
*hidden linearities exist
*finding minimum representation
*nr 0 1 0 0
*nr 0 0 1 0
*sr 0 0 0 1
*nr 1 -1 0 0
*nr 1 0 -1 0
*li 1 0 0 -1
*li-1 0 0 1
*linearity in row=6 removed or in cobasis, independent
*linearity in row=7 dependent, made redundant
H-representation
linearity 1 1
begin
5 4 rational
1 0 0 -1
0 1 0 0
0 0 1 0
1 -1 0 0
1 0 -1 0
end
*input had 7 rows and 4 columns
* 2 redundant row(s) found
3 7
* 1 hidden linearity found
(2) Compute the extreme points of a set of 10 points in R^3
% cat c.ext
V-representation
begin
10 4 rational
1 1 1 1
1 0 1 1
1 1/2 0 1/3
1 1 1 0
1 0 1 0
1 1 0 0
1 0 0 0
1 0 1/3 1/4
1 1 0 1
1 0 0 1
end
% redund c.ext
*redund:lrslib v.7.2 2020.6.8(64bit,lrslong.h,hybrid arithmetic)
*Input taken from c.ext
V-representation
begin
8 4 rational
1 1 1 1
1 0 1 1
1 1 1 0
1 0 1 0
1 1 0 0
1 0 0 0
1 1 0 1
1 0 0 1
end
*Input had 10 rows and 4 columns
* 2 redundant row(s) found:
3 8