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

<p>However, it is quite clean to reduce HAMCYCLE to SAT (e.g. <a href="https://web.archive.org/web/20130507102040/http://www.cs.toronto.edu/~philipp/pages/papers/DangerousReductions.pdf" rel="noreferrer">here</a>), 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.</p>

CC BY-SA 3.0
2014-05-16T18:16:34.057Z
The link posted is broken, do you have a updated reference?
Hooked
CC BY-SA 3.0
2014-05-16T20:52:01.360Z
I am unable to find it yet, when I will, I'll post.
Shaull
CC BY-SA 3.0
2013-02-26T08:05:24.277Z
2016-01-19T22:38:28.077Z
2016-01-19T22:38:28.077Z
Shaull
<p>Here's a simple ILP that nobody has mentioned yet.</p>
<p>Given the undirected graph <span class="math-container">$G=(V, E)$</span>,
use binary variables <span class="math-container">$\pi_{iv}$</span>
for <span class="math-container">$(i, v)\in [n]\times V$</span>, where <span class="math-container">$n=|V|$</span>.
Variable <span class="math-container">$\pi_{iv}$</span> indicates whether vertex <span class="math-container">$v$</span> is the <span class="math-container">$i$</span>th
vertex on the cycle.</p>
<p><span class="math-container">$$
\begin{align}
\sum_{v\in V} \pi_{iv} &amp;{} = 1 &amp;&amp; (i\in [n]) \\
\sum_{i=1}^n \pi_{iv} &amp;{} = 1 &amp;&amp; (v\in V) \\
\pi_{iu} + \pi_{i\oplus1,w} &amp; {} \le 1
&amp;&amp; (i\in[n], (u,w)\in V\times V\setminus E)
\end{align}
$$</span>
In the last constraint <span class="math-container">$i\oplus 1$</span> denotes <span class="math-container">$i+1$</span> if <span class="math-container">$i\ne n$</span>, and otherwise <span class="math-container">$1$</span>.
The constraint ensures that a vertex <span class="math-container">$u$</span> is placed just before vertex <span class="math-container">$w$</span> only if there is an edge from <span class="math-container">$u$</span> to <span class="math-container">$w$</span>.</p>
<p>I don't know whether this ILP is useful in practice.</p>
<p>Given edge weights, it can be augmented (by adding appropriate variables) to find a min-cost TSP.</p>

CC BY-SA 4.0
2024-04-10T15:38:59.210Z
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.
Chandra Chekuri
CC BY-SA 4.0
2024-04-10T13:29:11.130Z
2024-04-10T13:29:11.130Z
Neal Young
<p>I know this is old, but--</p>

<p>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.</p>

<p>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:</p>

<p>$$c_0 = 0$$</p>

<p>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</p>

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

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

CC BY-SA 4.0
2018-08-28T09:39:03.483Z
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
CC BY-SA 4.0
2018-08-28T19:32:24.390Z
@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
CC BY-SA 4.0
2018-08-28T19:57:02.417Z
Yes the main point of my comment was actually to point out the name MTZ as this may help for further reading.
Christian Komusiewicz
CC BY-SA 4.0
2018-08-26T17:25:14.920Z
2018-08-29T16:35:46.540Z
2018-08-29T16:35:46.540Z
Alex Meiburg
<p>A way to formulate this into a linear program is in the following way:</p>
<p>Let e=(u,v) be an edge between two vertices</p>
<p><span class="math-container">$min\sum_{(u,v) \in E} x_{(u,v)}$</span></p>
<p><span class="math-container">$\forall v \in V:\sum_{v \in V} x_{(u,v)} = 2$</span></p>
<p><span class="math-container">$\forall S \subset V, S \not \in$</span> {V,<span class="math-container">$\varnothing$</span>} : <span class="math-container">$\sum_{u \in S, v \not \in S} x_{(u,v)}\geq2$</span></p>
<p><span class="math-container">$x_{u,v} \in$</span> {0,1}</p>
<p>Explenation:</p>
<ol>
<li><p>The goal is:   <span class="math-container">$min\sum_{(u,v) \in E} x_{(u,v)}$</span></p>
</li>
<li><p>For every vertex v, it can have exactly two edges connecting it:<span class="math-container">$\sum_{v \in V} x_{(u,v)} = 2$</span>.</p>
</li>
<li><p>The Hamiltonian cycle satisfies that the graph should be connected with at least 2 edges coming from S to <span class="math-container">$\ \bar S$</span> so the constraint is:
<span class="math-container">$\forall S \subset V, S \not \in V,\varnothing$</span> : <span class="math-container">$\sum_{u \in S, v \not \in S} x_{(u,v)}\geq2$</span></p>
</li>
<li><p><span class="math-container">$x_{u,v} \in$</span> {0,1} , give 1 to the variable representing the fact that the edge e=(u,v) is chosen the Hamiltonian cycle, 0 otherwise.</p>
</li>
</ol>

CC BY-SA 4.0
2021-04-29T18:36:00.607Z
2021-04-29T18:56:33.183Z
2021-04-29T18:56:33.183Z
Asya Olshansky
<p>I'm trying to do reduce Hamiltonian Cycle to integer linear programming. Here's my idea:</p>

<p>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$.</p>

<p>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.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2013-02-26T10:18:58.520Z
This is what is implemented in Sage : http://hal.archives-ouvertes.fr/docs/00/50/49/14/PDF/LP_formulations.pdf
And here is the source code (two versions of this LP) : http://hg.sagemath.org/sage-main/file/5714ed3eab6a/sage/graphs/generic_graph.py#l5630
Nathann Cohen
CC BY-SA 4.0
2018-08-26T19:08:25.473Z
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
CC BY-SA 4.0
2018-08-28T22:28:30.213Z
This paper proves that if you use just the variables you have defined, you will need exponentially many inequalities to formulate hamiltonian cycles. https://link.springer.com/article/10.1007/s10107-014-0855-0
Austin Buchanan
<linear-programming><hamiltonian-paths>
Hamiltonian Cycle as an integer linear programming problem
Jimbob
# Hamiltonian Cycle as an integer linear programming problem

(Asked by: username_0 on 2013-02-26)

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!

**Tags:** linear-programming, hamiltonian-paths
> **Comments:**
> **username_1**: This is what is implemented in Sage : http://hal.archives-ouvertes.fr/docs/00/50/49/14/PDF/LP_formulations.pdf And here is the source code (two versions of this LP) : http://hg.sagemath.org/sage-main/file/5714ed3eab6a/sage/graphs/generic_graph.py#l5630  
> **username_2**: 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$.  
> **username_3**: This paper proves that if you use just the variables you have defined, you will need exponentially many inequalities to formulate hamiltonian cycles. https://link.springer.com/article/10.1007/s10107-014-0855-0  

---

## 4 answers

### Answer by username_4 on 2013-02-26. Score: 7

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](https://web.archive.org/web/20130507102040/http://www.cs.toronto.edu/~philipp/pages/papers/DangerousReductions.pdf)), 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.

> **Comments:**
> **username_5**: The link posted is broken, do you have a updated reference?  
> **username_4**: I am unable to find it yet, when I will, I'll post.  

---

### Answer by username_2 on 2024-04-10. Score: 4

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.

> **Comments:**
> **username_6**: 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.  

---

### Answer by username_7 on 2018-08-26. Score: 3

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

> **Comments:**
> **username_8**: 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.  
> **username_7**: @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.  
> **username_8**: Yes the main point of my comment was actually to point out the name MTZ as this may help for further reading.  

---

### Answer by username_9 on 2021-04-29. Score: 0

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.


---

