Category Archives: Appendix- Mathematical Programming

Quadratic Programming

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 (\bar{x},b) of constraints, similar to those in Integer Programming, except the numbers can be rationals instead of integers.  Instead of the single objective vector \bar{c}, we’re also given a second vector \bar{d}, both of rationals.  Our objective bound B is also a rational.

Can we find a vector of rationals \bar{y} that meets all of the constraints and sets the objective function \sum_{i=1}^{m} (c_{i}*y_{i}^{2} + d_{i}*y_{i}) \geq B?

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

Maximize 2x_{1}^{2} + 3x_{1} + 4x_{2}^{2} + 5x_{2} such that:

x_{1} \geq 0

x_{2} \geq 0

x_{1} + x_{2} \leq 2

I’m pretty sure this has a trivial solution of x_{1} = 0 and  x_{2} = 2, 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= {s_{1}..s_{n}} and a bound M.  Our QP instance will be have the following objective function: \sum_{i=1}^{n} x_{i}*(x_{i}-1) + x_{i}*s).   Our constraints will be that each x_{i} has to be between 0 and 1 (inclusive) and also \sum_{i=1}^{n} x_{i}*s_{i} \leq M.  Our bound B will be equal to M.

The first half of the objective function makes its contribution to the sum negative if x_{i} 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 x_{i}. 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.

Integer Programming

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 (\bar{x},b), where \bar{x} is an m-tuple of integers, and b is an integer.  We’re also given an m-tuple \bar{c} and an integer B.

Can we find an m-tuple of integers \bar{y} such that:

  • \bar{x}*\bar{y} \leq b for each (\bar{x},b) pair
  • \bar{c}*\bar{y} \geq 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 \bar{x} and B make the objective function.  So, the set ((1,2,3,4),100) really corresponds to the constraint  1x 1+2x2+3x3+4x4 \leq 100.

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

Given constraints:

x1 + x2 \leq 5

10x1 + 6x2 \leq 45

Maximize 5x1 + 4x2 (Or, as a decision problem, can 5x1 + 4x2 be \geq 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.

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 pi and weight wi.  We’re given a knapsack capacity B and a goal profit K.

Our constraints will be:

x1*w1+… xn*wn \leq B  (keep the total weight at B or less)

xi \leq 1 for all i (I can take at most 1 of each item)

-1*xi \leq 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 \leq 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.

Protected: Knapsack

This content is password protected. To view it please enter your password below: