# 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
• The standard reduction is different than what is suggested in the post: it has indicator variables $x_{vi}$ meaning that vertex $v$ is assigned to position $i$ on the cycle, and then constraints to ensure that every vertex is assigned one position, every position is assigned one vertex, and $v$ and $w$ cannot be assign to respective positions $i$ and $i+1$ if there is no edge from $v$ to $w$. – Neal Young Aug 26 '18 at 19:08
• This paper proves that if you use just the variables you have defined, you will need exponentially many inequalities to formulate hamiltonian cycles. link.springer.com/article/10.1007/s10107-014-0855-0 – Austin Buchanan Aug 28 '18 at 22:28
• yo look up the travelling salesman problem – Karagounis Z Apr 30 at 4:11

## 3 Answers

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

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.)

• The above is known as the Miller-Tucker-Zemlin formulation of TSP. In practice, the following constraints, called subtour elimination constraints usually work better: If the solution produces a cycle of length $\ell<n$, then one may add the constraint that at most $\ell-1$ of the edges of the cycle are selected and recompute the solution. This gives rise to an exponential number of constraints but in practice the number of added subtour elimination constraints is often much lower. – Christian Komusiewicz Aug 28 '18 at 9:39
• @CKomus I'm aware of subtour constraints -- and that's a valuable thing to mention! :) -- I was just trying to address the original question of how to formulate with a (small) number of integer constraints. – Alex Meiburg Aug 28 '18 at 19:32
• Yes the main point of my comment was actually to point out the name MTZ as this may help for further reading. – Christian Komusiewicz Aug 28 '18 at 19:57

A way to formulate this into a linear program is in the following way:

Let e=(u,v) be an edge between two vertices

$$min\sum_{(u,v) \in E} x_{(u,v)}$$

$$\forall v \in V:\sum_{v \in V} x_{(u,v)} = 2$$

$$\forall S \subset V, S \not \in$$ {V,$$\varnothing$$} : $$\sum_{u \in S, v \not \in S} x_{(u,v)}\geq2$$

$$x_{u,v} \in$$ {0,1}

Explenation:

1. The goal is: $$min\sum_{(u,v) \in E} x_{(u,v)}$$

2. For every vertex v, it can have exactly two edges connecting it:$$\sum_{v \in V} x_{(u,v)} = 2$$.

3. The Hamiltonian cycle satisfies that the graph should be connected with at least 2 edges coming from S to $$\ \bar S$$ so the constraint is: $$\forall S \subset V, S \not \in V,\varnothing$$ : $$\sum_{u \in S, v \not \in S} x_{(u,v)}\geq2$$

4. $$x_{u,v} \in$$ {0,1} , give 1 to the variable representing the fact that the edge e=(u,v) is chosen the Hamiltonian cycle, 0 otherwise.