24小时热门版块排行榜

返回列表

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

lzz654321

木虫 (著名写手)

凑活

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

[求助] 0-1规划连续求解得到解后，得不到整数解，如何处理才能得到整数解？已有4人参与

如题。如果四舍五入后得到的解去不一定满足约束条件，最后的结果和原始目标也不一定一致，应该如何处理比较好？可以给我参考文献。请各位虫友不知道的不要回答。

回复此楼

» 猜你喜欢

表哥与省会女结婚，父母去帮带孩子被省会女气回家生重病了已经有12人回复
依托企业入选了国家启明计划青年人才。有无高校可以引进的。已经有14人回复
江汉大学解明教授课题组招博士研究生/博士后已经有3人回复
AI 太可怕了，写基金时，提出想法，直接生成的文字比自己想得深远，还有科学性已经有11人回复
依托企业入选了国家启明计划青年人才。有无高校可以引进的。已经有11人回复

1楼 2014-07-26 21:18:17

已阅回复此楼关注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有帮助。