Knapsack problem constraints help

[fishturtle1]

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?

 

[mfb]

$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.

 

[scottdave]

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?

 

[fishturtle1]

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.

 

[fishturtle1]

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.

 

[mfb]

Ah...there is a better option. You can express the value of item 1 using c₁ and x₄. Then you can bring 1 without 4, but it has zero value - exactly as the problem statement wants.

 

[fishturtle1]

Ah...there is a better option. You can express the value of item 1 using c₁ and x₄. 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$

 

[mfb]

Right.

 

[StoneTemplePython]

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?

 

[mfb]

OP is not supposed to find a solution to an actual problem anyway.

 

[Ray Vickson]

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$).

 

[fishturtle1]

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.