Today’s topic is submodularity! This special structure allows a whole new mathematical toolbox to be used in the never-ending fight to improve formulations and reach optimal solutions faster.

Let be a finite ground set. A *submodular function* is a set-defined function that exhibits a “diminishing returns” property. That is, adding an element to a small set results in a greater impact on the function than adding that element to a larger set. There are multiple equivalent ways to define a submodular function. Perhaps the most intuitive of these is below.

Let with . is submodular if for every , we have . Here, represents the marginal increase in the set function when element is added to a smaller subset of , . This marginal increase must be *at least as large as* the marginal increase obtained by adding to a larger subset of that contains .

An equivalent definition is as follows. Let . is submodular if .

It should also be noted that under certain conditions, optimizing submodular functions can be very easy.

Let’s examine a few places in public sector operations research that submodularity could arise.

**Example 1: Path interdiction**

Let be a path in a network. In my previous blog post, we discussed basic maximum-reliability network interdiction. In the same vein, let be the probability of traversing arc undetected when arc is *not* interdicted. Let be the probability of traversing arc undetected when the arc *is* interdicted. Naturally, for all . Let be the set of path arcs that we choose to inderdict. Let the function be the probability of an attacker traversing the entire path undetected. This function can be written as

.

Then is *supermodular*. A supermodular function simply reverses the inequalities above: i.e. holds for with and every . The proof is obtained by directly applying the definition of supermodularity. The fact that is supermodular is very intuitive; the more arcs that we interdict, the less of a reduction (not increase!) we notice in the attacker’s traversal probability.

It follows that is *submodular*.

**Example 2: Radio tower coverage**

Imagine we were to give up our lives of fortune as operations researchers and pursue a humbler existence in the radio entertainment industry. We wish to select a subset of radio towers from which to broadcast our station. The broadcast ranges of these towers overlap.

Our goal is to cover as much surface area as possible. Let be the set of towers. For a subset of selected towers , let be the surface area covered by those towers. Then is submodular. Below are a few pictures to illustrate the point.

Suppose we have potential radio towers to use for coverage. Suppose also that want to use the *second* radio tower, because the cost of doing so is negligible.

What happens if we choose to also use the third radio tower? Naturally, our covered surface will increase. Note that the *marginal increase in surface area* is the strictly-blue region.

Cool! Now, suppose that we initially choose to utilize the *first and second* radio stations.

When both of these radio stations are selected, what happens to the marginal increase in surface area when we include the third tower in our broadcast coverage?

Again, the strictly-blue region represents the surface area we added to our network by including the third radio tower. This blue area is much smaller than it was when we included the second tower and not the first. Looking at the definition of submodularity, we expect this marginal increase to be smaller! Mathematically, we have .

Conforti, Michele, Gérard Cornuéjols, and Giacomo Zambelli. *Integer programming*. Vol. 271. Berlin: Springer, 2014.

Nice post – I particularly enjoyed the radio tower pictures. Is it “easy” to optimize the two examples you provided here?

LikeLike

Submodular maximization in general is known to NP-hard. However, we can still find acceptable solutions to some submodular maximization problems. For example, if we only allow ourselves to utilize a fixed number of radio towers, we can use a result from Nemhauser and friends. They showed that a greedy algorithm has a performance guarantee of ~63.2%.

The best-case scenario for submodular maximization is when we are maximizing a nonnegative linear function over what’s known as a submodular polyhedron (with a few other tiny assumptions). In this case, the greedy algorithm yields precisely the optimal solution.

LikeLike

I think this is a very nice introduction of submodularity and public sector OR. And I also enjoyed the picture in the radio station example, they are very well visualized!

We see examples for submodular maximization(and supermodular minimization) here, that’s NP-hard in general. Do you have any other thoughts for the inverse case, submodular minimization, in public sector OR ?

LikeLike

Submodular minimization is easier. This makes sense when you think of submodular functions as the “discrete version” of convex functions. There exist many polynomial algorithms for submodular minimization. The min-cut problem, which could be often seen in public sector OR, can be formulated as a submodular minimization problem.

LikeLike