/*
Set covering, set partition in SICStus Prolog.
Example from Lundgren, Rönnqvist, Värbrand
"Optimeringslära" ["Optimization"], page 408.
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.
Compare with the following models:
* MiniZinc: http://www.hakank.org/minizinc/set_covering4.mzn
* Comet : http://www.hakank.org/comet/set_covering4.co
* ECLiPSe : http://www.hakank.org/eclipse/set_covering4.ecl
Model created by Hakan Kjellerstrand, hakank@bonetmail.com
See also my SICStus Prolog page: http://www.hakank.org/sicstus/
*/
:-use_module(library(clpfd)).
:-use_module(library(lists)).
%
% First find the optimal value (MinVal), then find all the solutions
% with that value.
%
% Note: This model handles both the set partition and
% the set covering problem.
%
go :-
%
% set partition
%
write('SET PARTITION'),nl,
write('Find the optimal solution'),nl,
problem(Costs,Alternatives),
set_covering4(Costs, Alternatives, set_partition, MinVal,_),
format('\nFinding all optimal solutions with MinVal ~d:\n', [MinVal]),
findall(Assignments,
set_covering4(Costs, Alternatives, set_partition,
MinVal,Assignments),
L),
length(L, Len),
write(all_solutions:L),nl,
format('It was ~d solution(s) (set partition)\n', [Len]),
%
% set covering
%
write('\nSET COVERING\n'),nl,
write('Find the optimal solution'),nl,
problem(Costs,Alternatives),
set_covering4(Costs, Alternatives, set_covering, MinVal2,_),
format('\nFinding all optimal solutions with MinVal ~d:\n', [MinVal2]),
findall(Assignments2,
set_covering4(Costs, Alternatives, set_covering,
MinVal2,Assignments2),
L2),
length(L2, Len2),
write(all_solutions:L2),nl,
format('It was ~d solution(s) (set covering)\n', [Len2]),
fd_statistics.
set_covering4(Costs, Alternatives, Type, MinVal, Assignments) :-
% costs
length(Costs,NumAlternatives),
% alternatives
matrix(Alternatives,[NumAlternatives,_NumObjects]),
% decision variable: which alternative to choose
length(Xs,NumAlternatives),
% which alternative to choose
length(Xs,NumAlternatives),
domain(Xs,0,1),
% cover all objects with the alternatices
% (note: uses the transpose)
transpose(Alternatives,AlternativesT),
( foreach(Alternative,AlternativesT),
param(Xs,Type) do
scalar_product(Alternative,Xs,#=,Sum),
% set partition or set covering?
(
Type = set_partition
->
% all objects must be covered _exactly_ once
% (set partition)
Sum #= 1
;
% variant: all objects must be covered _at least_ once
% (set covering)
Sum #>= 1
)
),
% objective: minimize the number of alternatives
scalar_product(Costs,Xs,#=,Z),
Z #= MinVal,
%
% either search for all solutions (for the minimum value) or
% the optimal value
%
(
ground(MinVal)
->
labeling([], Xs)
;
labeling([minimize(Z)], Xs)
),
% which assignments was made?
assignments(Xs, Assignments),
write(z:Z),nl,
write(x:Xs),nl,
write(assignements:Assignments),nl,nl.
assignments(Xs,Assignments) :-
( foreach(X, Xs),
count(N,1,_),
fromto(Assignments, Out, In, [])
do
X #= 1 ->
Out = [N|In]
;
Out = In
).
% From Mats Carlsson
matrix(_, []) :- !.
matrix(L, [Dim|Dims]) :-
length(L, Dim),
( foreach(X,L),
param(Dims)
do matrix(X, Dims)
).
%
% Costs and the alternatives
%
problem([19, 16, 18, 13, 15, 19, 15, 17, 16, 15], % costs
[[1,0,0,0,0,1,0,0], % alternative 1 % alternatives
[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