5
$\begingroup$

I would like to know if there is an efficient way to formulate simple cycles on the Graph/Digraph. Let's say, there is a grid-form graph for which each vertex is only connected to a limited number of vertices as follows:

enter image description here

Some of the single cycles can be counted as:

1: [1,2,5,6,1]
2: [6,5,8,9,6]
3: [2,3,4,5,2]
4: [5,6,9,8,5]
5: [3,4,7,8,5,2,3] 
6: ...

I tried some algorithms to find cycles on the graph to make what I want, and by applying some sort of filters, I can get the results, but it is a bit hard to represent that as a general approach. For example, finding the cycles only with $4$ or $6$ vertices. My question: is there any way to represent such a problem as a MILP?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The question is a bit unclear. Are you seeking to find all Hamiltonian cycles? $\endgroup$
    – prubin ♦
    Jan 22 at 20:13
  • $\begingroup$ @prubin, thanks Prof. Yes. It would be great to find all unique H-cycles. I mean the tour (1-2-5-6-1) is the same as (2-5-6-1-2) and one of them would be sufficient. $\endgroup$
    – A.Omidi
    Jan 22 at 20:44
  • $\begingroup$ I think this is one of those "can you versus should you" questions. Is there a reason for wanting a MILP model versus either a constraint programming/constraint satisfaction model or just an iterative algorithm that finds all H-cycles? $\endgroup$
    – prubin ♦
    Jan 22 at 21:03
  • $\begingroup$ @prubin, I tried an algorithmic method, but it needs more time to change the output into a readable solution. I do not have more experiences to use CP than MILP, specifically from the solver/programming side. But, any help would be appreciated. $\endgroup$
    – A.Omidi
    Jan 23 at 5:15

2 Answers 2

Reset to default
3
$\begingroup$

Using a reasonably straightforward looping approach, I found a total of 13 distinct simple cycles in your graph:

[1, 2, 5, 4, 7, 8, 9, 6, 1]
[1, 2, 3, 4, 7, 8, 9, 6, 1]
[1, 2, 3, 4, 5, 8, 9, 6, 1]
[1, 2, 5, 8, 9, 6, 1]
[1, 2, 3, 4, 5, 6, 1]
[1, 2, 3, 4, 7, 8, 5, 6, 1]
[1, 2, 5, 6, 1]
[2, 3, 4, 5, 2]
[2, 3, 4, 7, 8, 5, 2]
[2, 3, 4, 7, 8, 9, 6, 5, 2]
[4, 5, 8, 7, 4]
[4, 5, 6, 9, 8, 7, 4]
[5, 6, 9, 8, 5]

The logic is fairly straightforward. We assume that the start of any cycle is the lowest index node in it. So we find all cycles starting at 1, then all cycles starting at 2 noting that they cannot contain 1, then all cycles starting at 3 (and not containing 1 or 2), etc. The cycles are found the usual way: each edge incident at the start node forms a new partial path; each partial path spawns more partial paths by extending it with each edge incident at the last node; an extension is discarded if it leads to either a node less than the start node or a node already on the path (and not the start); and an extension that returns to the start node forms a complete cycle.

This still results in duplication of paths (paths show up both "clockwise" and "counterclockwise"), so we check completed paths to see if they are duplicates.

The Java code to do this took about 11 ms., including building the graph structure, processing and printing. I don't see any way to build and solve a MILP model that finds all simple cycles in that short a time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, Prof. for your answer. The mentioned solutions are similar to what I could get by the cycling algorithm. Would you please, I do not understand the last sentence. Is it meaning there is No way to formulate such a problem? or meaning there is NO efficient formulation, MIP/CP, to solve such a problem? (At the moment, being efficient is not matter). In the second, it would be great to share that. $\endgroup$
    – A.Omidi
    Jan 24 at 7:05
  • $\begingroup$ I think it is possible to build a MILP model to find all simple cycles, but before I provide any details I need to verify that what I have in mind would work. $\endgroup$
    – prubin ♦
    Jan 24 at 16:32
  • $\begingroup$ OK, I have a MILP model that seems to work. On your test graph, using CPLEX, it found the same 13 cycles in around 25 seconds or so (compared to 11 milliseconds for the iterative method, and not counting the time to build the model). That's the good news. The model requires an a priori upper bound on the number of cycles, which I set to 20. After five minutes, the best bound was still 20. I'm not sure anything other than exploring the full tree will close the gap. According to the node log, some nodes were infeasible, but the feasible nodes it listed all had LP bounds of 20. $\endgroup$
    – prubin ♦
    Jan 24 at 21:29
2
$\begingroup$

With Johnson's algorithm from the networkx library, all 13 cycles are found in 0.0005 seconds:

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Dear @kuifje, thanks for your answer. I really would like to use a MILP instead of an algorithmic way. $\endgroup$
    – A.Omidi
    Jan 27 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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