Hello,
TLDR: How to implement Subtour Elimination Constraints
I am trying to solve a traveling salesman problem (TSP). I looked at the TSP example using a Hamiltonian circuit, but my TSP problem has a couple of differences which make it different from the example.
First, the the saleman needs to be able to visit a city more than once in cases where a city may not have a connection to another node. For example, in a hub and spoke configuration. Take for instance several nodes connected to a central node A. The other nodes may be connected to each other, but there is one node X that only has node A as a connection. To reach node X, the traveler must go through A, and then return to A in order to reach the other nodes.
My second difference is that the traveler may decide that they don't want to return to the orignal node.
No matter whether the user chooses to return to the starting point or not, they still must travel through/to each node.
I've created a working model using Excel Solver by following the document at this link: http://www.economicsnetwork.ac.uk/iree/v10n1/rasmussen.pdf. I've begun working on a model in Jacop to solve the problem as well, but I cannot figure out how to enter the Subtour Elimination Constraints (SEC) mentioned in part 7 of the document. The constraint is of the form:
ui-uj+1 <= (n-1)(1-xij) for all i,j in the set of arcs where i,j does not equal 1
From the Jacop documentation I see that u and x are IntVars n is a constant equal to the number of nodes.
It is listed as equation 16 in the linked document.
I'm having a hard time figuring out if building this kind of constraint is even possible, and if it is, how to do it. I would appreciate any help in trying to figure out how to build the SEC.
Thanks for you time.
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Of course, using JaCoP, you can add all these constraint using Linear constraint, for example. However, the model presented in the referred paper is well suited for linear programming and might be poor for constraint programming. "Poor", I mean that it can be solvable for small instances but will be difficult for larger instances.
TSP is a difficult problem for CP and therefore we have two global constraints, circuit and subcircuit that encapsulate Hamiltonian circuit problem in the graph. Obviously, you would like to solve more relaxed problem and it might be difficult.
Good luck with your coding!
/Kris
If you would like to refer to this comment somewhere else in this project, copy and paste the following link:
Hello,
TLDR: How to implement Subtour Elimination Constraints
I am trying to solve a traveling salesman problem (TSP). I looked at the TSP example using a Hamiltonian circuit, but my TSP problem has a couple of differences which make it different from the example.
First, the the saleman needs to be able to visit a city more than once in cases where a city may not have a connection to another node. For example, in a hub and spoke configuration. Take for instance several nodes connected to a central node A. The other nodes may be connected to each other, but there is one node X that only has node A as a connection. To reach node X, the traveler must go through A, and then return to A in order to reach the other nodes.
My second difference is that the traveler may decide that they don't want to return to the orignal node.
No matter whether the user chooses to return to the starting point or not, they still must travel through/to each node.
I've created a working model using Excel Solver by following the document at this link: http://www.economicsnetwork.ac.uk/iree/v10n1/rasmussen.pdf. I've begun working on a model in Jacop to solve the problem as well, but I cannot figure out how to enter the Subtour Elimination Constraints (SEC) mentioned in part 7 of the document. The constraint is of the form:
ui-uj+1 <= (n-1)(1-xij) for all i,j in the set of arcs where i,j does not equal 1
From the Jacop documentation I see that u and x are IntVars n is a constant equal to the number of nodes.
It is listed as equation 16 in the linked document.
I'm having a hard time figuring out if building this kind of constraint is even possible, and if it is, how to do it. I would appreciate any help in trying to figure out how to build the SEC.
Thanks for you time.
Hi!
Of course, using JaCoP, you can add all these constraint using Linear constraint, for example. However, the model presented in the referred paper is well suited for linear programming and might be poor for constraint programming. "Poor", I mean that it can be solvable for small instances but will be difficult for larger instances.
TSP is a difficult problem for CP and therefore we have two global constraints, circuit and subcircuit that encapsulate Hamiltonian circuit problem in the graph. Obviously, you would like to solve more relaxed problem and it might be difficult.
Good luck with your coding!
/Kris
Thanks for the response. I'll try to implement it in jacop, and also search for a suitable LP library.