4
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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/… $\endgroup$ – Nathann Cohen Feb 26 '13 at 10:18
  • $\begingroup$ 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$. $\endgroup$ – Neal Young Aug 26 '18 at 19:08
  • $\begingroup$ 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 $\endgroup$ – Austin Buchanan Aug 28 '18 at 22:28
5
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The link posted is broken, do you have a updated reference? $\endgroup$ – Hooked May 16 '14 at 18:16
  • $\begingroup$ I am unable to find it yet, when I will, I'll post. $\endgroup$ – Shaull May 16 '14 at 20:52
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – C Komus Aug 28 '18 at 9:39
  • $\begingroup$ @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. $\endgroup$ – Alex Meiburg Aug 28 '18 at 19:32
  • 1
    $\begingroup$ Yes the main point of my comment was actually to point out the name MTZ as this may help for further reading. $\endgroup$ – C Komus Aug 28 '18 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.