lpcdd {rcdd} R Documentation

## linear programming with exact arithmetic

### Description

Solve linear program or explain why it has no solution.

### Usage

```lpcdd(hrep, objgrd, objcon = as(0, class(objgrd)), minimize = TRUE,
solver = c("DualSimplex", "CrissCross"))
```

### Arguments

 `hrep` H-representation of convex polyhedron (see details) over which an affine function is maximized or minimized. `objgrd` gradient vector of affine function. `objcon` constant term of affine function. `minimize` minimize if `TRUE`, otherwise maximize. `solver` type of solver. Use the default unless you know better.

### Details

See `cddlibman.pdf` in the `doc` directory of this package, especially Sections 1 and 2 and the documentation of the function `dd_LPSolve` in Section 4.2.

This function minimizes or maximizes an affine function `x` maps to `sum(objgrd * x) + objcon` over a convex polyhedron given by the H-representation given by the matrix `hrep`. Let

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

Then the convex polyhedron in question is the set of points `x` satisfying

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

### Value

a list containing some of the following components:

 `solution.type` character string describing the solution type. `"Optimal"` indicates the optimum is achieved. `"Inconsistent"` indicates the feasible region is empty (no points satisfy the constraints, the polyhedron specified by `hrep` is empty). `"DualInconsistent"` or `"StrucDualInconsistent"` indicates the feasible region is unbounded and the objective function is unbounded below when `minimize = TRUE` or above when `minimize = FALSE`. `primal.solution` Returned only when `solution.type = "Optimal"`, the solution to the stated (primal) problem. `dual.solution` Returned only when `solution.type = "Optimal"`, the solution to the dual problem, Lagrange multipliers for the primal problem. `dual.direction` Returned only when `solution.type = "Inconsistent"`, coefficients of the positive combination of original inequalities that proves the inconsistency. `primal.direction` Returned only when `solution.type = "DualInconsistent"` or `solution.type = "StrucDualInconsistent"`, coefficients of the linear combination of columns that proves the dual inconsistency, also an unbounded direction for the primal LP.

### Rational Arithmetic

The arguments `hrep`, `objgrd`, and `objcon` may have type `"character"` in which case their 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.

`scdd`, `ArithmeticGMP`, `ConvertGMP`

### Examples

```# first two rows are inequalities, second two equalities
hrep <- rbind(c("0", "0", "1", "1", "0", "0"),
c("0", "0", "0", "2", "0", "0"),
c("1", "3", "0", "-1", "0", "0"),
c("1", "9/2", "0", "0", "-1", "-1"))
a <- c("2", "3/5", "0", "0")
lpcdd(hrep, a)

# primal inconsistent problem
hrep <- rbind(c("0", "0", "1", "0"),
c("0", "0", "0", "1"),
c("0", "-2", "-1", "-1"))
a <- c("1", "1")
lpcdd(hrep, a)

# dual inconsistent problem
hrep <- rbind(c("0", "0", "1", "0"),
c("0", "0", "0", "1"))
a <- c("1", "1")
lpcdd(hrep, a, minimize = FALSE)
```

[Package rcdd version 1.1 Index]