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.