Knapsack problem constraints help

  • Thread starter Thread starter fishturtle1
  • Start date Start date
  • Tags Tags
    Constraints
Click For Summary

Homework Help Overview

The discussion revolves around the Knapsack Problem, specifically focusing on constraints related to item selection for a backpacker's knapsack with volume and weight limits. The problem includes specific items with conditional values based on the inclusion of other items, which adds complexity to the optimization model.

Discussion Character

  • Mixed

Approaches and Questions Raised

  • Participants explore the formulation of constraints for the optimization problem, questioning the validity of certain equations and the implications of including or excluding specific items. There is discussion on whether multiple identical items can be included and how to express the value of items based on dependencies.

Discussion Status

There is an ongoing examination of the constraints proposed by the original poster, with some participants suggesting modifications and clarifications. The conversation reflects a collaborative effort to refine the problem setup without reaching a definitive conclusion.

Contextual Notes

Participants note the importance of clearly defining whether certain constraints allow for the inclusion of zero items and the implications of treating item values as constants versus variables. There is also mention of homework guidelines that may restrict the approach to finding solutions.

fishturtle1
Messages
393
Reaction score
82

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:
Physics news on Phys.org
fishturtle1 said:
##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.
fishturtle1 said:
##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.
 
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?
 
scottdave said:
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.
 
mfb said:
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.
 
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   Reactions: scottdave and fishturtle1
mfb said:
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##
 
fishturtle1 said:
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
OP is not supposed to find a solution to an actual problem anyway.
 
  • #11
fishturtle1 said:

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   Reactions: fishturtle1
  • #12
Ray Vickson said:
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.