Tsp.java
/* Copyright 2021, 狗万app足彩Gurobi Optimization, LLC */ //解决一个随机生成的一组//点使用惰性约束的旅行推销员问题。基本MIP模型只包含// 'degree-2'约束，要求每个节点有精确的//两条关联边。此模型的解决方案可能包含subtour - // tour，它们不访问每个节点。惰性约束回调//添加新的约束来切断它们。进口gurobi。*;public class Tsp extends GRBCallback {private GRBVar[][] vars;public Tsp(GRBVar[][] xvars) {var = xvars;} // Subtour消除回调。当找到可行解时，//查找包含节点0的子遍历，如果遍历不访问每个节点，则添加子遍历消去约束。如果(where == GRB.CB_MIPSOL){//找到一个整数可行的解决方案-它访问每个节点? int n = vars.length; int[] tour = findsubtour(getSolution(vars)); if (tour.length < n) { // Add subtour elimination constraint GRBLinExpr expr = new GRBLinExpr(); for (int i = 0; i < tour.length; i++) for (int j = i+1; j < tour.length; j++) expr.addTerm(1.0, vars[tour[i]][tour[j]]); addLazy(expr, GRB.LESS_EQUAL, tour.length-1); } } } catch (GRBException e) { 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). protected static int[] findsubtour(double[][] sol) { int n = sol.length; boolean[] seen = new boolean[n]; int[] tour = new int[n]; int bestind, bestlen; int i, 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; } } } int result[] = new int[bestlen]; for (i = 0; i < bestlen; i++) result[i] = tour[bestind+i]; return result; } // Euclidean distance between points 'i' and 'j' protected static double distance(double[] x, double[] y, int i, int j) { double dx = x[i]-x[j]; double dy = y[i]-y[j]; return Math.sqrt(dx*dx+dy*dy); } public static void main(String[] args) { if (args.length < 1) { System.out.println("Usage: java Tsp ncities"); System.exit(1); } int n = Integer.parseInt(args[0]); try { GRBEnv env = new GRBEnv(); GRBModel model = new GRBModel(env); // Must set LazyConstraints parameter when using lazy constraints model.set(GRB.IntParam.LazyConstraints, 1); double[] x = new double[n]; double[] y = new double[n]; for (int i = 0; i < n; i++) { x[i] = Math.random(); y[i] = Math.random(); } // Create variables GRBVar[][] vars = new GRBVar[n][n]; for (int i = 0; i < n; i++) for (int j = 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 constraints for (int i = 0; i < n; i++) { GRBLinExpr expr = new GRBLinExpr(); for (int j = 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 itself for (int i = 0; i < n; i++) vars[i][i].set(GRB.DoubleAttr.UB, 0.0); model.setCallback(new Tsp(vars)); model.optimize(); if (model.get(GRB.IntAttr.SolCount) > 0) { int[] tour = findsubtour(model.get(GRB.DoubleAttr.X, vars)); assert tour.length == n; System.out.print("Tour: "); for (int i = 0; i < tour.length; i++) System.out.print(String.valueOf(tour[i]) + " "); System.out.println(); } // Dispose of model and environment model.dispose(); env.dispose(); } catch (GRBException e) { System.out.println("Error code: " + e.getErrorCode() + ". " + e.getMessage()); e.printStackTrace(); } } }
