Set partitioning

Question

I'm trying to get a good grasp with this problem but I'm struggling. Let's say that I have a S={1,2,3,4,5}, an L={(1,3,4),(2,3),(4,5),(1,3),(2),(5)} and an other tuple with the costs of L like C={10,20,12,15,4,10}

I want to make a constraint program in Prolog so as to take the solution that solves the problem with the minimum cost.(in this occasion it is the total sum of the costs of the subsets i will get)

My problem is that I cannot understand the way I'll make my modelisation. What I know is that I should choose a modelisation of binary variables {0,1} but I hardly understand how i will manage to express it via Prolog.

Answer 1

There is an easy way to do it: You can use Boolean indicators to denote which elements comprise a subset. For example, in your case:

subsets(Sets) :-
    Sets = [[1,0,1,1,0]-10,  % {1,3,4}
            [0,1,1,0,0]-20,  % {2,3}
            [0,0,0,1,1]-12,  % {4,5}
            [1,0,1,0,0]-15,  % {1,3}
            [0,1,0,0,0]-4,   % {2}
            [0,0,0,0,1]-10]. % {5}

I now use SICStus Prolog and its Boolean constraint solver to express set covers:

:- use_module(library(lists)).
:- use_module(library(clpb)).

setcover(Cover, Cost) :-
        subsets(Sets),
        keys_and_values(Sets, Rows, Costs0),
        transpose(Rows, Cols),
        same_length(Rows, Coeffs),
        maplist(cover(Coeffs), Cols),
        labeling(Coeffs),
        phrase(coeff_is_1(Coeffs, Rows), Cover),
        phrase(coeff_is_1(Coeffs, Costs0), Costs),
        sumlist(Costs, Cost).

cover(Coeffs, Col) :-
        phrase(coeff_is_1(Col,Coeffs), Cs),
        sat(card([1],Cs)).

coeff_is_1([], []) --> [].
coeff_is_1([1|Cs], [L|Ls]) --> [L], coeff_is_1(Cs, Ls).
coeff_is_1([0|Cs], [_|Ls]) --> coeff_is_1(Cs, Ls).

For each subset, a Boolean variable is used to denote whether that subset is part of the cover. Cardinality constraints make sure that each element is covered exactly once.

Example query and its result:

| ?- setcover(Cover, Cost).
Cover = [[0,0,0,1,1],[1,0,1,0,0],[0,1,0,0,0]],
Cost = 31 ? ;
Cover = [[1,0,1,1,0],[0,1,0,0,0],[0,0,0,0,1]],
Cost = 24 ? ;
no

I leave picking a cover with minimum cost as an easy exercise.