eliminate {lintools}

Eliminate a variable from a set of edit rules

Description

Eliminating a variable amounts to deriving all (non-redundant) linear (in)equations not containing that variable. Geometrically, it can be interpreted as a projection of the solution space (vectors satisfying all equations) along the eliminated variable's axis.

Usage

eliminate(
  A,
  b,
  neq = nrow(A),
  nleq = 0,
  variable,
  H = NULL,
  h = 0,
  eps = 1e-08
)

Arguments

A

[numeric] Matrix

b

[numeric] vector

neq

[numeric] The first neq rows in A and b are treated as linear equalities.

nleq

[numeric] The nleq rows after neq are treated as inequations of the form a.x<=b. All remaining rows are treated as strict inequations of the form a.x<b.

variable

[numeric|logical|character] Index in columns of A, representing the variable to eliminate.

H

[numeric] (optional) Matrix indicating how linear inequalities have been derived.

h

[numeric] (optional) number indicating how many variables have been eliminated from the original system using Fourier-Motzkin elimination.

eps

[numeric] Coefficients with absolute value <= eps are treated as zero.

Value

A list with the folowing components

• A: the A corresponding to the system with variables eliminated.

• b: the constant vector corresponding to the resulting system

• neq: the number of equations

• H: The memory matrix storing how each row was derived

• h: The number of variables eliminated from the original system.

Details

For equalities Gaussian elimination is applied. If inequalities are involved, Fourier-Motzkin elimination is used. In principle, FM-elimination can generate a large number of redundant inequations, especially when applied recursively. Redundancies can be recognized by recording how new inequations have been derived from the original set. This is stored in the H matrix when multiple variables are to be eliminated (Kohler, 1967).

References

D.A. Kohler (1967) Projections of convex polyhedral sets, Operational Research Center Report , ORC 67-29, University of California, Berkely.

H.P. Williams (1986) Fourier's method of linear programming and its dual. American Mathematical Monthly 93, pp 681-695.

Examples

# Example from Williams (1986)
A <- matrix(c(
   4, -5, -3,  1,
  -1,  1, -1,  0,
   1,  1,  2,  0,
  -1,  0,  0,  0,
   0, -1,  0,  0,
   0,  0, -1,  0),byrow=TRUE,nrow=6) 
b <- c(0,2,3,0,0,0)
L <- eliminate(A=A, b=b, neq=0, nleq=6, variable=1)