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

From: Philipp Marcus <marcus_at_cip.ifi.lmu.de>
Date: Tue, 13 Apr 2010 13:15:13 +0200
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.

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

<http://87.230.22.228/doc/bips/lib/fd/HNN-2.html>
> 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

Best regards,
Philipp
Received on Tue Apr 13 2010 - 11:15:20 CEST

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