Generation of restrictions for a MIP (Mixed Integer Programming). Solving the DFJ formulation of the TSP (Travelling Salesman Problem). Using Julia JuMP.

Modify The Algorithm of so that in each iteration of The Algorithm, not only the SEC (Subtour Elimination Constraint) that eliminates the city 1 subtour, if not the SEC can add all subtours to the TSP model. As an example, if n = 7 and the solution has subtours associated with the subsets of the cities S1 = {1,3}, S2 = {2,4,7}, S3 = {5,6}, then the 3 SECs should be added to the TSP model in a particular iteration of the algorithm and these would be the corresponding restrictions of subsets S1, S2 and S3. In the Algorithm, only restriction S1 has been added to the model.

import Pkg using Pkg Pkg.add("JuMP") using JuMP Pkg.add("GLPK") using GLPK Pkg.add("Cbc") using Cbc Pkg.add("TSPLIB") using TSPLIB Pkg.add("GraphPlot") using GraphPlot Pkg.add("LightGraphs") using LightGraphs

model=Model(GLPK.Optimizer)

TSPprob = readTSPLIB(:dantzig42) n = TSPprob.dimension

function plotsolution(x_sol, tspinstance) G = SimpleDiGraph() add_vertices!(G,n)

for i in 1:n for j in 1:n if x_sol[i,j] > 0.0 add_edge!(G,i,j) end end end gplot(G, tspinstance.nodes[:,1], -tspinstance.nodes[:,2], nodelabel=1:n, arrowlengthfrac=0.03) end

TSPallzeros =zeros(n,n);

plotsolution(TSPallzeros,TSPprob)

c=zeros(n,n) c=TSPprob.weights

for i in 1:n c[i,i]=sum(c[j,k] for j in 1:n, k in 1:n if k!=j) end

TSPmodel = Model(Cbc.Optimizer)

set_optimizer_attribute(TSPmodel, "logLevel", 0) @variable(TSPmodel, x[1:n,1:n], Bin) @constraint(TSPmodel, cityout[i in 1:n], sum(x[i,j] for j in 1:n) == 1) @constraint(TSPmodel, cityin[j in 1:n], sum(x[i,j] for i in 1:n) == 1)

@objective(TSPmodel, Min, sum(c[i,j]*x[i,j] for i=1:n,j=1:n));

optimize!(TSPmodel)

x_sol=value.(x) plotsolution(x_sol,TSPprob)

function subtour(x,n,k) S=Int64[] push!(S,1) next=0 current=1 while next!=1 for i in 1:n if x[current,i]>0.5 next=i if next!=1 push!(S,next) current=i break end end end end return S end

println(subtour(x_sol,n))

global len_tour=0 global iter=0 while len_tour!=n global iter=iter+1 println("Iteration = ",iter) global TSPsolval=value.(x) barS=subtour(TSPsolval,n) global len_tour=length(barS) println("Length of the subtour containing city 1 = ",len_tour) if len_tour != n @constraint(TSPmodel,sum(x[i,j] for i in 1:n, j in 1:n if i in barS && !(j in barS))>=1) optimize!(TSPmodel) end end

plotsolution(TSPsolval,TSPprob)