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

**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}+2x_{2}+3x_{3}+4x_{4} 100.

Here is a simple Integer Programming problem written in the way we’re probably more used to seeing:

Given constraints:

x_{1} + x_{2} 5

10x_{1} + 6x_{2} 45

Maximize 5x_{1} + 4x_{2 } (Or, as a decision problem, can 5x_{1} + 4x_{2} be 23?

The answer is yes: If x_{1}=3 and x_{2} = 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 x_{1}=3.75 and x_{2}=1.25.

**Reduction: **Karp’s paper uses 3SAT, which is fine, but it’s hard to see how the objective function works there. I think a much more natural reduction is from Knapsack.

So we’re given a set of n items, each item i has a profit p_{i} and weight w_{i}. We’re given a knapsack capacity B and a goal profit K.

Our constraints will be:

x_{1}*w_{1}+… x_{n}*w_{n} B (keep the total weight at B or less)

x_{i} 1 for all i (I can take at most 1 of each item)

-1*x_{i} 0 for all i (Each x_{i} has to be at least 0)

The last sets of constraints force each x_{i} variable to be either 0 or 1.

The objective function asks:

p_{1}*x_{1} + … + p_{n}*x_{n} 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.