/*
Set partition and set covering in Comet.
Example from the swedish book Lundgren, Rönnqvist, Värbrand "Optimeringslära" (translation: "Optimization theory"), page 408.
* Set partition:
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.
* Set covering:
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.
Compare with the MiniZinc model http://www.hakank.org/minizinc/set_covering4.mzn
This Comet model was created by Hakan Kjellerstrand (hakank@bonetmail.com)
Also, see my Comet page: http://www.hakank.org/comet
*/
import cotfd;
int t0 = System.getCPUTime();
int num_alternatives = 10;
int num_objects = 8;
// costs for the alternatives
int costs[1..num_alternatives] = [ 19, 16, 18, 13, 15, 19, 15, 17, 16, 15];
// the alternatives, and their objects
int a[1..num_alternatives, 1..num_objects] =
[
// 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
];
Solver m();
// decision variable: which alternative to choose
var{int} x[1..num_alternatives](m, 0..1);
// the objective to minimize
var{int} z(m, 0..100000);
Integer num_solutions(0);
// exploreall {
minimize z subject to {
// m.post(z <= 45); // for exploreall
m.post(z == sum(i in 1..num_alternatives) x[i]*costs[i]);
forall(j in 1..num_objects) {
// set partition: all objects must be covered _exactly_ once
m.post(sum(i in 1..num_alternatives) (x[i]*a[i,j]) == 1);
// set covering: all objects must be covered _at least_ once
// m.post(sum(i in 1..num_alternatives) (x[i]*a[i,j]) >= 1);
}
} using {
label(m);
num_solutions := num_solutions + 1;
cout << x << " z: " << z << endl;
cout << "selected: ";
forall(i in 1..num_alternatives)
if (x[i] == 1)
cout << i << " ";
cout << endl;
}
cout << "\nnum_solutions: " << num_solutions << endl;
int t1 = System.getCPUTime();
cout << "time: " << (t1-t0) << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail = " << m.getNFail() << endl;
cout << "#propag = " << m.getNPropag() << endl;