Java调用CPLEX解决TSP问题（基于MTZ模型）

Java调用CPLEX解决TSP问题（基于MTZ模型）

MTZ模型理解简单，编码简单，但是对于解决规模较大的问题复杂度较大。我在计算TSP问题时，101个点大概需要15分钟，120个点大概需要2个小时，再往上就没有试过了。

现把对应代码存档于此。值得注意的是约束3中ui和uj不能只添加一个。

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;t.*;
t.IloCopyManager.Check;
import ilog.cplex.*;public class Main {public static int _cityNum;public static double[][] _cityDis;public static ArrayList<Integer> _set;public static ArrayList<ArrayList<Integer>> _setPool;public static ArrayList<Integer> _setCG;// for constraint generationpublic static ArrayList<ArrayList<Integer>> _setCGPool;// for constraint// generationpublic static long _time;public static double _ansLength;public static double[][] _ansCity;public static void main(String[] args) {String filename = "E:\JAVA\TSP1\data\gr120.tsp";// 读取标准化后的文件ReadData(filename);// 运行算法MTZsolve();// MTZ方法// 输出结果WriteAns(filename + ".ans");// 检查是否满足约束// checkOpt();System.out.println("finish");}// MTZ方法解决public static void MTZsolve() {try {_ansCity = new double[_cityNum][_cityNum];IloCplex cplex = new IloCplex();IloIntVar[][] x = new IloIntVar[_cityNum][_cityNum];// 0-1变量IloIntVar[] u = new IloIntVar[_cityNum];// 设定变量取值范围for (int i = 0; i < _cityNum; i++) {for (int j = 0; j < _cityNum; j++) {if (i != j)x[i][j] = cplex.intVar(0, 1);elsex[i][j] = cplex.intVar(0, 0);}}for (int i = 1; i < _cityNum; i++) {u[i] = cplex.intVar(1, _cityNum - 1);}// 目标函数IloLinearNumExpr tempObj = cplex.linearNumExpr();for (int i = 0; i < _cityNum; i++) {tempObj.add(cplex.scalProd(x[i], _cityDis[i]));}cplex.addMinimize(tempObj);// 添加约束 1 和 2for (int i = 0; i < _cityNum; i++) {IloLinearIntExpr constraint2 = cplex.linearIntExpr();for (int j = 0; j < _cityNum; j++) {constraint2.addTerm(x[j][i], 1);}cplex.addEq(cplex.sum(x[i]), 1);cplex.addEq(constraint2, 1);}// 添加约束 3for (int i = 1; i < _cityNum; i++) {for (int j = i + 1; j < _cityNum; j++) {IloLinearIntExpr constraint3_1 = cplex.linearIntExpr();constraint3_1.addTerm(u[i], 1);constraint3_1.addTerm(u[j], -1);constraint3_1.addTerm(x[i][j], _cityNum - 1);cplex.addLe(constraint3_1, _cityNum - 2);IloLinearIntExpr constraint3_2 = cplex.linearIntExpr();constraint3_2.addTerm(u[j], 1);constraint3_2.addTerm(u[i], -1);constraint3_2.addTerm(x[j][i], _cityNum - 1);cplex.addLe(constraint3_2, _cityNum - 2);}}// 输出结果long start = System.currentTimeMillis();boolean success = cplex.solve();long end = System.currentTimeMillis();_time = end - start;if (success) {_ansLength = ObjValue();for (int i = 0; i < _cityNum; i++)_ansCity[i] = Values(x[i]);} elseSystem.out.println("cplex.solve() failed.");} catch (IloException e) {// TODO Auto-generated catch blocke.printStackTrace();}}// 检查是否满足条件 绕圈走一遍public static boolean checkOpt() {System.out.println("checkn--------------");_setCGPool = new ArrayList<ArrayList<Integer>>();boolean[] flag = new boolean[_cityNum];for (int i = 0; i < _cityNum; i++) {if (flag[i])continue;_setCG = new ArrayList<Integer>();int st = i;int cnt = 0;System.out.println("n");while (true) {System.out.print(st + " ");_setCG.add(st);flag[st] = true;for (int j = 0; j < _cityNum; j++) {if ((int) (_ansCity[st][j] + 0.00001) == 1) {st = j;break;}}cnt++;if (st == i || cnt >= _cityNum)break;}_setCGPool.add(new ArrayList<Integer>(_setCG));}if (_setCGPool.size() == 1) {System.out.println("nsuccess");return true;} else {System.out.println("nfail");return false;}}// 输出答案public static void WriteAns(String filename) {System.out.print(filename + "n------------------------------n");System.out.printf("rum time(sec)= %-10.2fn", _time / 1000.0);System.out.printf("min= %-10.2fn", _ansLength);for (int i = 0; i < _cityNum; i++) {for (int j = 0; j < _cityNum; j++)System.out.print((int) (_ansCity[i][j] + 0.00001) + " ");System.out.println();}}// 读取标准化后的数据public static void ReadData(String filename) {File file = new File(filename);BufferedReader reader = null;try {System.out.println("正在读取" + filename);reader = new BufferedReader(new FileReader(file));String tempString = null;tempString = adLine();_cityNum = Integer.im());_cityDis = new double[_cityNum][_cityNum];for (int i = 0; i < _cityNum; i++) {tempString = adLine();String[] arg = tempString.split(" ");for (int j = 0; j < arg.length; j++) {_cityDis[i][j] = Double.parseDouble(arg[j]);_cityDis[j][i] = _cityDis[i][j];}}reader.close();} catch (IOException e) {e.printStackTrace();} finally {if (reader != null) {try {reader.close();} catch (IOException e1) {}}}}
}