查看: 4653|回复: 5

Lingo可以求解多大规模的TSP问题？

字体大小: 正常放大

2 主题	12 听众	171 积分

升级 35.5%

TA的每日心情

	慵懒 2016-6-29 20:41

签到天数: 85 天

[LV.6]常住居民II

自我介绍: 正在努力学习数学建模，还望网友多多指教

群组: MATLAB与数模算法实训

电梯直达

1^#

发表于 2015-7-29 17:47 |只看该作者 |正序浏览

|招呼Ta 关注Ta

在求解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, 下载次数: 335)

屏幕截图.jpg

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

xxaxiuxluo

2 主题	12 听众	171 积分

升级 35.5%

TA的每日心情

	慵懒 2016-6-29 20:41

签到天数: 85 天

[LV.6]常住居民II

自我介绍: 正在努力学习数学建模，还望网友多多指教

群组: MATLAB与数模算法实训

6^#

发表于 2015-7-30 09:01 |只看该作者 |招呼Ta 关注Ta

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

之前我还不知道有TSPLIB！

我也说一句

发表

使用道具举报

wujianjack2

21 主题	97 听众	3110 积分

TA的每日心情

	奋斗 2014-3-2 00:26

签到天数: 243 天

[LV.8]以坛为家I

5^#

发表于 2015-7-29 21:26 |只看该作者 |招呼Ta 关注Ta

  我说的非常好的例子是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 之前我还不知道有TSPLIB！详情回复发表于 2015-7-30 09:01

我也说一句

发表

已有 1 人评分	体力	收起理由
liwenhui	+ 10

总评分: 体力 + 10 查看全部评分

有什么好说的

使用道具举报

liwenhui

70 主题	65 听众	5197 积分

独孤求败

TA的每日心情

	擦汗 2018-4-26 23:29

签到天数: 1502 天

[LV.Master]伴坛终老

自我介绍: 紫薇软剑，三十岁前所用，误伤义士不祥，乃弃之深谷。重剑无锋，大巧不工。四十岁前恃之横行天下。四十岁后，不滞于物，草木竹石均可为剑。自此精修，渐进至无剑胜有剑之境。

群组: 计量经济学之性

群组: LINGO

4^#

发表于 2015-7-29 20:53 |只看该作者 |招呼Ta 关注Ta |邮箱已经成功绑定

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

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

收起(1)

xxaxiuxluo :前辈可以举个栗子吗？

2015-07-30 09:02 回复

我也说一句

发表

四十岁后，不滞于物，草木竹石均可为剑。

使用道具举报

wujianjack2

21 主题	97 听众	3110 积分

TA的每日心情

	奋斗 2014-3-2 00:26

签到天数: 243 天

[LV.8]以坛为家I

3^#

发表于 2015-7-29 19:23 |只看该作者 |招呼Ta 关注Ta

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

收起(2)

xxaxiuxluo :非常感谢！LINGO求解MILP（是指混合整数线性规划吧？）应该问题都不大吧？另外，我想请问多一个问题，LINGO不是很适合解哪一类型的规划问题？

2015-07-29 20:51 回复

wujianjack2 :回复 xxaxiuxluo INGO目前可以解LP, QP, MILP, MIQP, MIQCP, MISOCP, NLP, MINLP, SP, CCP等众多类型的问题，不适合解带逻辑约束的问题，可解的问题类型内，效率总体来说一般，特别是MILP与state of the art还有不少差距。

2015-07-29 21:22 回复

我也说一句

发表

有什么好说的

使用道具举报

xxaxiuxluo

2 主题	12 听众	171 积分

升级 35.5%

TA的每日心情

	慵懒 2016-6-29 20:41

签到天数: 85 天

[LV.6]常住居民II

自我介绍: 正在努力学习数学建模，还望网友多多指教

群组: MATLAB与数模算法实训

2^#

发表于 2015-7-29 17:59 |只看该作者 |招呼Ta 关注Ta

@liwenhui 求不沉啊

点评

liwenhui 实际应用我从来没有碰到过数量超过100的TSP问题，因为一旦超过100，通常它会有其它的特别的约束条件，这样就不是典型的TSP问题。对付非典型的问题，我会另谋出路。详情回复发表于 2015-7-29 20:53

我也说一句

发表

使用道具举报

返回列表

帐号		密码		只需要一步，快速开始		注册地址	找回密码

Lingo可以求解多大规模的TSP问题？

点评

点评

社区QQ达人

邮箱绑定达人

发帖功臣

元老勋章

新人进步奖

风雨历程奖

最具活力勋章

QQ

电话咨询

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务|