24小时热门版块排行榜

返回列表

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

lzz654321

木虫 (著名写手)

凑活

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

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

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

回复此楼

» 猜你喜欢

孩子确诊有中度注意力缺陷已经有14人回复
三甲基碘化亚砜的氧化反应已经有4人回复
请问下大家为什么这个铃木偶联几乎不反应呢已经有5人回复
请问有评职称，把科研教学业绩算分排序的高校吗已经有5人回复
2025冷门绝学什么时候出结果已经有3人回复
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入已经有4人回复
康复大学泰山学者周祺惠团队招收博士研究生已经有6人回复
AI论文写作工具：是科研加速器还是学术作弊器？已经有3人回复
论文投稿，期刊推荐已经有4人回复
请问2026国家基金面上项目会启动申2停1吗已经有5人回复

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有帮助。