Category Archives: Appendix- Mathematical Programming

Traveling Salesman Polytope Non-Adjacency

This may be the hardest problem description to understand that I’ve done.  I’m still not sure I really understand the problem, let alone the reduction.  So I apologize in advance for what you’re about to read.

The problem: Traveling Salesman Polytope Non-Adjacency.  This is problem MP8 in the appendix.

The description:  I’ve got a lot of this definition from the paper by Papadimitriou that has the reduction.  We’ll take it slowly:

Suppose we have a complete, undirected, weighted graph G=(V, E).  Let |V| = n.  This means that |E| = n*(n-1)/2.  We can number these edges, and then denote whether a potential tour is “using” an edge or not by a 0/1 vector.  So a vector (0,1,1,0,1,0) means that the solution we’re considering uses edges 2,3, and 5.  (This may or may not be a legal tour).  Each legal Hamiltonian Cycle can be represented as one of these vectors.  This gives us a set of 0/1 vectors.  We can think of these vectors as points in Rn.  We then want to talk about the convex hull of these points.

Two vertices on this convex hull are defined to be “adjacent” if they are connected by an edge on the convex hull.

So, the problem asks: Given two Hamiltonian Cycles on G, are they non-adjacent on this convex hull?

(Yes, it’s weird that the problem never uses the distances between the vertices.  I think this is really “Hamiltonian Cycle Polytope Non-Adjacency”.  In fact, I think this makes more sense because the graph that is built in the reduction is not a complete graph)

Example: This is pretty hard to visualize, so let’s start with a simple graph:

Let’s list edges in alphabetical order in our vector. The vector will have 6 elements in alphabetical order: ab, ac, ad, bc, bd, cd

So the tours we have are:

  • ABCDA, represented as (1,0,1,1,0,1)
  • ABDCA, represented as (1,1,0,0,1,1)
  • ACBDA, represented as (0,1,1,1,1,0)

..and that’s really it.  All of the other tours are either reversals of the above (such as ADCBA), or an above tour shifted by starting at a different point (like BCDAB), which use the same edges and thus create the same vectors.

So, we are left with 3 points in 6-dimensional space.  Obviously, any 2 points in that space are adjacent.  If we start with a graph with 5 vertices:

we have 10 dimensions to our vector, for the edges ab, ac, ad, ae, bc, bd, be, cd, ce, and de. We also have 12 tour vectors. I won’t list them all, but for example, the tour ABCDEA would be represented by (1,0,0,1,1,0,0,1,0,1).  In this case, the need to define what the convex hull of those points are, and whether 2 tours are adjacent becomes harder to see.

Reduction:

Papadimitriou uses 3SAT.  So we’re given a set of m clauses over p variables, and we need to build a graph and two tours.  The graph he builds is made up of a series of widgets.  These widgets are designed to force certain edges to be used if the graph is to have a Hamiltonian Cycle.  The idea is that he constructs the widgets in a way that we can construct 2 cycles that are non-adjacent if and only if the formula was satisfiable.  So for example, here is his “exclusive or” subgraph (p. 316 of the paper):

In this subgraph, a Hamiltonian Cycle needs to go from u to u’ or v to v’ (it can’t do both, it can’t do neither).  By constructing ever-more complicated versions of this, he builds a graph.  Here’s how it looks for the formula B = (x1, x2, x3) ∧ (x1, x2, ~x3) ∧ (~x1, ~x2, ~x3) (p. 319 of the paper):

The bold lines in the figure above correspond to setting all variables to true.  There is also a circuit corresponding to making all variables false.  (We assume this satisfies at least one clause because if it didn’t, we have a Satisfiability instance where each clause has at least one positive literal, which is trivially satisfiable).  It turns out that every edge in this graph belongs to at least one of these two cycles.  For these two cycles to not be adjacent in the polytope, there needs to be some other circuit “between” them.  This circuit corresponds to a legal way to set all of the variables to make all clauses true.  If no such circuit exists (and the formula is not satisfiable), then the 2 tours are adjacent.

Difficulty: 9.  I can see what he’s doing, but I really have trouble following how he gets there.  Part of the difficulty with this problem is that it’s such a weird non-intuitive (to me) definition of “adjacency”.  I wonder if there is a better one out there.  Another source of difficulty is what I think of as confusion between TSP and HC.  The crazy widgets don’t help either.

K-Relevancy

Back from my trip, we pick up with a problem where I couldn’t find a simple reduction, and man I wish I could.

The problem: K-Relevancy.  This is problem MP7 in the appendix.

The description: Given a set X of (\bar{x}, b) pairs, where \bar{x} is an m-tuple of integers, and a positive integer K, can I find a subset X’ of X, of K or less elements, such that any m-tuple \bar{y} that solves \bar{x} \cdot \bar{y} \leq b for all \bar{x} in X’, also solves it for all pairs in X?

Example: Here’s a pretty easy example that I think gets the point across:

X1: 2y1 + 2y2  \leq 5

X2: 4y1 + 4y2 \leq 10

Obviously, any values of y1 and y2 that make the first inequality true also make the second one true.

Here’s a slightly more interesting one:

X1: y1+y2 \leq 10

X2: y1-y2 \leq 10

X3 y1 \leq 10

X1 defines a half-plane where points like y1=100, y2=-100 exist.  But X2 defines an intersecting halfplane, where the only legal solutions have y1 \leq 10.  So the third equation isn’t necessary.

Reduction: G&J say that this reduces from X3C, but I can’t see how.  They refer me to a technical report by Reiss and Dobkin, which I found published by Dobkin and Reiss in Theoretical Computer Science.  But the thrust of this paper is to talk about how Linear Programming is kind of in its own complexity class, and to create a notion of “LP-Completeness”.  They show that if K = |X|-1, relevancy is the same as Linear Programming.  They also say that you can extend the idea that Johnson and Preparata use in the Hemisphere problem to other problems like Relevancy.  (Hemisphere is LP-Complete if we want to know if all or no points are in the Hemisphere).

The problem I have with that is that Johnson and Preparate’s reduction used Max-2-Sat, not X3C, and the reduction there seems pretty tailored towards the Hemisphere problem, and I don’t see an easy way to get from there to our problem. So I don’t really know what they mean.

But, Dobkin and Reiss do show how Hemisphere and Relevancy relate in the LP-Complete world, so we can follow that chain of reductions:

  • So, Hemisphere is equivalent to “Origin Interior” (given a set of points on the unit sphere, is the origin outside the convex hull of those points?), which they claim is the same problem restated.
  • Origin Interior is equivalent to “Extreme point” (given a set of points on the unit sphere and any point, is that point outside the convex hull of our pointset?), which pretty clearly is the same problem.
  • Extreme point is equivalent to “Hyperplane Halfplane Intersection” (given a set of half-spaces, and a hyperplane, does our hyperplane intersect the intersection of all of the halfspaces?).  They say this is true based on the “geometric duality concept”.
  • Hyperplane Halfplane Intersection is just a geometric interpretation of Relevancy, so those problems are equivalent.

I think that the arguments that show that these problems are all equivalent to LP will also work as reductions in our NP-Complete world.  But man, I really want to know why G&J said this reduction was from X3C, and whether an easy reduction from there exists.

Difficulty: 8, but I hope something easier exists.

Open Hemisphere

I’m going to be out of town for the next 2 weeks, so we’ll be going on a bit of a hiatus.

The problem: Open Hemisphere.  This is problem MP6 in the appendix.

The description: Given a set X of m-tuples of integers, and a positive number K, can we find an m-tuple  \bar{y} of rationals such that at least K of the m-tuples, when multiplied by \bar{y}, are at least 0?

Example: Suppose our tuples were:

  1. {1,1,1}
  2. {-1,-1,-1}
  3. {1,-1,1}
  4. {-1,1,-1}

If K = 2, we can choose \bar{y} to be {1,0,1}.  This multiplied by tuples 1 and 3 would be positive (with a value of 2).  We could have also chosen {-1,0,-1} to make the multiplication with tuples 2 and 4 positive.  I don’t think there is a legal \bar{y} if K=3.  There certainly isn’t if K=4 (you can’t make both tuple 1 and tuple 2 positive simultaneously).

Reduction: Johnson and Preparata use Max-2-Sat.   So we’re given a 2-Sat instance with s clauses, m variables, and a target N, the number of clauses we need to satisfy.  Let t = \lceil log_{2}(ms+1) \rceil and d = m+1+3t.  We will create d-tuples as follows.

  • “A” vectors: 23t copies of “positive” and “negative” vectors for each variable.  So variable i has vectors Ai = i-1 0’s, followed by 1 followed by m-i 0’s, followed by 1, followed by each permutation of 1 or -1 of length 3t.  ~Ai is similar, except the first 1 is replaced by a -1.
  • 2t “B” vectors for each variable (positive and negative).  So variable i has vectors Bi = i-1 0’s, followed by 4, followed by m-i 0’s followed y -2, followed by 2t 0’s, followed by each permutation of 1 or -1 of length t.  ~Bi is similar, but the 4 is replaced by -4.
  • One “C” vector for each clause.  If the clause had variables xi and xj, the clause would be: i-1 0’s followed by 4*the sign of xi, followed by j-1 0’s, followed by 4* the sign of xj followed by m-j 0’s followed by 1 followed by 3t 0’s.

By “the sign of xi“, I mean 1 if xi shows up as a positive literal, and -1 if it shows up as a negated literal.  It’s also worth noting that since t is based on the log of the input size, creating a number of vectors that is exponential in t still keeps the input size of our hemisphere instance polynomial.

Our K will be 2m+23t+m*2t+N.  (All of the A tuples, half of the B tuples, and N of the C tuples)

If we have a Max-2-Sat solution, here’s how you build the \bar{y}:

  • Positions 1-m correspond to variables.  If the variable is set positively, put a 1 in that position.  If the variable is set negatively, put a -1 in that position.
  • Put a 1.5 in position m+1
  • Put a 0 everywhere else.

This will multiply positively with all A tuples, half of the B tuples, and  N of the C tuples.

If we have a hemisphere solution, it has to fit certain criteria:

  • At least 2m*23t-22t of the A vectors multiply positivly with our solution (this is how many you need even if all B and C vectors multiply positively)
  • Position m+1 of the solution vector is > 0 (otherwise not enough A vectors are positive)
  • At most 2t Bi vectors multiply positively with our solution for each variable i.  (Position m+1 of the B vector is the -2.  If we have more than 2t Bi vectors we’ll set position m+1 in the solution vector negative)
  • Position m+1 of the solution vector is  at least as big as the sum of the absolute values of the values in positions m+2+2t through m+1 + 3 (If it wasn’t, the limit on the B vectors would mean we wouldn’t be able to take enough A vectors to get a hemisphere solution)
  • Each value in the first m positions in the solution vector is at least as big as the absolute value of (position m+1) /4  (You can prove this by contradiction using algebra).  Importantly, this means those values can’t can’t be 0.
  • We must have at least N C tuples that multiply positively with the solution vector (given the limits on A and B).

Using these facts, we can find the ways to set the variables: Each of the first m positions in the solution vector correspond to a variable.  If the value at that position is positive, set it to true, if the value is negative, set it to false.  This will satisfy the N clauses that correspond to the C tuples that were made positive in the hemisphere solution.

Difficulty: 9.  Notice how much work has to happen to get around the fact that the hemisphere could have rational answers.  Also, notice how many tuples you need to get this reduction.  I’m also not 100% convinced yet that there isn’t a hole in the various claims about how the hemisphere solution has to behave that allows some weird combination of values to fall through.

Minimum Weight Solution to Linear Equations

After the last few problems in this chapter were so hard, I was worried when I saw this was a “no reference provided” problem.  Luckily, I think I was able to figure the reduction out.

The problem: Minimum Weight Solution to Linear Equations.  This is problem MP5 in the appendix.

The description: Given a set of equations X, where each equation consists of an m-tuple of integers \bar{x} and an integer b.  We’re also given a positive integer K \leq m.  Can we find an m-tuple \bar{y} with rational entries such that at most K of y’s entries are non-zero and \bar{x} \cdot \bar{y} = b for all equations in X?

Example: I find it easier to write the equations out.  Suppose we have:

3y1+2y2+y3 = 7

4y1+3y2 + 7y3 = 10

If we set K=2, that means that only 2 of the 3 y values in the solution can be non-zero (so we need at least one 0).  Choosing y1=1, y2=2, y3=0 works.

Reduction: G&J don’t give the reduction, but in the comments, they say it’s polynomial if K=m.  That plus the use of “X” (the set in X3C) made me think that the reduction from X3C had the \bar{y} be related to the sets chosen from C.

So our X3C instance has a set X of 3q elements, and a set C of collections of 3-element subsets of X.  We’ll set m (the size of the tuples in our equations) to |C|.  Our equation set X’ will have 3q equations.  Each equation will correspond to an element in X, and the positions of its \bar{x} vector will correspond to the sets in C.  Each vector element will have a 1 in the positions where the element exists in the set in C, and 0 otherwise.  Our b value will be 1 for each equation, and K will be q (we want q of the variables to be 1)

So, for example, if X = {1,2,3,4,5,6}, and C was {1,2,3}, {4,5,6}, {2,4,5}, we would have 6 equations:

y1 = 1   (the equation for element 1)

y1 + y3 = 1 (the equation for element 2, which appears in sets 1 and 3)

y1 = 1 (the equation for element 3)

y2+y3 = 1 (the equation for element 4)

y2+y3 = 1 (the equation for element 5)

y2 = 1 (the equation for element 6)

Since this is a small and simple X3C instance, there is a lot of redundancy in the equations.  But hopefully it’s clear how it relates to the initial instance: We’re asking if we can create a 0/1 tuple that solves each of these equations (fractional values for the y variables won’t work because if we do that we will have more than K non-zero variable values).  Setting a variable to 1 means “choosing” that set in the X3C instance.  Having the equation be true means that we have found exactly one set in C’ holding that element of X.  Having all of the equations be true means we have found a C’ that holds exactly one copy of all elements in X (thus solving the X3C instance).

Difficulty: 5, assuming I didn’t mess anything up.  It’s very tempting to set up the equations in the wrong way (for example, making there be |C| equations of 3q-tuples)

Feasible Basis Extension

The paper for this one is one of the older ones I have- it was published in 1972, but they say it was first submitted in 1970, which would be before Cook’s paper came out.

The problem: Feasible Basis Extension.  This is problem MP4 in the appendix.

The description: Given an mxn matrix A of integers (m < n), and a column vector  \bar{a} of size m, and a subset S of <m columns of A, can  we find a non-singular (i.e., invertible) mxm  submatrix B of A, such that:

  • B contains all of the columns of S, and
  • All of the elements of the vector \bar{x}, where \bar{x} = B-1 * \bar{a} are  \geq 0?

Example: I’ll try to keep the matrix calculations simple.  Suppose A was:

1 2 3
4 5 6

\bar{a} was:

\frac{1}{6}
\frac{1}{2}

and S was just the second column.  Then B has to be a 2×2 submatrix of A that includes the second column, for example:

1 2
4 5

The inverse of this is:

\frac{-5}{3} \frac{2}{3}
\frac{4}{3} \frac{-1}{3}

Which, if we multiply by \bar{a}, gives us:

\frac{1}{18}
\frac{1}{18}

Reduction:

The paper by Murty is from 1972, so doesn’t really follow the same reduction structure we’re used to.  The basic idea is to start with an instance of TSP, and realize that we can write a tour as an nxn matrix X where xij = 1 if the tour goes from city i to city j, and 0 otherwise.  (This is basically a way of taking a permutation of the n cities, and stretching it out to an nxn 0-1 matrix).  We can then write the TSP problem as a set of constraints: Each row in the solution sums to exactly 1, each column in the solution sums to exactly 1, and all entries are \geq 0.  We are trying to minimize the cost of all of the 1 entries in the solution.   We can get the decision problem by adding a new constraint: That the costs of all of the entries is \leq the K from the TSP instance.

He then shows that if this system has a feasible basis, it must be a tour that satisfies the TSP instance.  The proof involves lemmas that talk about the “convex polytope” of the constraints, which I think needs some pretty sophisticated linear programming familiarity to follow.

Difficulty: 8.  Maybe less if you are teaching a mathematical programming class- I don’t think the ideas are hard, but I do think they’re not likely to come up in an algorithms class.

 

Cost-Parametric Linear Programming

This is a hard reduction that I’m not sure I understand.  I’m sure if I was better at vector operations, I’d be more able to figure it out.

The problem: Cost-Parametric Linear Programming.  This is problem MP3 in the appendix.

The description: Given a set of integer constraints (\bar{x},b) as in Integer Programming, (except that the inequalities are \geq instead of \leq for some reason, but we can always multiply by -1 to flip the constraints) and a set J that is a subset of  indices of the variables in \bar{x}.  Can we find an m-tuple \bar{c} with rational values such that \sqrt{\bar{c} \cdot \bar{c} }\leq q and for all feasible non-negative m-tuples \bar{y} that satisfy the constraints,  the minimum of \sum_{j \in J}( c_j * y_j) > \frac{1}{2}* max \{|c_j| : j \in J\} +\sum_{j \in J} min \{0,c_j\}

Example: Ok, here’s a pretty simple situation.  Suppose we have 3 variables, with constraints:

x_1 + x_2 + x+3 \leq 1  (Or, technically, -x_1 - x_2 - x_3 \geq -1)

x_1 \geq .3

x_2 \geq .4

x_3 \geq .2

Now, suppose we choose a \bar{c} of (1,1,0} and a J of {1,2}.  So in this case, the minimum of \sum_{j \in J}( c_i * y_i) would be .3 + .4 = .7.  That needs to be more than \frac{1}{2}* max \{|c_j| : j \in J\} +\sum_{j \in J} min \{0,c_j\}  This comes out to .5 + 0, so it works.  So, with this \bar{c}, we need \sqrt{\bar{c} \cdot \bar{c} }\leq q , so a q > \sqrt{2} makes this solution correct.  There may be different values for \bar{c} that will also work on smaller q’s.

Reduction: G&J say that the reduction is from 3SAT, but I think the paper by Jersolow uses DNF Non-Tautology. Given a logical formula in DNF form, he builds a linear inequality system. All variables in formula become variables in the linear program.  For each clause, every variable has a constraint that it’s \leq 1.  (and, I think implicitly, \geq 0).  If the variable shows up in a literal positively, we add the constraint that it is \geq 1.  If it shows up negatively, we have a constraint that it’s \leq 0.  This means that we have a solution to the constraints if and only if we set the variables to the truth values that make the clause true.  (Remember, we have a DNF formula, so each clause is a conjunction- we need to make each variable true).

He then shows that the minimum way to solve the constraints (since it’s in DNF, that means making one clause true) is \leq \frac{1}{2}* max \{|c_j| : j \in 1..m \} +\sum_{j=1}^ m min \{0,c_j\} is true for all \bar{c} if and only if A is a tautology.  From there he goes on to show that our problem instance holds.

I’m pretty confused by the logic- especially seems it looks like he’s saying that his problem is true if and only if the original problem is a tautology, when non-tautology is what we’re supposed to be reducing from.

Difficulty 9.  This is a hard problem to understand,  and the reduction is hard to follow as well.   It’s very possible I’m not understanding something in the paper.

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: