Set Cover

Recall the definition of Set Cover: Given a collection ${\cal S}$ of finite sets from a universe $U$ and a cost $c_s$ for each set $s\in {\cal S}$, the problem is to choose a minimum-cost set cover — a collection ${\cal C}$ of sets in ${\cal S}$ such that each element $e\in U$ is contained in at least one set in ${\cal C}$. The cost of ${\cal C}$ is $\sum _{s\in {\cal C}} c_s$.

The standard integer linear program for the problem is

In the linear-program relaxation of the problem, the variables can take non-integer values:

If a (possibly fractional) $x$ meets the constraint $\sum _{s\ni e} x_s \ge 1$ for an element $e$, we say that $x$ covers $e$, and, if $x$ covers all elements, it is a fractional set cover — a feasible solution to the linear program. If $x$ is an integer solution, we identify it with the collection of sets $\{ s\in {\cal S}: x_s \gt 0\}$.

The figure shows a fractional set cover of size 2 (that is, $\sum _s x_s = 2$). The value assigned to each variable $x_s$ is written above its set $s$. For each element $e$, the total coverage $\sum _{s\ni e} x_s$ of $e$ is shown below $e$. The total coverage of each element is at least 1, so $x$ is a fractional set cover.

Multicommodity Flow

Maximum multicommodity flow (defined in this note) is exactly modeled by the following linear program:

For each path $p\in P$, there is a variable $f_p$ representing the flow on path $p$. For each edge $e$, there is a constraint that the total flow on paths through the edge is at most the edge capacity $c_e$. Subject to these constraints, the objective is to maximize the total flow $|f|$ (i.e., $\sum _p f_p$) on all paths.

Wikipedia

• Set cover

• Multi-commodity flow

• covering and packing

• linear programming