# 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/… Commented Feb 26, 2013 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$. Commented Aug 26, 2018 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 Commented Aug 28, 2018 at 22:28

## 4 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? Commented May 16, 2014 at 18:16
• I am unable to find it yet, when I will, I'll post. Commented May 16, 2014 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. Commented Aug 28, 2018 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. Commented Aug 28, 2018 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. Commented Aug 28, 2018 at 19:57

Here's a simple ILP that nobody has mentioned yet.

Given the undirected graph $$G=(V, E)$$, use binary variables $$\pi_{iv}$$ for $$(i, v)\in [n]\times V$$, where $$n=|V|$$. Variable $$\pi_{iv}$$ indicates whether vertex $$v$$ is the $$i$$th vertex on the cycle.

\begin{align} \sum_{v\in V} \pi_{iv} &{} = 1 && (i\in [n]) \\ \sum_{i=1}^n \pi_{iv} &{} = 1 && (v\in V) \\ \pi_{iu} + \pi_{i\oplus1,w} & {} \le 1 && (i\in[n], (u,w)\in V\times V\setminus E) \end{align} In the last constraint $$i\oplus 1$$ denotes $$i+1$$ if $$i\ne n$$, and otherwise $$1$$. The constraint ensures that a vertex $$u$$ is placed just before vertex $$w$$ only if there is an edge from $$u$$ to $$w$$.

I don't know whether this ILP is useful in practice.

Given edge weights, it can be augmented (by adding appropriate variables) to find a min-cost TSP.

• This is the one I "teach" as a reduction from Hamiltonian Cycle to SAT with the same variables. Typically we teach SAT to Hamilton Cycle when discussing NP-Completeness. I also wants to convey to students that SAT is a powerful problem because like ILP it can model constraints etc. Students find it a bit tricky to use extra variables to model constraints. Another good example is to reduce k-Color to SAT. Commented Apr 10 at 15:38

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.