/* Copyright 2025, Gurobi Optimization, LLC */// Solve a traveling salesman problem on a randomly generated set of// points using lazy constraints.   The base MIP model only includes// 'degree-2' constraints, requiring each node to have exactly// two incident edges.  Solutions to this model may contain subtours -// tours that don't visit every node.  The lazy constraint callback// adds new constraints to cut them off.usingSystem;usingGurobi;classtsp_cs:GRBCallback{privateGRBVar[,]vars;publictsp_cs(GRBVar[,]xvars){vars=xvars;}// Subtour elimination callback.  Whenever a feasible solution is found,// find the smallest subtour, and add a subtour elimination// constraint if the tour doesn't visit every node.protectedoverridevoidCallback(){try{if(where==GRB.Callback.MIPSOL){// Found an integer feasible solution - does it visit every node?intn=vars.GetLength(0);int[]tour=findsubtour(GetSolution(vars));if(tour.Length<n){// Add subtour elimination constraintGRBLinExprexpr=0;for(inti=0;i<tour.Length;i++)for(intj=i+1;j<tour.Length;j++)expr.AddTerm(1.0,vars[tour[i],tour[j]]);AddLazy(expr<=tour.Length-1);}}}catch(GRBExceptione){Console.WriteLine("Error code: "+e.ErrorCode+". "+e.Message);Console.WriteLine(e.StackTrace);}}// Given an integer-feasible solution 'sol', return the smallest// sub-tour (as a list of node indices).protectedstaticint[]findsubtour(double[,]sol){intn=sol.GetLength(0);bool[]seen=newbool[n];int[]tour=newint[n];intbestind,bestlen;inti,node,len,start;for(i=0;i<n;i++)seen[i]=false;start=0;bestlen=n+1;bestind=-1;node=0;while(start<n){for(node=0;node<n;node++)if(!seen[node])break;if(node==n)break;for(len=0;len<n;len++){tour[start+len]=node;seen[node]=true;for(i=0;i<n;i++){if(sol[node,i]>0.5&&!seen[i]){node=i;break;}}if(i==n){len++;if(len<bestlen){bestlen=len;bestind=start;}start+=len;break;}}}for(i=0;i<bestlen;i++)tour[i]=tour[bestind+i];System.Array.Resize(reftour,bestlen);returntour;}// Euclidean distance between points 'i' and 'j'protectedstaticdoubledistance(double[]x,double[]y,inti,intj){doubledx=x[i]-x[j];doubledy=y[i]-y[j];returnMath.Sqrt(dx*dx+dy*dy);}publicstaticvoidMain(String[]args){if(args.Length<1){Console.WriteLine("Usage: tsp_cs nnodes");return;}intn=Convert.ToInt32(args[0]);try{GRBEnvenv=newGRBEnv();GRBModelmodel=newGRBModel(env);// Must set LazyConstraints parameter when using lazy constraintsmodel.Parameters.LazyConstraints=1;double[]x=newdouble[n];double[]y=newdouble[n];Randomr=newRandom();for(inti=0;i<n;i++){x[i]=r.NextDouble();y[i]=r.NextDouble();}// Create variablesGRBVar[,]vars=newGRBVar[n,n];for(inti=0;i<n;i++){for(intj=0;j<=i;j++){vars[i,j]=model.AddVar(0.0,1.0,distance(x,y,i,j),GRB.BINARY,"x"+i+"_"+j);vars[j,i]=vars[i,j];}}// Degree-2 constraintsfor(inti=0;i<n;i++){GRBLinExprexpr=0;for(intj=0;j<n;j++)expr.AddTerm(1.0,vars[i,j]);model.AddConstr(expr==2.0,"deg2_"+i);}// Forbid edge from node back to itselffor(inti=0;i<n;i++)vars[i,i].UB=0.0;model.SetCallback(newtsp_cs(vars));model.Optimize();if(model.SolCount>0){int[]tour=findsubtour(model.Get(GRB.DoubleAttr.X,vars));Console.Write("Tour: ");for(inti=0;i<tour.Length;i++)Console.Write(tour[i]+" ");Console.WriteLine();}// Dispose of model and environmentmodel.Dispose();env.Dispose();}catch(GRBExceptione){Console.WriteLine("Error code: "+e.ErrorCode+". "+e.Message);Console.WriteLine(e.StackTrace);}}}