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

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/