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

From: Wit Jakuczun <wit.jakuczun_at_gmail.com>
Date: Mon, 12 Apr 2010 17:31:31 +0200
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
-- 
[ Wit Jakuczun  http://www.linkedin.com/in/jakuczunwit  ]
Received on Mon Apr 12 2010 - 15:31:41 CEST

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