lpcdd: linear programming with exact arithmetic

In rcdd: Computational Geometry

linear programming with exact arithmetic

Description

Solve linear program or explain why it has no solution.

Usage

lpcdd(hrep, objgrd, objcon, 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. May be missing, in which case, taken to be zero.
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 a linear combination of original inequalities and equalities that proves the inconsistency. Coefficients for original inequalities are nonnegative.
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. This 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.

Warning

If you want correct answers, use rational arithmetic. If you do not, this function may (1) produce approximately correct answers, (2) fail with an error, (3) give answers that are nowhere near correct with no error or warning, or (4) crash R losing all work done to that point. In large simulations (1) is most frequent, (2) occurs roughly one time in a thousand, (3) occurs roughly one time in ten thousand, and (4) has only occurred once and only with the redundant function. So the R floating point arithmetic version does mostly work, but you cannot trust its results unless you can check them independently.

See Also

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)

rcdd documentation built on April 25, 2023, 1:09 a.m.