On to a new section of the appendix!
The problem: Integer Programming. This is problem MP1 in the appendix.
The description: Given a set of X of pairs (,b), where is an m-tuple of integers, and b is an integer. We’re also given an m-tuple and an integer B.
Can we find an m-tuple of integers such that:
- b for each (,b) pair
Example: The definition above kind of hides the way we commonly think of integer (or linear) programming. The X set is the set of constraints, and the and B make the objective function. So, the set ((1,2,3,4),100) really corresponds to the constraint 1x 1+2x2+3x3+4x4 100.
Here is a simple Integer Programming problem written in the way we’re probably more used to seeing:
x1 + x2 5
10x1 + 6x2 45
Maximize 5x1 + 4x2 (Or, as a decision problem, can 5x1 + 4x2 be 23?
The answer is yes: If x1=3 and x2 = 2, we satisfy both constraints and get an objective value of 23.
Notice that if we allowed non-integer values for our variables, we would have a linear program, and could get to an objective value of 23.75 by setting x1=3.75 and x2=1.25.
So we’re given a set of n items, each item i has a profit pi and weight wi. We’re given a knapsack capacity B and a goal profit K.
Our constraints will be:
x1*w1+… xn*wn B (keep the total weight at B or less)
xi 1 for all i (I can take at most 1 of each item)
-1*xi 0 for all i (Each xi has to be at least 0)
The last sets of constraints force each xi variable to be either 0 or 1.
The objective function asks:
p1*x1 + … + pn*xn B?
I think it’s pretty clear that this is exactly the rules for Knapsack written as an Integer Programming problem.
Difficulty: 3. I think this might be too easy for a homework problem because the proof part of the reduction (Knapsack says “yes” if and only if IP says “yes”) is trivial. But the need for the last set of constraints (that each variable is >=0, written as a <= equation) is a fun wrinkle that will mess up some people.