0/1 MultiDimensional Knapsack Problem

hello guys. im in trouble with 01MKP. Actually I dont know how to ask. If there is someone who is familiar this problem, im asking him/her

There is dataset for test this algorithm from JE beasley ( Here: http://people.brunel.ac.uk/~mastjjb/...les/mknap2.txt )

in this data set, we have 2 knapsack with capacities 600. 28 items with different weights. and each item has different constraint for each knapsack.
For example, item #1 has 1898 weight. the capacity of knapsack #1 is 600 (smaller than item)

And in the constr list #1, item #1 has 45 constraint for knapsack 1.

Can someone tell me how we can determine this 45 value? I mean what is the tricky point in this stupid problem:\

2 28 // 2 knapsacks, 28 objects
1898 440 22507 270 14148 3100 4650 30800 615 4975
1160 4225 510 11880 479 440 490 330 110 560
24355 2885 11748 4550 750 3720 1950 10500 // 28 weights
600 600 // 2 knapsack capacities
45 0 85 150 65 95 30 0 170 0
40 25 20 0 0 25 0 0 25 0
165 0 85 0 0 0 0 100 // #1 constr.
30 20 125 5 80 25 35 73 12 15
15 40 5 10 10 12 10 9 0 20
60 40 50 36 49 40 19 150 // #2 constr.

Have you tried reading one of the literature articles on this topic?

See, for example, http://home.himolde.no/~arildh/nikgakn.pdf

Quote:

---

Originally Posted by BioPhysEngr

Have you tried reading one of the literature articles on this topic?

See, for example, http://home.himolde.no/~arildh/nikgakn.pdf

---

sorry buddy. I'm really newbie about this topic and im researching for days. finally i got it.

but if you are familiar this problem, i wanna ask one more question..

My solution candidates are in a two-dimensional array

For ex. if there are 3 items, solution candidates are:

000
001
010
011
100
101
110
111

Beside, I wanna solve this problem with tabu search algorithm. (I'm newbie about that too)

If I didnt get wrong, there should be a graph instead of 2-dim array for tabu search. Right?
And if your answer is "true" then how i can generate this graph?

or anything else that can help me about this problem?

dont swear me:) thanks in advance.........

can you help me out too? pleasee. im a newbie to it. i have the same questions as your original post.
im going to use it on gsa with tabu search. but first . i really need to know know this multidimensional knapsack works? please help or contact me ?

I think this description makes sense:

http://tracer.lcc.uma.es/problems/multi01knap/knap.htm

I think the 'weights' correspond to the c vector while the constraints correspond to the A matrix

Hope that helps

uhm ok.. but i still quite dont get it. i have quite a few questions, if u dont mind:
im basing this on 1d 0-1 knapsack, i have the same referece as the one who started this
thread (because i dont know how to start a post here)..
1. is the answer of the sample stated above (2 knpacks,28 objcts), a one dimensional array?
2. in r. papers, they say maximize the total profit of selected items, but on the comments in the data set doesnt give the profit property of the items, only the weights, and constraint on each knapsack? i guessing its no the profit!=contraints because profit>0.
???
3. if final answer is indeed in 1d array, so does in my algorithm i have to consider the every objects constraint in each dimension to be able to put into THE knapsack (only 1 knapsack)? (OR does this have two knapsack and answer should be in 2d array?? i think im confusing the concept of multidimensional and multiple knapsack problem.. sorrry .. )

sorry i really dont know this much. i need to clarify things.. please help. number i most important :(

So, I'm not 100% sure, but I think that for this dataset:

Code:

---

2 28 // 2 knapsacks, 28 objects
1898 440 22507 270 14148 3100 4650 30800 615 4975
1160 4225 510 11880 479 440 490 330 110 560
24355 2885 11748 4550 750 3720 1950 10500 // 28 weights
600 600 // 2 knapsack capacities
45 0 85 150 65 95 30 0 170 0
40 25 20 0 0 25 0 0 25 0
165 0 85 0 0 0 0 100 // #1 constr.
30 20 125 5 80 25 35 73 12 15
15 40 5 10 10 12 10 9 0 20
60 40 50 36 49 40 19 150 // #2 constr.

---

That the following things are true:

(a) You have two knapsacks, each of which is constrained to hold only 600 units. There are 28 items, each item of which has three properties (a) 'weight' = profit, (b) units required if you store it in knapsack one, and (c) units required if you store it in knapsack two. These three parameters are given in three arrays of 28 elements. So for example, the first item has a weight (profit) of 1898, and can be stored in knapsack 1 using 45 units of knapsack 1's space or can be stored in knapsack 2, using 30 units of knapsack 2's space (or can be stored in neither).

I'm not 100% sure that the 'weights' are actually equivalent to 'profit' in the formalism I just linked to, but I THINK they are because (a) in that case, all the relevant information has been given and (b) the weights, in many cases, exceed the capacity of the knapsacks and it seems odd that they would be included in the problem if they were obviously irrelevant.

So. Best guess (but I think it seems pretty likely).

Does that help?

Also, you can read one of the texts on this problem for free at OpenLibrary:

http://openlibrary.org/books/OL18082...apsack_problem

thanks so much for the explanation , i kind of though the same too that weight there may be the profit, or that weight in that dataset corresponds to it constraint*profit = weight (but i think this is very unlikely too because i would still have to derive that profit from weight) ..
but i'm still confused of what the solution looks like for the problem: please, sorry again
i have 3 possibilities in mind:

well for a dataset like the first one but this time there are only 5 items to include, still two knapsacks.

1. 1 dimensional array?
01101 (sample optimal solution)
such that this solution (combination) does not exceed each of the knapsacks capacity?
so max profit is same for each knapsack, considered as one?
2. 2 dimensional array? number of instances per item=number of knapsack
01101
10101
in this scene, it seems as though there are two instance for each item (for each knapsack)
so the maxProfit wil be summation of all items included for each knapsack?
3. 2 dimensional array? like if item 1 is already in knapsack 1, it cannot be included in the
10101
01010
in this scene, it seems as though there is a global source of items for each knapsack..
so the maxProfit wil be summation of all items included for each knapsack?

:(

Sorry . im trying to understand the definition of the solution. on your referred article, it says that 'it seeks to find that subset which satisfies a constraint in total weight' so in this thread's given dataset, the solution is still 1 subset?.. im newbie. and kinda stupid because i don't really understand it (maybe because its also my second language.. still trying to learn eng). sorry