TOPICS
Search

Set Covering Deployment


Set covering deployment (sometimes written "set-covering deployment" and abbreviated SCDP for "set covering deployment problem") seeks an optimal stationing of troops in a set of regions so that a relatively small number of troop units can control a large geographic region. ReVelle and Rosing (2000) first described this in a study of Emperor Constantine the Great's mobile field army placements to secure the Roman Empire. Set covering deployment can be mathematically formulated as a (0,1)-integer programming problem.

RomanEmpire

To formulate the Roman domination problem, consider the eight provinces of the Constantinian Roman Empire illustrated above. Each region is represented as a white disk, and the red lines indicate region connections. Call a region secured if one or more field armies are stationed in that region, and call a region securable if a field army can be deployed to that area from an adjacent area. In addition, assume that a field army can only be deployed to an adjacent region if at least one army remains in the original region to provide logistical support. Also assume that each region contains at most two armies, as the number of available armies are limited and cannot be concentrated in any one region.

RomanEmpireGraph

This problem can then be mathematically formulated by representing the Empire as a graph G=(V,E) with vertex set V and edge set E. We can then associate two binary variables X_i and Y_i with each vertexv_i (i.e., each province) in the vertex set V=(v_1,...,v_n) of the Roman Empire graph which specify whether a first and second field army (respectively) is located at a given vertex v_i. In the terminology of graph theory, the Roman Empire graph is a simple connected graph on eight vertices and with 13 edges.

In set covering deployment, the problem to be solved is to maximize the quantity sum_(i=1)^(n)(X_i+Y_i) subject to the constraints

 X_i>Y_i for all i,
(1)

which guarantees that the first legion is stationed at a given vertex before a second can be,

 X_i+sum_((v_i,v_j))Y_j>1 for all i,
(2)

which guarantees that if v_i does not contain a field army, it has a neighbor with two field armies, and

 X_i,Y_i in 0,1 for all i,
(3)

which enforces the integer constraint (i.e., when combined with the first constraint, only zero, one, or two field armies may be placed in any given region). This integer programming problem can then be translated into matrix terms and solved using standard techniques to find the minimum number of field armies needed to secure the Constantinian Roman Empire (ReVelle and Rosing 2000, Rubalcaba 2005).

In the Season 4 opening episode "Trust Metric" (2007) of the television crime drama NUMB3RS, math genius Charlie Eppes uses set covering deployment as an analogy for optimizing the position of police officers in downtown Los Angeles in a search for escaped fugitives.


See also

Integer Programming, Linear Programming, Optimization

Explore with Wolfram|Alpha

References

ReVelle, C. S. and Rosing, K. E. "Defendens Imperium Romanum: A Classical Problem in Military Strategy." Amer. Math. Monthly 107, 585-594, 2000.Rubalcaba, R. R. "Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs." Ph.D. dissertation. Auburn, Alabama: Auburn University. May 13, 2005. http://webpages.uah.edu/~rubalcr/RUBALCABA.pdf.

Referenced on Wolfram|Alpha

Set Covering Deployment

Cite this as:

Weisstein, Eric W. "Set Covering Deployment." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SetCoveringDeployment.html

Subject classifications