lpcdd {rcdd}R Documentation

linear programming with exact arithmetic


Solve linear program or explain why it has no solution.


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


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.


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)


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.

See Also

scdd, ArithmeticGMP, ConvertGMP


# 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]