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
@liwenhui 求不沉啊
n=500提示内存不足是因为matrix generator使用的内存不够了，可以在options中调整。
这类TSP属于MILP问题，你这么建模的效率不是很高，加一些技巧后可以求解更大的规模，LINGO求解MILP的效率总的来说不算世界前列。
不过，解TSP还是用专门解TSP的工具比较好，有些比较好的例子用先进的求解器在普通电脑上解几千个城市的TSP也就数十秒，而且内存消耗极低。
xxaxiuxluo 发表于 2015-7-29 17:59 static/image/common/back.gif
@liwenhui 求不沉啊
实际应用我从来没有碰到过数量超过100的TSP问题，因为一旦超过100，通常它会有其它的特别的约束条件，这样就不是典型的TSP问题。对付非典型的问题，我会另谋出路。
我说的非常好的例子是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 !
wujianjack2 发表于 2015-7-29 21:26 static/image/common/back.gif
我说的非常好的例子是tsplib95中的pr2392，这是一个有2392个城市的tsp问题，state of the art的求解log如 ...
{:3_41:}之前我还不知道有TSPLIB！
页:
[1]