table of contents
redund|minrep(1) | lrslib 7.3 | redund|minrep(1) |
Name¶
redund|minrep - Remove redundant inequalities from an H-representation or redundant vertices (non-extreme points) from a V-representation. minrep also identifies hidden linearities.
Synopsis¶
redund [input-file] [output-file]
minrep [input-file] [output-file]
mpirun -np [procs] mplrs -minrep [input-file] [output-file] [option...]
Description¶
redund and minrep are aliases to lrs which is part of the C library lrslib(5). This functionality can also be performed by lrs directly by using the options described below. All computations are done in exact arithmetic. For input file descriptions see lrs(1). A parallel version of minrep is given by mplrs -minrep. The -redund option performs the same function and is retained for legacy. (see mplrs(1))
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)
redund 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. 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.
lrs If neither redund or redund_list options are present
the initial LP test is made, reported and the run halted. Otherwise as above
for redund.
mplrs This option is ignored. In redund/minrep mode a minimum
representation is always found.
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
Examples¶
(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
Notes¶
- 1.
- FAQ page
- 2.
- redund: extreme point enumeration and eliminating redundant inequalities
- 3.
- User's guide for lrslib
Author¶
David Avis <avis at cs dot mcgill dot ca >
See also¶
lrs(1), mplrs(1), lrslib(5),
2024.1.10 | January 2024 |