/* 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.importcom.gurobi.gurobi.*;publicclassTspextendsGRBCallback{privateGRBVar[][]vars;publicTsp(GRBVar[][]xvars){vars=xvars;}// Subtour elimination callback. Whenever a feasible solution is found,// find the subtour that contains node 0, and add a subtour elimination// constraint if the tour doesn't visit every node.protectedvoidcallback(){try{if(where==GRB.CB_MIPSOL){// Found an integer feasible solution - does it visit every node?intn=vars.length;int[]tour=findsubtour(getSolution(vars));if(tour.length<n){// Add subtour elimination constraintGRBLinExprexpr=newGRBLinExpr();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,GRB.LESS_EQUAL,tour.length-1);}}}catch(GRBExceptione){System.out.println("Error code: "+e.getErrorCode()+". "+e.getMessage());e.printStackTrace();}}// Given an integer-feasible solution 'sol', return the smallest// sub-tour (as a list of node indices).protectedstaticint[]findsubtour(double[][]sol){intn=sol.length;boolean[]seen=newboolean[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;}}}intresult[]=newint[bestlen];for(i=0;i<bestlen;i++)result[i]=tour[bestind+i];returnresult;}// 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){System.out.println("Usage: java Tsp ncities");System.exit(1);}intn=Integer.parseInt(args[0]);try{GRBEnvenv=newGRBEnv();GRBModelmodel=newGRBModel(env);// Must set LazyConstraints parameter when using lazy constraintsmodel.set(GRB.IntParam.LazyConstraints,1);double[]x=newdouble[n];double[]y=newdouble[n];for(inti=0;i<n;i++){x[i]=Math.random();y[i]=Math.random();}// 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"+String.valueOf(i)+"_"+String.valueOf(j));vars[j][i]=vars[i][j];}// Degree-2 constraintsfor(inti=0;i<n;i++){GRBLinExprexpr=newGRBLinExpr();for(intj=0;j<n;j++)expr.addTerm(1.0,vars[i][j]);model.addConstr(expr,GRB.EQUAL,2.0,"deg2_"+String.valueOf(i));}// Forbid edge from node back to itselffor(inti=0;i<n;i++)vars[i][i].set(GRB.DoubleAttr.UB,0.0);model.setCallback(newTsp(vars));model.optimize();if(model.get(GRB.IntAttr.SolCount)>0){int[]tour=findsubtour(model.get(GRB.DoubleAttr.X,vars));asserttour.length==n;System.out.print("Tour: ");for(inti=0;i<tour.length;i++)System.out.print(String.valueOf(tour[i])+" ");System.out.println();}// Dispose of model and environmentmodel.dispose();env.dispose();}catch(GRBExceptione){System.out.println("Error code: "+e.getErrorCode()+". "+e.getMessage());e.printStackTrace();}}}