$
$ Set covering deployment in Essence'.
$
$ See http://mathworld.wolfram.com/SetCoveringDeployment.html
$ """
$ 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.
$ """
$
$ Reference:
$ - ReVelle, Rosing, K. E.
$ "Defendens Imperium Romanum: A Classical Problem in Military Strategy."
$
$ Model created by Hakan Kjellerstrand, hakank@gmail.com
$ See also my Essence'/Tailor page: http://www.hakank.org/savile_row/
$
language ESSENCE' 1.0
$ data
$ number of countries
letting n be 8
$ the incidence matrix of country neighbours
$ Alexandria, Asia minor, Britain, Byzantium, Gaul, Iberia, Rome, Tunis
letting m =
[[0, 1, 0, 1, 0, 0, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0, 1, 0],
[0, 0, 1, 0, 0, 1, 1, 0],
[0, 0, 1, 0, 1, 0, 1, 1],
[1, 0, 0, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0]
]
$ the first army
find X: matrix indexed by [int(1..n)] of int(0..1)
$ the second (reserve) army
find Y: matrix indexed by [int(1..n)] of int(0..1)
$ number of armies (objective to minimize)
find c_armies: int(0..n)
minimising c_armies
such that
c_armies = sum i: int(1..n) . X[i] + Y[i],
$ Constraint 1: There is always an army in a city (+ maybe a backup)
$ Or rather: Is there a backup, there must be an an army
forall i: int(1..n) . X[i] >= Y[i],
$ Constraint 2: There should always be an backup army near every city,
$ (i.e. all cities must be covered).
forall i: int(1..n) .
(X[i] + (sum j: int(1..n) . (m[i,j] = 1)*Y[j])) >= 1