# modeling Set Cover and Multicommodity Flow

Set Cover and Multicommodity flow as (integer) linear programs.

Modeling a problem as a linear program or integer linear program is a basic skill. Here are two examples.

# Set Cover

Recall the definition of Set Cover: Given a collection of finite sets from a universe and a cost for each set , the problem is to choose a minimum-cost set cover — a collection of sets in such that each element is contained in at least one set in . The cost of is .

The standard integer linear program for the problem is

$\min \Big\{ c\cdot x ~ |~ x\in {\mathbb Z}_+^{|{\cal S}|};\, (\forall e\in U)\, \sum _{s\ni e} x_ s \ge 1\Big\} .$

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

$\min \Big\{ c\cdot x ~ |~ x\in {\mathbb R}_+^{|{\cal S}|};\, (\forall e\in U)\, \sum _{s\ni e} x_ s \ge 1\Big\} .$

If a (possibly fractional) meets the constraint for an element , we say that covers , and, if covers all elements, it is a fractional set cover — a feasible solution to the linear program. If is an integer solution, we identify it with the collection of sets .

The figure shows a fractional set cover of size 2 (that is, ). The value assigned to each variable is written above its set . For each element , the total coverage of is shown below . The total coverage of each element is at least 1, so is a fractional set cover.

# Multicommodity Flow

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

$\max \Big\{ |f| : f\in {\mathbb R}_+^{|P|}, (\forall e\in E)\, \sum _{p\ni e} f_ p \le c_ e\Big\} .$

For each path , there is a variable representing the flow on path . For each edge , there is a constraint that the total flow on paths through the edge is at most the edge capacity . Subject to these constraints, the objective is to maximize the total flow (i.e., ) on all paths.

Remark.

The number of variables in this formulation can be exponential in the size of the graph.1 Greedy and Lagrangian-relaxation algorithms can deal with this, as long as they have an appropriate oracle (optimization subroutine).

Exercise.

Describe how, given a graph , to model the problem of finding a maximum-size independent set in as an integer linear programming problem.

# Wikipedia

## Footnotes

1. You may be familiar with an alternate formulation of network flow using flow variables for the edges. That formulation can be smaller, but has both negative and positive coefficients — it is not a packing or covering linear program.