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