Knapsack problem constraints help

  • #1
334
44

Homework Statement


8 (a) (The Knapsack Problem) A backpacker's knapsack has a volume of V in.^3 and can hold up to W lb of gear. The backpacker has a choice of ##n## items to carry in it, with the ##i##th item requiring ##a_i## in.^3 of space, weighing ##w_i## lb, and providing ##c_i## units of value for the trip. What items should be taken in the knapsack?

(b) Refine part (a) to include the following considerations: Item 1, a can of tuna fish, Item 2, a can of corn, and Item 3, a can of stew, have no value unless Item 4 the can opener, is taken; and only one snack, either Item 5, potato chips, or Item 6, unpopped popcorn, is to go. Of course Items 2,3, and 6 all use Item 7, the cooking pot.

Homework Equations




The Attempt at a Solution


Let ##x_i = 1## if item i is brought, and ##x_i = 0## if item i is not brought.

a)

Maximize ##c_1x_1 + c_2x_2 + . . . + c_nx_n##
subject to
##a_1x_1 + a_2x_2 + . . . + a_nx_n \le V##
##w_1x_1 + w_2x_2 + . . . + w_nx_n \le W##
##0 \le x_i \le 1## and ##x_i## is integral.
##c_i, a_i, w_i \ge 0##
b)

Maximize ##c_1x_1 + c_2x_2 + . . . + c_nx_n##
subject to
##a_1x_1 + a_2x_2 + . . . + a_nx_n \le V##
##w_1x_1 + w_2x_2 + . . . + w_nx_n \le W##
##c_1 + c_2 + c_3 = (c_1 + c_2 + c_3)x_4## (if item 4 is not brought, then these c's should have 0 value)
##x_5 + x_6 \le 1##
##x_2 + x_3 + x_6 \le 3x_7## (if item 7 is not brought, then none of these items are brought)

##0 \le x_i \le 1##, ##x_i## is integral.
##c_i, a_i, w_i \ge 0##

My question is, for part b are my constraints correct?
 
Last edited:

Answers and Replies

  • #2
35,635
12,181
##c_1 + c_2 + c_3 = (c_1 + c_2 + c_3)x_4## (if item 4 is not brought, then these c's should have 0 value)
That equation is only true if ##x_4=1 ##or ##c_1 + c_2 + c_3 = 0##. The ##c_i## are given constants and you can't expect them to be zero. Your equation forces you to take the can opener.
You can use the same approach as for the cooking pot here, for the maximization there is no point in bringing worthless items anyway.
##c_i, a_i, w_i \ge 0##
Technically you don't know that. It is also not necessary to specify as these values are given anyway.
 
  • #3
scottdave
Science Advisor
Homework Helper
Insights Author
1,814
778
It is not clear to me from your statement if more than 1 of each item can be brought. Where do you get the list of values and weights and volumes?
 
  • #4
334
44
It is not clear to me from your statement if more than 1 of each item can be brought. Where do you get the list of values and weights and volumes?
I think if say.. I brought 2 identical toothbrushes, then they would just count as 2 separate items with the same weight/volume/value. In total we get ##n## items, but I don't think they have to be unique. The values/weights/volumes aren't specified.
 
  • #5
334
44
That equation is only true if ##x_4=1 ##or ##c_1 + c_2 + c_3 = 0##. The ##c_i## are given constants and you can't expect them to be zero. Your equation forces you to take the can opener.
You can use the same approach as for the cooking pot here, for the maximization there is no point in bringing worthless items anyway.Technically you don't know that. It is also not necessary to specify as these values are given anyway.
Ok so the constraint would be ##x_1 + x_2 + x_3 \le 3x_4## This means if we don't bring the can opener, then ##x_4 = 0##. Therefore ##x_1, x_2, x_3 = 0##. I was hesitant to use this because I thought there would be cases where we brought the unopennable items without the can opener, so their value would be 0, but we'd still have to account for their weight/volume. But I see from your comment, that would be redundant so we don't need to consider that.
 
  • #6
35,635
12,181
Ah...there is a better option. You can express the value of item 1 using c1 and x4. Then you can bring 1 without 4, but it has zero value - exactly as the problem statement wants.
 
  • Like
Likes scottdave and fishturtle1
  • #7
334
44
Ah...there is a better option. You can express the value of item 1 using c1 and x4. Then you can bring 1 without 4, but it has zero value - exactly as the problem statement wants.
That would mean changing the objective function to
Maximize ##x_4x_1c_1 + x_4x_2c_2 + x_4x_3c_3 + x_4c_4 + x_5c_5 + . . . + x_nc_n##
 
  • #9
StoneTemplePython
Science Advisor
Gold Member
1,203
596
That would mean changing the objective function to
Maximize ##x_4x_1c_1 + x_4x_2c_2 + x_4x_3c_3 + x_4c_4 + x_5c_5 + . . . + x_nc_n##

This is a quadratic program over an integer domain. Solvers exist for this (e.g. Gurobi) but this is considerably more advanced than even a linear program over an integer domain. Are you sure you want to model it this way?
 
  • #10
35,635
12,181
OP is not supposed to find a solution to an actual problem anyway.
 
  • #11
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722

Homework Statement


8 (a) (The Knapsack Problem) A backpacker's knapsack has a volume of V in.^3 and can hold up to W lb of gear. The backpacker has a choice of ##n## items to carry in it, with the ##i##th item requiring ##a_i## in.^3 of space, weighing ##w_i## lb, and providing ##c_i## units of value for the trip. What items should be taken in the knapsack?

(b) Refine part (a) to include the following considerations: Item 1, a can of tuna fish, Item 2, a can of corn, and Item 3, a can of stew, have no value unless Item 4 the can opener, is taken; and only one snack, either Item 5, potato chips, or Item 6, unpopped popcorn, is to go. Of course Items 2,3, and 6 all use Item 7, the cooking pot.

Homework Equations




The Attempt at a Solution


Let ##x_i = 1## if item i is brought, and ##x_i = 0## if item i is not brought.


b)
Maximize ##c_1x_1 + c_2x_2 + . . . + c_nx_n##
subject to
##a_1x_1 + a_2x_2 + . . . + a_nx_n \le V##
##w_1x_1 + w_2x_2 + . . . + w_nx_n \le W##
##c_1 + c_2 + c_3 = (c_1 + c_2 + c_3)x_4## (if item 4 is not brought, then these c's should have 0 value)
##x_5 + x_6 \le 1##
##x_2 + x_3 + x_6 \le 3x_7## (if item 7 is not brought, then none of these items are brought)

##0 \le x_i \le 1##, ##x_i## is integral.
##c_i, a_i, w_i \ge 0##

My question is, for part b are my constraints correct?

Just as a matter of form: do not include the statement ##c_i, a_i, w_i \ge 0## within the scope of the model input itself: doing so makes it look like you are regarding the ##c_i##, ##a_i## and ##w_i## as additional variables in the optimization. In fact, they are not "variables" at all; they are given as input data supplied from outside the model itself.

Next: your constraint ##x_5 + x_6 \le 1## allows both ##x_5 = 0## and ##x_6 = 0##, which is perfectly OK if your interpretation is that you can have at most one snack. If you must include exactly one snack, replace that constraint by ##x_5 + x_6 = 1##.

Finally, in some books and papers the constraint "##0 \le x_i \le 1##, ##x_i## is integral" would be simply "##x_i = 0,1##" or "##x_i## binary" (and, of course, you should specify that it holds for all ##i##).
 
  • Like
Likes fishturtle1
  • #12
334
44
Just as a matter of form: do not include the statement ##c_i, a_i, w_i \ge 0## within the scope of the model input itself: doing so makes it look like you are regarding the ##c_i##, ##a_i## and ##w_i## as additional variables in the optimization. In fact, they are not "variables" at all; they are given as input data supplied from outside the model itself.

Next: your constraint ##x_5 + x_6 \le 1## allows both ##x_5 = 0## and ##x_6 = 0##, which is perfectly OK if your interpretation is that you can have at most one snack. If you must include exactly one snack, replace that constraint by ##x_5 + x_6 = 1##.

Finally, in some books and papers the constraint "##0 \le x_i \le 1##, ##x_i## is integral" would be simply "##x_i = 0,1##" or "##x_i## binary" (and, of course, you should specify that it holds for all ##i##).
This all makes sense, ill keep it in mind on the rest of this chapter. Also i'll probably make a note next to the constraint to clarify that I think we can bring at most one snack. Thank you.
 

Related Threads on Knapsack problem constraints help

Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
5
Views
841
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
17
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
3K
Top