On 11/19/05, Gabor Grothendieck <[EMAIL PROTECTED]> wrote:
> On 11/19/05, Gabor Grothendieck <[EMAIL PROTECTED]> wrote:
> > 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
>
> Just one after thought. The constraint x <= 1 will not be active so,
> eliminating it, the above can be reduced to:
>
> lp("min", rep(1,3), rbind(t(mtrx)), rep(">=", 4), rep(1,4))$solution
Although the above is not wrong I should have removed the rbind
which is no longer needed and simplifying it further, as it seems
that lp will do the rep for you itself for certain arguments, gives:
lp("min", rep(1,3), t(mtrx), ">=", 1)$solution # 1 0 1
>
>
> >
> >
> >
> > 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
