Formulating a problem involving sets with ILP

107 Views Asked by At

Consider set $\mathcal{G} = \{G_1, \ldots, G_K\}$. We are given $\mathcal{A}_i \subset \mathcal{G}$, $i \in \mathcal{N}= \{1,\ldots, N\}$ and for each $\mathcal{A}_i$, there is a corresponding cost denoted by $C_i$. We want to choose $\mathcal{A}_j$, $j \in \mathcal{J} \subset \mathcal{N}$ with minimum cost such that union of $\mathcal{A}_j$, $j \in \mathcal{J}$ is the set $\mathcal{G}$. Therefore, the problem is to $\min_{\alpha_1, \ldots, \alpha_N} \sum_{i \in \mathcal{N}}\alpha_i C_i$ subject to $\cup_{i \in \mathcal{N}, \alpha_i=1} \mathcal{A}_i = \mathcal{G}$, $\alpha_i \in \{0,1\}$ for $i \in \mathcal{N}$.

Is it possible to write this problem as a standard ILP?

1

There are 1 best solutions below

0
On BEST ANSWER

Let me recapitulate (so that I understand this):

  • You have a base set $G$ with $K$ elements.
  • Then you have $N$ subsets $A^{(i)}$ of $G$, each comes with cost $C_i$.
  • You want to cover $G$ with a selection of $A^{(i)}$ such that the cost is minimal.

We can model the selection of subsets via the vector of unknowns $x \in \{ 0, 1 \}^N$.
For each set $A^{(i)}$ we have a vector $y^{(i)} \in \{ 0, 1 \}^K$ which is kind of its index function regarding $G$: $$ y_j^{(i)} = \begin{cases} 1 & \text{if } A^{(i)}_j \in G \\ 0 & \text{else} \end{cases} $$
To cover $G$ a feasible selection $x$ of subsets $A^{(i)}$ must have at least one of each element of $G$ and thus fulfill the constraint $$ 1_K \le \sum_i x_i y^{(i)} = Y x $$ where $1_K = (1, \dotsc, 1)^\top \in \{0,1\}^K$ and $Y = (y^{(1)}, \dotsc, y^{(N)}) \in \{0,1\}^{K \times N}$.

So we got the ILP: $$ \begin{array}{ll} \min & c^\top x \\ \text{w.r.t.} & Y x \ge 1_K \\ & x \in \{ 0, 1 \}^N \end{array} $$ where $c$ is the cost vector with components $C_i$.