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

From: Wit Jakuczun <wit.jakuczun_at_gmail.com>
Date: Tue, 13 Apr 2010 13:41:28 +0200
W dniu 2010-04-13 13:15, Philipp Marcus pisze:
> Hi,
>
> thanks for all your hints in your previous mail. My exact problem is:
>
> Given a set of items that have a certain dissimilarity amongst each 
> other. Also given n knappsacks with unbounded capacity, the items 
> should be allocated in such a way, that every item is packed to a 
> knappsack and each knappsack has the lowest  possible average 
> dissimilarity among its items. (Put similar things in the same knappsack).
>
> Currently I also don't know exactly how to map it to the knappsack 
> problem, to show that it is NP-complete (if it is, but I guess so). 
> One aspect that would speak against seeing it as a knappsack problem 
> is, that in my formulation the capacity of the knappsack and the 
> volumes of items don't play any role.
>
Ok. So what is your exact task to do:
1) to prove NP-completeness of the problem
2) write a solver for a problem using ECLiPSe ?


>> Next remarks:
>> 1)  You are using fd library. It is, according to my knowledge, 
>> recommended to use ic library.
> Thats a good point. I decided to use fd because i have no ordering in 
> my symbolic domain. Maybe I should check to transform it to 
> ic_symbolic. I think this would make it much easier to integrate 
> distances that are reals.
>
You could also use 1,2 and 3 instead of A, B and C. Ordering in domain 
is not important for you.

>> 2) Domains of CLP variables should consist of integers (unless you 
>> are using ic_symbolic library)
>>
>> [B1,B2,B3,B4,B5,B6] #:: ["B","C","D"]
> The definition of #:: in lib(fd) allows using lists AND variables.
> http://87.230.22.228/doc/bips/lib/fd/HNN-2.html
>
I was referring to elements of the lists. From the link:
/+Domain/
    Variable, integer, integer interval or a list of integers and
    integer intervals.

You used "A", "B" and "C" that are not integers.--

Best regards

[ Wit Jakuczun http://pl.linkedin.com/in/jakuczunwit ]
Received on Tue Apr 13 2010 - 11:41:45 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET