CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10
  1. #1
    Join Date
    Mar 2012
    Posts
    2

    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.

  2. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: 0/1 MultiDimensional Knapsack Problem

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

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

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    Join Date
    Mar 2012
    Posts
    2

    Re: 0/1 MultiDimensional Knapsack Problem

    Quote Originally Posted by BioPhysEngr View Post
    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.........

  4. #4
    Join Date
    Jan 2013
    Posts
    7

    Re: 0/1 MultiDimensional Knapsack Problem

    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 ?

  5. #5
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: 0/1 MultiDimensional Knapsack Problem

    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
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  6. #6
    Join Date
    Jan 2013
    Posts
    7

    Re: 0/1 MultiDimensional Knapsack Problem

    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

  7. #7
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: 0/1 MultiDimensional Knapsack Problem

    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?
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  8. #8
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    Re: 0/1 MultiDimensional Knapsack Problem

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

    http://openlibrary.org/books/OL18082...apsack_problem
    Best Regards,

    BioPhysEngr
    http://blog.biophysengr.net
    --
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  9. #9
    Join Date
    Jan 2013
    Posts
    7

    Re: 0/1 MultiDimensional Knapsack 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?


  10. #10
    Join Date
    Jan 2013
    Posts
    7

    Re: 0/1 MultiDimensional Knapsack Problem

    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

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured