Try minizing 1'x subject to 1 >= x >= 0 and m'x >= 1 where m is your mtrx and ' means transpose. It seems to give an integer solution, 1 0 1, with linear programming even in the absence of explicit integer constraints:
library(lpSolve) lp("min", rep(1,3), rbind(t(mtrx), diag(3)), rep(c(">=", "<="), 4:3), rep(1,7))$solution On 11/19/05, Adrian DUSA <[EMAIL PROTECTED]> wrote: > Dear list, > > I have a problem with a toy example: > mtrx <- matrix(c(1,1,0,1,1,1,0,1,1,0,0,1), nrow=3) > rownames(ma) <- letters[1:3] > > I would like to determine which is the minimum combination of rows that > "covers" all columns with at least a 1. > None of the rows covers all columns; all three rows clearly covers all > columns, but there are simpler combinations (1st and the 3rd, or 2nd and 3rd) > which also covers all columns. > > I solved this problem by creating a second logical matrix which contains all > possible combinations of rows: > tt <- matrix(as.logical(c(1,0,0,0,1,0,0,0,1,1,1,0,1,0,1,0,1,1,1,1,1)), nrow=3) > > and then subset the first matrix and check if all columns are covered. > This solution, though, is highly inneficient and I am certain that a > combination of apply or something will do. > > ########################### > > possibles <- NULL > length.possibles <- NULL > ## I guess the minimum solution is has half the number of rows > guesstimate <- floor(nrow(tt)/2) + nrow(tt) %% 2 > checked <- logical(nrow(tt)) > repeat { > ifelse(checked[guesstimate], break, checked[guesstimate] <- TRUE) > partials <- as.matrix(tt[, colSums(tt) == guesstimate]) > layer.solution <- logical(ncol(partials)) > > for (j in 1:ncol(partials)) { > if (length(which(colSums(mtrx[partials[, j], ]) > 0)) == ncol(mtrx)) { > layer.solution[j] <- TRUE > } > } > if (sum(layer.solution) == 0) { > if (!is.null(possibles)) break > guesstimate <- guesstimate + 1 > } else { > for (j in which(layer.solution)) { > possible.solution <- rownames(mtrx)[partials[, j]] > possibles[[length(possibles) + 1]] <- possible.solution > length.possibles <- c(length.possibles, length(possible.solution)) > } > guesstimate <- guesstimate - 1 > } > } > final.solution <- possibles[which(length.possibles == min(length.possibles))] > > ########################### > > More explicitely (if useful) it is about reducing a prime implicants chart in > a Quine-McCluskey boolean minimisation algorithm. I tried following the > original algorithm applying row dominance and column dominance, but (as I am > not a computer scientist), I am unable to apply it. > > If you have a better solution for this, I would be gratefull if you'd share > it. > Thank you in advance, > Adrian > > -- > Adrian DUSA > Romanian Social Data Archive > 1, Schitu Magureanu Bd > 050025 Bucharest sector 5 > Romania > Tel./Fax: +40 21 3126618 \ > +40 21 3120210 / int.101 > > ______________________________________________ > 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 > ______________________________________________ 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