Moving along in the Mathematical Programming section.

**The problem: **Quadratic Programming. This is problem MP2 in the appendix.

**The description**: Given a set of pairs (,b) of constraints, similar to those in Integer Programming, except the numbers can be rationals instead of integers. Instead of the single objective vector , we’re also given a second vector , both of rationals. Our objective bound B is also a rational.

Can we find a vector of rationals that meets all of the constraints and sets the objective function ?

**Example: **I’ll again try to write a simple example in a format closer to what I think is used in practice:

Maximize such that:

I’m pretty sure this has a trivial solution of and , for an objective score of 26.

**Reduction:** It’s worth mentioning that this is a “Not known to be in NP” problem, I think because the range of possible rational solutions is too large to nondeterministically guess. Sahni’s paper reduces from Sum of Subsets. So we’re given a set S= {} and a bound M. Our QP instance will be have the following objective function: . Our constraints will be that each has to be between 0 and 1 (inclusive) and also . Our bound B will be equal to M.

The first half of the objective function makes its contribution to the sum negative if is not 0 or 1 (and 0 if it is 0 or 1). So the only way to get the objective to exactly M is to choose 0/1 values for each . The second half of the objective function and the summation constraint force us to create a sum that is as large as possible but not larger than B. In this case the objective function value is the sum of the subset chosen, which is equal to B if and only if we have a SOS solution.

**Difficulty: **5. The hack to make fractional variable assignments negative is very cool, and easy to explain, but hard to find on your own. I also think that worrying about quadratics and fractional values for your variables makes this problem harder to handle.