数学建模社区-数学中国

标题: Lingo可以求解多大规模的TSP问题？ [打印本页]

作者: xxaxiuxluo 时间: 2015-7-29 17:47
标题: Lingo可以求解多大规模的TSP问题？
在求解n个城市的TSP问题中，设置n为100，距离矩阵是用qrand生成的，有点惊讶，Lingo很快就找到全局最优解，，后来尝试n=200，也没用多久就得到Global solve，不是超过30个城市的话，求解都会变得困难吗？虽然在n=500时提示内存不足。。
希望大家不吝赐教！

model:
sets:
city/1..150/:u;
link(city,city):dist,x;!距离矩阵，x为决策变量;
endsets
data:
dist= @qrand();
enddata
min=@sum(link:dist*x);
n=@size(city);
@for(link:@bin(x));
!不能从自己到自己;
@for(city(i):x(i,i)=0);
!每个城市出发一次回来一次;
@for(city(k):@sum(city(i):x(i,k))=1;
@sum(city(j):x(k,j))=1;);
!防止结果出现子巡回;
@for(city(i):u(i)<=n-1);
@for(city(i):@for(city(j)|j#ne#i#and#j#gt#1:
u(i)-u(j)+n*x(i,j)<=n-1));
end

复制代码

屏幕截图.jpg (35.67 KB, 下载次数: 319)

屏幕截图.jpg

作者: xxaxiuxluo 时间: 2015-7-29 17:59
@liwenhui 求不沉啊

作者: wujianjack2 时间: 2015-7-29 19:23
n=500提示内存不足是因为matrix generator使用的内存不够了，可以在options中调整。
这类TSP属于MILP问题，你这么建模的效率不是很高，加一些技巧后可以求解更大的规模，LINGO求解MILP的效率总的来说不算世界前列。
不过，解TSP还是用专门解TSP的工具比较好，有些比较好的例子用先进的求解器在普通电脑上解几千个城市的TSP也就数十秒，而且内存消耗极低。

作者: liwenhui 时间: 2015-7-29 20:53

xxaxiuxluo 发表于 2015-7-29 17:59
@liwenhui 求不沉啊

实际应用我从来没有碰到过数量超过100的TSP问题，因为一旦超过100，通常它会有其它的特别的约束条件，这样就不是典型的TSP问题。对付非典型的问题，我会另谋出路。

作者: wujianjack2 时间: 2015-7-29 21:26
  我说的非常好的例子是tsplib95中的pr2392，这是一个有2392个城市的tsp问题，state of the art的求解log如下：
Host: Leiz-PC  Current process id: 3988
Using random seed 99
Problem Name: pr2392
2392-city problem (Padberg/Rinaldi)
Problem Type: TSP
Number of Nodes: 2392
Rounded Euclidean Norm (CC_EUCLIDEAN)
Set initial upperbound to 381724 (from tour)
  LP Value  1: 364586.000000  (0.59 seconds)
  LP Value  2: 373801.992481  (1.36 seconds)
  LP Value  3: 376863.285634  (2.29 seconds)
  LP Value  4: 377455.478632  (3.92 seconds)
  LP Value  5: 377642.800694  (5.23 seconds)
  LP Value  6: 377768.062910  (7.10 seconds)
  LP Value  7: 377917.966208  (10.05 seconds)
  LP Value  8: 378016.160175  (16.10 seconds)
  LP Value  9: 378032.000000  (17.14 seconds)
recomputing rownorms ...
  LP Value 10: 378032.000000  (17.33 seconds)
New lower bound: 378032.000000
recomputing rownorms ...
  LP Value  1: 378032.000000  (17.72 seconds)
New upperbound from x-heuristic: 378032.00
Final lower bound 378032.000000, upper bound 378032.000000
Exact lower bound: 378032.000000
DIFF: 0.000000
Final LP has 3361 rows, 5704 columns, 26466 nonzeros
Optimal Solution: 378032.00
Number of bbnodes: 1
Total Running Time: 20.23 (seconds)

结果是378032, proven optimal !

作者: xxaxiuxluo 时间: 2015-7-30 09:01

wujianjack2 发表于 2015-7-29 21:26
我说的非常好的例子是tsplib95中的pr2392，这是一个有2392个城市的tsp问题，state of the art的求解log如 ...

之前我还不知道有TSPLIB！

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)