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

Hi,

Thanks for your suggestion to see my problem as a Vehicle Routing 
Problem. I think that the mapping of the dissimilarity of items to 
distances of customers works, but as the VRP searches only the optimal 
tour between the cities (Items) it does not take into account the 
distances the vehicles don't pass. But for a meassure of dissimilarity 
these distances do matter.

Do you see a possibility to take these not-passed distances in the VRP 
into account?

What I've tried so far is the following that can be called by:
assignItems([B1,B2,B3,B4,B5,B6],Measure)


:-lib(propia).
:-lib(fd).
:-lib(listut).

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).

%items having an id and a assigned knappsack
:-export struct(item(id,knapp)).

assignItems([B1,B2,B3,B4,B5,B6],Measure) :-
     [B1,B2,B3,B4,B5,B6] #:: ["B","C","D"], %the knappsacks
     
Items=[item{id:"item1",knapp:B1},item{id:"item2",knapp:B2},item{id:"item3",knapp:B3},item{id:"item4",knapp:B4},item{id:"item5",knapp:B5},item{id:"item6",knapp:B6}],
     
sigma(Items,"B",Value1),countItemsInKnappsack(Items,"B",Count1),Measure1 
#= Value1/Count1, 0 #< Count1,
     
sigma(Items,"C",Value2),countItemsInKnappsack(Items,"C",Count2),Measure2 
#= Value2/Count2, 0 #< Count2,
     
sigma(Items,"D",Value3),countItemsInKnappsack(Items,"D",Count3),Measure3 
#= Value3/Count3, 0 #< Count3,
     Measure #= Measure1 + Measure2 + Measure3/3,
     branch_and_bound:minimize(labeling([B1,B2,B3,B4,B5,B6]),Measure).

sigma(Items,Knappsack,Value) :-
     length(Items,C),
     N is C-1,
     (    count(I,0,N),
         fromto([],This,Next,AllProds),
         param(Items,Knappsack)
     do
         (    count(K,0,I),
             foreach(Prod,ProdList),
             param(Knappsack,Items,I)
         do
             nth0(I, Items, item{id:Id1,knapp:Knappsack1}),printf("id:%w 
\t knapp:%w\n",[Id1,Knappsack1]),
             nth0(K, Items, item{id:Id2,knapp:Knappsack2}),
             (Id1 #\= Id2 ->
                 (Knappsack1 #= Knappsack #/\ Knappsack2 #= Knappsack 
#=> B3 #=1 )
                 #/\ (Knappsack1 #\= Knappsack #\/ Knappsack2 #\= 
Knappsack #=> B3 #=0 ),
                 dist(Id1,Id2,Dist) infers most,
                 Prod #= B3*Dist,
                 0 #<= Prod
             ;
                 Prod = 0
             )
         ),
         lists:append(ProdList,This,Next)
     ),
     fd_global:sumlist(AllProds,Value).

countItemsInKnappsack(Items,KnappsackToCount,Count) :-
     (    foreach(item{knapp:Knappsack},Items),
         foreach(C,ContainedItems),
         param(KnappsackToCount)
     do
         %arg(knapp of item,Item,Knappsack),
         C#::[0,1],
         (Knappsack #= KnappsackToCount #=> C #= 1) #/\ (Knappsack #\= 
KnappsackToCount #=> C #= 0)
     ),
     fd_global:sumlist(ContainedItems,Count).



12.04.2010 17:31,Wit Jakuczun:
> 2010/4/12 Philipp Marcus<marcus_at_cip.ifi.lmu.de>:
>    
>> Hi,
>>
>> I have a problem that can be abstracted as a modification of the
>> knappsack problem. I need help to solve it.
>>
>> Imagine:
>> Given a set of items I that have a meassure of dissimilarity amongst
>> eachother: dis(Item1,Item2,Dissimilarity)
>> Given a knappsack K, pack items from I into K so that the average
>> dissimilarity amongst the packed items is minimized, to exclude trivial
>> solutions one might state a constraint that the knappsack has to contain
>> at least k elements.
>>
>> Later I'd like to expand this example to n knappsacks, whereby items
>> should be allocated in such a way, that every item is packed to a
>> knappsack and each knappsack has the lowest average dissimilarity possible.
>>
>>      
> Your problem sounds like some variation of uncapacitated VRP problem.
> There are plenty of heuristics for VRP problems.
>
>    
>> I would be really happy if someone could give me suggestions on how to
>> solve it best.
>>
>>      
> What have you tried so far?
>
> Best regards
>