Hamiltonian Cycle as an integer linear programming problem

Question

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!

Answer 1

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.

Answer 2

I know this is old, but--

First, make this a 'directed' cycle: only one $e_{ij}$ is true on each vertex, so that $v_i = 1$. This will enable a sort of useful indexing on the cycle.

Next, create additional variables $c_i$ as counters for what the "index" in the cycle of vertex $i$ is. Arbitrarily, we'll call vertex 0 to be index zero:

$$c_0 = 0$$

Then index 1 will be whatever follows it, and so on. To enforce this: if there's no edge from vertex $i$ and $j$, then they can be whatever they want; if they do share an edge, then $c_j$ must be $c_i + 1$. That's equivalent to saying that $c_j \le c_i + 1$ and $c_j \ge c_i + 1$. We can combine these two cases into

$$c_j \le (c_i+1) - n(e_{ij} - 1)$$ $$c_j \ge (c_i+1) + n(e_{ij} - 1)$$

So that when $e_{ij}=0$ these constraints do nothing, and when it's 1 they're tight. If the vertices are numbered $0$ to $n-1$, then we have such a constraint for all $i \in [0,n-1]$ and all $j \in [1,n-1]$, with $i\neq j$. (Whatever vertex $k$ has $c_k = n-1$ will necessarily be the only capable of feeding an edge back to vertex 0.)