24小时热门版块排行榜    

CyRhmU.jpeg
南方科技大学公共卫生及应急管理学院2025级博士研究生招生报考通知
查看: 1607  |  回复: 14

lzz654321

木虫 (著名写手)

凑活

引用回帖:
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

新虫 (初入文坛)

【答案】应助回帖

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有帮助。
知乎主页: https://www.zhihu.com/people/robin-20-22
12楼2014-09-10 22:49:13
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

gcss

新虫 (初入文坛)

不是分支定界就是用刀割,无论如何都摆脱不了枚举。如果不求精确解,去搞local search, ga, heuristic
13楼2014-11-09 12:05:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

hnzjwjj

新虫 (初入文坛)

feixiaolin: 屏蔽内容, 答非所问,屏蔽 2014-11-09 17:11:50
本帖内容被屏蔽

14楼2014-11-09 15:03:05
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

Robin_Sen

新虫 (初入文坛)

你是什么学校的Phd来着?有机会可以合作。
可以看我知乎的主页。
https://www.zhihu.com/people/robin-20-22
知乎主页: https://www.zhihu.com/people/robin-20-22
15楼2016-07-29 17:26:56
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 lzz654321 的主题更新
信息提示
请填处理意见