Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I'm trying to do reduce Hamiltonian Cycle to integer linear programming. Here's my idea:

Create variables $e_{ij}$ for every edge $(i,j)$ in the graph. Require each $$e_{ij}\in \{0,1\}$$. Create additional variables $v_i$ for every vertex $i$ in the graph, and define $$v_i = \sum_{\{j:(i,j)\in E\}}e_{ij}$$ (so that $v_i$ counts how many edges are connected to vertex $i$). Specify an integer linear program where the goal is to maximize $\sum_{(i,j)\in E}e_{ij}$ subject to the constraint that $v_i = 2$ for all $i\in V$.

As I see it, this should find a solution (if one exists) of exactly $n$ edges in the graph which form cycles. However, there's no guarantee that these cycles are a single tour of the graph. For example, consider a complete graph of 6 vertices. The above problem might find a "solution" which consists of two cycles each of 3 vertices, instead of finding the correct solution of a single cycle which includes all vertices. In short, the sticking point is requiring that the linear program finds only one cycle. Is there a way to enforce a limit on the number of cycles found via a linear programming constraint? I'm stumped on this.

Thanks!

share|improve this question
1  
This is what is implemented in Sage : hal.archives-ouvertes.fr/docs/00/50/49/14/PDF/… And here is the source code (two versions of this LP) : hg.sagemath.org/sage-main/file/5714ed3eab6a/sage/graphs/… –  Nathann Cohen Feb 26 '13 at 10:18

2 Answers 2

I'm not certain of this question's applicability to cstheory.SE (since this is a well known example given in many introductory operations research classes), but regardless it is indeed possible to express connectivity using linear programming constraints and, for the most part, you're on the right track.

The direct way to enforce connectivity, requiring an exponential number of constraints, is to require that for every set $S \subset V$ not equal to either $V$ or $\emptyset$, the tour must contain at least two edges connecting vertices in $S$ to $V \setminus S$. This set of constraints, or slight modifications thereof, is key in the usual definition of the Held-Karp LP relaxation for TSP (however, the polynomial-time solvability of this LP is generally shown by providing a separation oracle).

To get a polynomial-size LP relaxation, one can use the LP given in the TSP Wikipedia article. Intuitively, what this program is doing is introducing new variables that maintain each vertex's position in some ordering of the Hamiltonian path, and uses the fact that there must be a discontinuity among the ordering in a subtour to enforce that some difference will necessarily be too large. Note that the provided LP is for the directed Hamiltonian cycle problem, but can be modified to accommodate undirected HamPath with little difficulty.

share|improve this answer

Describing connectivity in integer programming is not as straightforward as the rest of the reduction, I think.

However, it is quite clean to reduce HAMCYCLE to SAT (e.g. here), and it is very clean to reduce SAT to integer programming. I think you will end up with a system that is not all that complicated. Perhaps it is worth doing so than busting your head over a direct reduction.

share|improve this answer
    
The link posted is broken, do you have a updated reference? –  Hooked May 16 at 18:16
    
I am unable to find it yet, when I will, I'll post. –  Shaull May 16 at 20:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.