Questions tagged [hamiltonian-path]
The hamiltonian-path tag has no usage guidance.
8
questions
1
vote
0
answers
35
views
Optimal control problem with bounded control
Let's consider the following deterministic constrained optimisation problem, where $c(t)$ is the control, and $x(t)$ and $y(t)$ are the state variables:
\begin{align}
J(t) = \inf_{c(t)} \ &\int_0^\...
- 123
1
vote
1
answer
805
views
About circuit constraints in OR - tools
I am trying to implement a scheduling problem to solve with CP-SAT from OR-tools. There, in particular, for every machine I want to add a time transition constraint from every task that is performed ...
- 221
5
votes
2
answers
161
views
Number of simple cycles on the graph
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 ...
- 9,068
3
votes
3
answers
203
views
Directed trees and the order/score of each node in the tree
Suppose we have a directed tree as follows:
The information regarding the edges are also given to us as a list
like edge_info = [ (a,c) , (a,b) , (b,d) , (b,e) , (b,f) ]
I am trying to find a way to ...
- 1,378
2
votes
0
answers
43
views
Shortest (undirected) path constrained to a sub-set of nodes
I expect this to be an NP-complete problem, as it may reduce to the Hamiltonian Path problem.
Anyway, I was wondering whether there exists some study and (aproximated) solutions for this particular ...
- 571
3
votes
2
answers
1k
views
Simple example of finding Hamiltonian path using Google OR-Tools?
I'd like to test how good/fast OR-Tools is in finding hamiltonian paths on some (big) directed graphs.
But I can't find simple enough (for me) examples.
Something like these ones (or even simpler), ...
- 59
1
vote
1
answer
123
views
Equivalence of Shortest Hamiltonian Paths with a Starting Node to Traveling Salesman Problem
Q- Can someone explain the equivalence in detail please?
- 409
1
vote
1
answer
161
views
Equivalence of Shortest Hamiltonian Paths to Traveling Salesman Problem
Two questions:
Q1- Why do we need to add "bidirectional" arcs (instead of single directional arcs)
between the new node n + 1 and with every node in the original network?
Q2- Why is the ...
- 409