On 11/19/05, Adrian DUSA <[EMAIL PROTECTED]> wrote:
> On Saturday 19 November 2005 19:17, Patrick Burns wrote:
> > [....snip...] One cheat would be to do the LP problem
> > multiple times with the rows of your matrix randomly
> > permuted. Assuming you keep track of the real rows,
> > you could then get a sense of how many solutions there
> > might be.
>
> Thanks for the answer. The trick does work (i.e. it finds all minimum
> solutions) provided that I permute the rows a sufficient number of times. And
> I have to compare each solution to the existing (unique) ones, which takes a
> lot of time...
> In your experience, what would be the definiton of "multiple times" for large
> matrices?
>
> My (dumb) solution is guaranteed to find all possible minimums, because it
> checks every possible combination. For large matrices, though, this would be
> really slow. I wonder if that could be vectorized in some way; before the LP
> function, I was thinking there might be a more efficient way to loop over all
> possible columns (using perhaps the apply family).
>
> Thanks again,
> Adrian
>
Getting back to your original question of using apply, solving the LP
gives us the number of components in any minimal solution and
exhaustive search of all solutions with that many components can
be done using combinations from gtools and apply like this:
library(gtools) # needed for combinations
soln <- lp("min", rep(1,3), rbind(t(mtrx)), rep(">=", 4), rep(1,4))$solution
k <- sum(soln)
m <- nrow(mtrx)
combos <- combinations(m,k)
combos[apply(combos, 1, function(idx) all(colSums(mtrx[idx,]))),]
In the example we get:
[,1] [,2]
[1,] 1 3
[2,] 2 3
which says that rows 1 and 3 of mtrx form one solution
and rows 2 and 3 of mtrx form another solution.
______________________________________________
R-help@stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
