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

From: Wit Jakuczun <wit.jakuczun_at_...6...>
Date: Mon, 12 Apr 2010 17:31:31 +0200
2010/4/12 Philipp Marcus <marcus_at_...247...>:
> 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  ]
Received on Mon Apr 12 2010 - 15:31:41 CEST

This archive was generated by hypermail 2.3.0 : Mon Aug 26 2019 - 09:14:36 CEST