24小时热门版块排行榜

南方科技大学公共卫生及应急管理学院2025级博士研究生招生报考通知

返回列表

lzz654321

木虫 (著名写手)

凑活

应助: 15 (小学生)
金币: 4792.9
散金: 174
红花: 28
帖子: 2003
在线: 546.9小时
虫号: 2405403
注册: 2013-04-07
性别: GG
专业: 金融学

引用回帖:

10楼: Originally posted by lbb122400 at 2014-07-31 16:43:39
当然有说明四舍五入是一般不可行的，你可以再仔细看看。我确信上面有。而且还有算例说明。呵呵，舍近求远，看什么文献啊。...

呵呵。。。。

回复此楼

11楼2014-07-31 16:53:02

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

Robin_Sen

新虫 (初入文坛)

应助: 0 (幼儿园)
金币: 10.3
帖子: 9
在线: 2小时
虫号: 3408508
注册: 2014-09-10
性别: GG
专业: 运筹学

【答案】应助回帖

lz说的应该是解出Linear Programming Relaxation，然后想四舍五入得到一个feasible solution？
这个想法是错误的，LP的解只能作为一个lower bound（min problem的时候），然后如果分支定界法的话，通过遍历son可以得到feasible solution作为upper bound，随着算法的不同，又可以加入cutting plane，得到更好的lower bound，然后当upper bound=lower bound 的时候，算法就停止了，即得到最优整数解。
当然有的时候upper bound不一定等于lower bound，比如cplex程序运行了一小时还没终止，但是会告诉你lower bound和upper bound之间的gap，比如说gap是5%，那么你可以取他的upper bound作为你的解，至少他是整数并且feasible，但不是最优解。

再比如travelling salesman problem，可以解几十万个城市，它也不能保证给出最优解，而只是upper bound和lower bound之间的gap只有1%不到而已，一般得到这样的解也就可以接受，然后被采纳了。

希望对lz有帮助。