[R] Looking for an R package for Set Cover Problem

[Hans W Borchers]

As the Wikipedia page you took your example problem from explains, the sets
cover problem can be formulated as an integer linear programming problem.
In R, such problems will be solved effectively applying one of the available
MILP packages, for example LPsolve or Rsymphony.


Kumar Mainali <kpmainali <at> gmail.com> writes:
>
> I am looking for an R package that solves Set Cover Problem. As Wikipedia
> explains:
>
> Given a set of elements [image: \{1,2,...,m\}] (called the universe) and a
> set [image: S] of [image: n] sets whose union equals the universe, the set
> cover problem is to identify the smallest subset of [image: S] whose union
> equals the universe. For example, consider the universe [image: U = \{1, 2,
> 3, 4, 5\}] and the set of sets [image: S = \{\{1, 2, 3\}, \{2, 4\}, \{3,
> 4\}, \{4, 5\}\}]. Clearly the union of [image: S] is [image: U]. However,
> we can cover all of the elements with the following, smaller number of
> sets: [image: \{\{1, 2, 3\}, \{4, 5\}\}].

For this concrete case the set of linear inequalities looks like:

    x1           >= 1  # as 1 is only element of S1
    x1 + x2      >= 1  # etc.
    x1 + x3      >= 1
    x2 + x3 + x4 >= 1
    x4           >= 1  # all xi in {0,1}

which has the minimal solution x1, x2, x3, x4 = 1, 0, 0, 1 .

> Thank you,
> Kumar Mainali
>
> Postdoctoral Fellow
> Environmental Science Institute
> The University of Texas at Austin
> ᐧ