redundant {rcdd} R Documentation

## Eliminate redundant rows of H-representation and V-representation

### Description

Eliminate redundant rows from H-representation (intersection of half spaces) or V-representation (convex hull of points and directions) of convex polytope.

### Usage

```redundant(input, representation = c("H", "V"))
```

### Arguments

 `input` either H-representation or V-representation of convex polyhedron (see details). `representation` if `"H"`, then `input` is an H-representation, otherwise a V-representation. May also be obtained from a `"representation"` attribute of `input`, if present.

### Details

See `cddlibman.pdf` in the `doc` directory of this package, especially Sections 1 and 2.

Both representations are (in R) matrices, the first two rows are special. Let `foo` be either an H-representation or a V-representation and

```      l <- foo[ , 1]
b <- foo[ , 2]
v <- foo[ , - c(1, 2)]
a <- (- v)
```

In the H-representation the convex polyhedron in question is the set of points `x` satisfying

```      axb <- a %*% x - b
all(axb <= 0)
all(l * axb == 0)
```

In the V-representation the convex polyhedron in question is the set of points `x` for which there exists a `lambda` such that

```      x <- t(lambda) %*% v
```
where `lambda` satisfies the constraints
```      all(lambda * (1 - l) >= 0)
sum(b * lambda) == max(b)
```

An H-representation or V-representation object can be checked for validity using the function `validcdd`.

### Value

a list containing some of the following components:

 `output` The input matrix with redundant rows removed. `implied.linearity` For an H-representation, row numbers of inequality constraint rows that together imply equality constraints. For a V-representation, row numbers of rays that together imply lines. `redundant` Row numbers of redundant rows. Note: this is set `redset` output by the `dd_MatrixCanonicalize` function in `cddlib`. It apparently does not consider all rows it deletes “redundant”. Redundancy can also be determined from the following component. `new.position` Integer vector of length `nrow(input)`. Says for each input row which output row it becomes or zero to indicate redundant.

### Rational Arithmetic

The input representation may have type `"character"` in which case its elements are interpreted as unlimited precision rational numbers. They consist of an optional minus sign, a string of digits of any length (the numerator), a slash, and another string of digits of any length (the denominator). The denominator must be positive. If the denominator is one, the slash and the denominator may be omitted. The `cdd` package provides several functions (see ConvertGMP and ArithmeticGMP) for conversion back and forth between R floating point numbers and rationals and for arithmetic on GMP rationals.

`ArithmeticGMP`, `ConvertGMP`, `validcdd`, `makeH`

### Examples

```hrep <- rbind(c(0, 0,  1,  1,  0),
c(0, 0, -1,  0,  0),
c(0, 0,  0, -1,  0),
c(0, 0,  0,  0, -1),
c(0, 0, -1, -1, -1))

redundant(d2q(hrep), representation = "H")

foo <- c(1, 0, -1)
hrep <- cbind(0, 1, rep(foo, each = 9), rep(foo, each = 3), foo)
print(hrep)
redundant(d2q(hrep), representation = "V")
```

[Package rcdd version 1.1 Index]