---
name: "redund"
section: "1"
platform: "linux"
package: "lrslib"
version: "0.73-2+b1"
release: "Debian 13 (Trixie)"
platforms: ["linux"]
url: "https://new.carta.tech/redund"
---

# redund(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)](/lrs/1.md)**. 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)](/mplrs/1.md)**)

*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

  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)](/lrs/1.md), [**mplrs**(1)](/mplrs/1.md), **lrslib**(5),