linear programming with exact arithmetic
Solve linear program or explain why it has no solution.
lpcdd(hrep, objgrd, objcon, 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. 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.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 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.
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.
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.
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)