$
$ Set partition, set covering in Essence'
$
$ Example from Lundgren, RÃ¶nnqvist, Vaerbrand
$ "Optimeringslaera", page 408
$ (it's a Swedish book about optimization theory/operations research)
$
$ We want to minimize the cost of the alternatives which covers all the
$ objects, i.e. all objects must be choosen. The requirement is than an object
$ may be selected _exactly_ once.
$
$ Alternative Cost Object
$ 1 19 1,6
$ 2 16 2,6,8
$ 3 18 1,4,7
$ 4 13 2,3,5
$ 5 15 2,5
$ 6 19 2,3
$ 7 15 2,3,4
$ 8 17 4,5,8
$ 9 16 3,6,8
$ 10 15 1,6,7
$
$ The problem has a unique solution of z = 49 where alternatives
$ 3, 5, and 9 is selected.
$
$ If we, however, allow that an object is selected more than one time,
$ then the solution is z = 45 (i.e. less cost than the first problem),
$ and the alternatives 4, 8, and 10 is selected, where object 5 is
$ selected twice (alt. 4 and 8). It's an unique solution as well.
$
$
$ Model created by Hakan Kjellerstrand, hakank@gmail.com
$ See also my Essence' page: http://www.hakank.org/savile_row/
$
language ESSENCE' 1.0
letting num_alternatives be 10
letting num_objects be 8
letting costs: matrix indexed by [int(1..num_alternatives)] of int(1..20) be [ 19, 16, 18, 13, 15, 19, 15, 17, 16, 15]
$ the alternatives and the objects they contain
letting alt: matrix indexed by [int(1..num_alternatives), int(1..num_objects)] of int(0..1) be
[
$ 1 2 3 4 5 6 7 8 the objects
[1,0,0,0,0,1,0,0], $ alternative 1
[0,1,0,0,0,1,0,1], $ alternative 2
[1,0,0,1,0,0,1,0], $ alternative 3
[0,1,1,0,1,0,0,0], $ alternative 4
[0,1,0,0,1,0,0,0], $ alternative 5
[0,1,1,0,0,0,0,0], $ alternative 6
[0,1,1,1,0,0,0,0], $ alternative 7
[0,0,0,1,1,0,0,1], $ alternative 8
[0,0,1,0,0,1,0,1], $ alternative 9
[1,0,0,0,0,1,1,0] $ alternative 10
]
$ decision variable: which alternatives to choose
find x: matrix indexed by [int(1..num_alternatives)] of int(0..1)
$ the objective to minimize
find z: int(0..1000)
minimising z
such that
forall j: int(1..num_objects) .
$ all objects must be covered _exactly_ once, i.e. set partition
(sum i: int(1..num_alternatives) . x[i]*alt[i,j] ) = 1
$ variant: all objects must be covered _at least_ once, i.e. set covering
$ (sum i: int(1..num_alternatives) . x[i]*alt[i,j] ) >= 1
,
z = sum i: int(1..num_alternatives) . x[i]*costs[i]