Modelling DFJ elminations constraints

Hi, everyone.

I am new in this world of programming, specially in Julia, and i have found some trouble to ‘declare’ the subtour elimination from DFJ problems in Travelling Salesman Problem (TSP).

Constrait:
image

How can i compute this?

Thank you all very much in advance.

Are you using JuMP? I think you would want to the use the function combinations from Combinatorics.jl to get all the subsets of 1:n of a certain length, then for each subset add constraint (@add_constraint in JuMP).

Note that there are 2^n subsets of 1:n so you may have problems with even moderate n.

My package TravelingSalesmanExact uses a variant of this approach where you don’t add constraints for every subtour, but rather you solve the problem once, see what subtours are in the “solution” you got, add constraints to remove those, and solve again and repeat until you end up with a full length tour.

Take a read of PSA: make it easier to help you

In general, it’s a lot easier to help if you can provide a code snippet of what you are trying to achieve, what you have tried, and what the current error/behavior you are not expecting is.

1 Like