# Hamiltonian Cycle as an integer linear programming problem

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!

-
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

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.

-

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.

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