From: Marco Gavanelli <marco.gavanelli_at_unife.it>

Date: Tue, 13 Apr 2010 13:46:57 +0200

Date: Tue, 13 Apr 2010 13:46:57 +0200

Dear Philipp, Philipp Marcus wrote: > 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). My guess is that it is not NP-complete, but NP-hard, since it is an optimization problem and not a satisfaction problem. I would suggest to use the eplex library, as your problem can be seen as an integer programming problem, and eplex is probably the most efficient way to solve it. The model could be the following: VARIABLES: I have a matrix X of variables that can take values 0 or 1; the element Xik of the matrix takes value 1 iff you put object i into knapsack k Also, I have another matrix D, whose elements Dijk can take value 0 or 1. Dijk is 1 iff object i and object j are both in the knapsack k CONSTRAINTS: > every item is packed to a knapsack (for each item i), the \sum_k Xik=1 (i.e., you sum varying k, and you do that for each i, so you have a number of constraints equal to the number of objects) Relation between matrix D and matrix X: for each pair of objects (i,j) and for each knapsack k 2*Dijk >= Xik+Xjk i.e., if both Xik and Xjk are 1, then Dijk should take value 1. OBJECTIVE FUNCTION: minimize the total dissimilarity. The total dissimilarity is the sum of the dissimilarity for every knapsack. The dissimilarity for knapsack k is given as sum_i,j Dijk*DISS(i,j) i.e., for each pair (i,j) you ave a dissimilarity DISS taken from your predicate dist(i,j,DISS). It is a constant, so if you multiply it by a decision variable (such as Dijk) you still get a linear function. Cheers, Marco -- Marco Gavanelli, Ph.D. in Computer Science Dept of Engineering University of Ferrara Tel/Fax +39-0532-97-4833 http://www.ing.unife.it/docenti/MarcoGavanelli/Received on Tue Apr 13 2010 - 11:47:14 CEST

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