In trying to use simplex() from the boot package, I have run into a
situation that doesn't seem like it should be possible. It is claiming
that it has solved the LP, but returns a vector of all zeros, which
does not satisfy the constraints I passed in. A small example:
> ubMatrix <- matrix(c(1,1,-1,0,-1,-1), 3, 2)
> ubVector <- c(2,1,-1)
> objective <- c(0,1)
> ubMatrix
[,1] [,2]
[1,] 1 0
[2,] 1 -1
[3,] -1 -1
> ubVector
[1] 2 1 -1
> smplx <- simplex( a = objective, A1 = ubMatrix, b1 = ubVector)
> smplx$solved
[1] 1
> smplx$soln
x1 x2
0 0
> ubMatrix %*% smplx$soln <= ubVector
[,1]
[1,] TRUE
[2,] TRUE
[3,] FALSE
The correct answer to the problem, which also has a value of 0, but
satisfies the constraints is [1, 0] :
> ubMatrix %*% c(1,0) <= ubVector
[,1]
[1,] TRUE
[2,] TRUE
[3,] TRUE
Any ideas what's going on here? Am I missing something obvious? Any
advice on how I might work around this problem would be greatly
appreciated.
Andrew
Simplex(boot) returning invalid answer
2 messages · Andrew Stoneman, Duncan Murdoch
2 days later
On Fri, 11 Mar 2005 09:09:15 -0800, Andrew Stoneman <stoneman at otsys.com> wrote :
In trying to use simplex() from the boot package, I have run into a situation that doesn't seem like it should be possible. It is claiming that it has solved the LP, but returns a vector of all zeros, which does not satisfy the constraints I passed in. A small example:
ubMatrix <- matrix(c(1,1,-1,0,-1,-1), 3, 2) ubVector <- c(2,1,-1) objective <- c(0,1)
ubMatrix
[,1] [,2] [1,] 1 0 [2,] 1 -1 [3,] -1 -1
ubVector
[1] 2 1 -1
smplx <- simplex( a = objective, A1 = ubMatrix, b1 = ubVector)
You missed this in the help page:
b1: A vector of length 'm1' giving the right hand side of the
"<=" constraints. This argument is required if 'A1' is given
and ignored otherwise. All values in 'b1' must be
non-negative.
The reason for this requirement is that the origin should be a feasible solution; that's where the algorithm starts. It's been a while since I looked at this stuff so I forget if there's an easier transformation, but one way to solve the problem you're interested in (-x-y <= -1) is to multiply through by -1 giving (x + y
= 1),
i.e. ubMatrix <- matrix(c(1,1,-1,0), 2, 2) ubVector <- c(2,1) lbMatrix <- matrix(c(1,1), 1, 2) lbVector <- 1 objective <- c(0,1) simplex(a = objective, A1 = ubMatrix, b1 = ubVector, A2 = lbMatrix, b2 = lbVector) which gives the answer you were looking for. I suppose you might suggest to the maintainer to add stopifnot(all(c(b1, b2, b3) >= 0)) to the beginning of the function rather than giving a bad answer for bad input. Duncan Murdoch