redund|minrep(1)

✨ NAME ✨

redund|minrep — bestie, this is the glow-up tool that removes redundant inequalities from an H-representation or redundant vertices (aka non-extreme points) from a V-representation. And minrep also sniffs out hidden linearities. iykyk 💅

---

🎀 SYNOPSIS 🎀

redund [input-file] [output-file]

minrep [input-file] [output-file]

mpirun -np [procs] mplrs -minrep [input-file] [output-file] [option...]

---

💖 DESCRIPTION 💖

okay so redund and minrep are literally aliases to lrs, which is part of the C library lrslib(5). You can also do all of this by calling lrs directly with the options down below. All computations are done in exact arithmetic — no floating point nonsense here, we're precise 💅. For the deets on input files, go see lrs(1). There's a parallel version of minrep too, and it's mplrs -minrep. Also the -redund option does the exact same thing and is just kept around for legacy (peep mplrs(1)).

🌸 redund

H-representation: the redundant inequalities in an input H-representation get removed and the remaining inequalities are output. Hidden linearities are NOT detected unless you include the testlin option — and if you do, the output is a minimum representation and the dimension gets reported. slay.

V-representation: it outputs all extreme points and extreme rays, which is often called the convex hull problem. The testlin option makes linearities get detected and explicitly output.

Outputs can be piped straight into lrs. redund is a link to lrs, which can also do these things via the testlin, redund and redund_list options. And heads up: mplrs -redund always sets the testlin option, so it always produces minimum representations. no cap.

🦋 minrep

Equivalent to redund with the testlin option. that's the whole vibe.

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)

bestie note: this one goes before the begin line only. and it's new in 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. (iconic behaviour honestly)

🌈 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 https://inf.ethz.ch/personal/fukudak/polyfaq/polyfaq.html
2. redund: extreme point enumeration and eliminating redundant inequalities http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html#redund
3. User's guide for lrslib http://cgm.cs.mcgill.ca/%7Eavis/C/lrslib/USERGUIDE.html

---

👑 AUTHOR 👑

David Avis <avis at cs dot mcgill dot ca > 💖

---

🌸 SEE ALSO 🌸

lrs(1), mplrs(1), lrslib(5),

---

and that's the whole page bestie ✨ this masterpiece is from January 2024, rockin' version 2024.1.10 of lrslib 7.3, and the manual itself goes by redund|minrep(1) 🫶 go remove some redundant inequalities, you got this 💅🎀