tsp_cs.cs
/* Copyright 2021, 狗万app足彩Gurobi Optimization, LLC */ //解决一个随机生成的一组//点使用惰性约束的旅行推销员问题。基本MIP模型只包含// 'degree-2'约束，要求每个节点有精确的//两条关联边。此模型的解决方案可能包含subtour - // tour，它们不访问每个节点。惰性约束回调//添加新的约束来切断它们。使用系统;使用Gurobi;类tsp_cs: GRBCallback{私有GRBVar[，] vars;public tsp_cs(GRBVar[，] xvars) {var = xvars;} // Subtour消除回调。当找到一个可行解时，//找到最小的子遍历，如果遍历不访问每个节点，则添加子遍历消除约束。 protected override void Callback() { try { if (where == GRB.Callback.MIPSOL) { // Found an integer feasible solution - does it visit every node? int n = vars.GetLength(0); int[] tour = findsubtour(GetSolution(vars)); if (tour.Length < n) { // Add subtour elimination constraint GRBLinExpr expr = 0; 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 <= tour.Length-1); } } } catch (GRBException e) { 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). protected static int[] findsubtour(double[,] sol) { int n = sol.GetLength(0); bool[] seen = new bool[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; } } } for (i = 0; i < bestlen; i++) tour[i] = tour[bestind+i]; System.Array.Resize(ref tour, bestlen); return tour; } // 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) { Console.WriteLine("Usage: tsp_cs nnodes"); return; } int n = Convert.ToInt32(args[0]); try { GRBEnv env = new GRBEnv(); GRBModel model = new GRBModel(env); // Must set LazyConstraints parameter when using lazy constraints model.Parameters.LazyConstraints = 1; double[] x = new double[n]; double[] y = new double[n]; Random r = new Random(); for (int i = 0; i < n; i++) { x[i] = r.NextDouble(); y[i] = r.NextDouble(); } // 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"+i+"_"+j); vars[j, i] = vars[i, j]; } } // Degree-2 constraints for (int i = 0; i < n; i++) { GRBLinExpr expr = 0; for (int j = 0; j < n; j++) expr.AddTerm(1.0, vars[i, j]); model.AddConstr(expr == 2.0, "deg2_"+i); } // Forbid edge from node back to itself for (int i = 0; i < n; i++) vars[i, i].UB = 0.0; model.SetCallback(new tsp_cs(vars)); model.Optimize(); if (model.SolCount > 0) { int[] tour = findsubtour(model.Get(GRB.DoubleAttr.X, vars)); Console.Write("Tour: "); for (int i = 0; i < tour.Length; i++) Console.Write(tour[i] + " "); Console.WriteLine(); } // Dispose of model and environment model.Dispose(); env.Dispose(); } catch (GRBException e) { Console.WriteLine("Error code: " + e.ErrorCode + ". " + e.Message); Console.WriteLine(e.StackTrace); } } }
