Re: [eclipse-clp-users] Knappsack-Problem Modification

Hi,

thanks for all your replies. I think Marco's suggestion to minimize the 
total dissimilarity instead of the total average dissimilarities is 
great. I've implemented a version with ic and ic_symbolic (though I know 
it's not neccessary). Maybe I'll try to do it with eplex later, but I am 
not familiar with that lib.

Another problem that comes up are the similarities among the solutions 
as it obviously does not matter in which knapsack several items are 
packed, but that they are in the same.
Example:

    I1 = "B"        I1 = "C"
    I2 = "C"        I2 = "B"
    I3 = "C"        I3 = "B"
    I4 = "B"        I4 = "C"
    I5 = "D"        I5 = "D"
    I6 = "D"        I6 = "D"


Does anyone have a suggestion how to realize symmetry breaking during 
search (e.g. by using ic_sbds) in my implementation? A call could be:

    ?- assignItems([I1, I2, I3, I4, I5, I6], Measure).
    I1 = "B"
    I2 = "C"
    I3 = "C"
    I4 = "B"
    I5 = "D"
    I6 = "D"
    Measure = 120
    Yes (0.06s cpu, solution 1, maybe more)


:-lib(ic_symbolic).
:-lib(ic).

%items having an id and an assigned knapsack
:-export struct(item(id,knap)).

dist("item1","item1",0).
dist("item2","item1",50).
dist("item2","item2",0).
dist("item3","item1",40).
dist("item3","item2",0).
dist("item3","item3",0).
dist("item4","item1",60).
dist("item4","item2",60).
dist("item4","item3",50).
dist("item4","item4",0).
dist("item5","item1",100).
dist("item5","item2",100).
dist("item5","item3",100).
dist("item5","item4",100).
dist("item5","item5",0).
dist("item5","item5",0).
dist("item6","item1",100).
dist("item6","item2",100).
dist("item6","item3",100).
dist("item6","item4",86).
dist("item6","item5",60).
dist("item6","item6",0).

sigma(Items,Knapsack,SumOfDissimilarities) :-
     length(Items,C),
     N is C-1,
     (    count(I,0,N),
         fromto([],This,Next,AllProds),
         param(Items,Knapsack)
     do
         (    count(K,0,I),
             foreach(Prod,ProdList),
             param(Knapsack,Items,I)
         do
             listut:nth0(I, Items, item{id:Id1,knap:Knapsack1}),
             listut:nth0(K, Items, item{id:Id2,knap:Knapsack2}),
             (Id1 \= Id2 ->
&=(Knapsack1, Knapsack, B1),
&=(Knapsack2, Knapsack, B2),
                 $=(B1+B2,2,B3),
                 %B3 is 1, if both items are in the same knapsack
                 dist(Id1,Id2,Dist),
                 Prod $= B3*Dist
             ;
                 Prod $= 0
             )
         ),
         lists:append(ProdList,This,Next)
     ),
     ic_global:sumlist(AllProds,SumOfDissimilarities).

search(List) :-
     (    foreach(Element,List)
     do
         ic_symbolic:indomain(Element)
     ).

assignItems([I1,I2,I3,I4,I5,I6],Measure) :-
     (local domain(knapsacks("B","C","D"))),
     [I1,I2,I3,I4,I5,I6] &:: 
["B","C","D"],Items=[item{id:"item1",knap:I1},item{id:"item2",knap:I2},item{id:"item3",knap:I3},item{id:"item4",knap:I4},item{id:"item5",knap:I5},item{id:"item6",knap:I6}],
     
sigma(Items,"B",Value1),sigma(Items,"C",Value2),sigma(Items,"D",Value3),
     Measure $= (Value1 + Value2 + Value3),
     branch_and_bound:minimize(search([I1,I2,I3,I4,I5,I6]),Measure).

Best regards,
Philipp