From: Wit Jakuczun <wit.jakuczun_at_...6...>

Date: Tue, 13 Apr 2010 13:41:28 +0200

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
: Mon Jul 09 2018 - 02:05:29 CEST
*