Min Set Cover ILP¶

Author: Ben Rosenberg¶

Imports¶

We begin by importing some relevant libraries. We import ortools to formulate and solve the ILP, and we import time to time the entire process of solving the ILP.

In [1]:
from ortools.linear_solver import pywraplp as OR
import time

Input data¶

Next, we define our input data. Recall from lecture that in the Set Cover problem we have as an input a set $U$ of $N$ elements, and a set $S$ of $M$ subsets of $U$.

Here is the input we will be using:

We will create and solve an ILP to determine the solution to the minimum set cover problem, in which we select the fewest possible elements of $S$ such that all elements in $U$ are contained in their union.

In [2]:
universe = range(1, 11)

subsets = {
    1: [1, 2, 3, 4, 10],
    2: [2, 3, 4, 5, 6, 7, 9],
    3: [8, 10],
    4: [2, 4, 5, 7, 8, 9],
    5: [3, 4, 6, 7, 9],
    6: [5, 7],
    7: [3, 4, 6],
    8: [5, 8]
}

Model Definition¶

Now we define our model. The Set Cover problem has the following constraint, using the variable $x_s$ to denote whether subset $s$ is included in the solution:

$$\sum_{s : u\in s} x_s \geq 1 \qquad \forall u\in U$$

And the objective simply minimizes the total number of subsets used:

$$\min \sum_{s\in S} x_s$$

In [ ]:
start_time = time.time()

m = OR.Solver('Set Cover', OR.Solver.SCIP_MIXED_INTEGER_PROGRAMMING)

# add variable x
x = {}
for s in subsets:
    x[s] = m.BoolVar(f'x[{s}]')

# add constraint for each element of the universe
for u in universe:
    m.Add(sum(x[s] for s,subset in subsets.items() if u in subset) >= 1)

# set objective
m.Minimize(sum(x[s] for s in subsets))

m.Solve()

end_time = time.time()

diff = time.gmtime(end_time - start_time)
print('\n[Total time used: {} minutes, {} seconds]'.format(diff.tm_min, diff.tm_sec))

print('Objective:', m.Objective().Value())

[Total time used: 0 minutes, 0 seconds]
Objective: 3.0

So we have our optimal objective. The optimal solution associated with that, in terms of selected subsets, is given below:

In [4]:
# optimal solution
for s in subsets:
    print(f'x[{s}] = {x[s].solution_value()}')

x[1] = 1.0
x[2] = 0.0
x[3] = 0.0
x[4] = 1.0
x[5] = 0.0
x[6] = 0.0
x[7] = 1.0
x[8] = 0.0