c****n
发帖数: 21367 | 1 谢谢
1. For general linear programming, is interior point method still the
fastest in term of time complexity? I've heard that Karmarkar's algorithm
was bounded by O(n3.5 L), any improvement afterwards?
2. Is the strong-polynomial algorithm for linear programming still a hot
research direction? how does experts in this area, such as you, perceive the
difficulty and existence of strong-polynomial algorithm?
3. How about the average time complexity? We knew that about Simplex method.
Is there any re | g****t
发帖数: 31659 | 2 理论我不懂.
如果是实用问题的话,我的经验,
小规模的问题用单纯型.大规模的就用牛顿法.
这样可以通过tuning确保,你的原问题A,
和A+e的结果差不多.(e是小扰动)
这点基本的鲁棒性挺重要的.因为你建模不可能绝对准确.
其实我更prefer全部都用牛顿法.Karmarkar方法和单纯形
概念都太复杂,不够直观.学过我就忘了.
牛顿法我个人比较熟悉.各种情况我自己将会弄好各种变形.
谢谢
1. For general linear programming, is interior point method still the
fastest in term of time complexity? I've heard that Karmarkar's algorithm
was bounded by O(n3.5 L), any improvement afterwards?
2. Is the strong-polynomial algorithm for linear programming still a hot
research direction? how does
【在 c****n 的大作中提到】
: 谢谢
: 1. For general linear programming, is interior point method still the
: fastest in term of time complexity? I've heard that Karmarkar's algorithm
: was bounded by O(n3.5 L), any improvement afterwards?
: 2. Is the strong-polynomial algorithm for linear programming still a hot
: research direction? how does experts in this area, such as you, perceive the
: difficulty and existence of strong-polynomial algorithm?
: 3. How about the average time complexity? We knew that about Simplex method.
: Is there any re
| r*****k
发帖数: 1281 | 3 商业软件 诸如Cplex都是用simplex method解决
大规模问题的
【在 g****t 的大作中提到】
: 理论我不懂.
: 如果是实用问题的话,我的经验,
: 小规模的问题用单纯型.大规模的就用牛顿法.
: 这样可以通过tuning确保,你的原问题A,
: 和A+e的结果差不多.(e是小扰动)
: 这点基本的鲁棒性挺重要的.因为你建模不可能绝对准确.
: 其实我更prefer全部都用牛顿法.Karmarkar方法和单纯形
: 概念都太复杂,不够直观.学过我就忘了.
: 牛顿法我个人比较熟悉.各种情况我自己将会弄好各种变形.
:
| c****n
发帖数: 21367 | 4 谢谢你们两位的回答，我的问题是关于理论研究的...
椭圆法，内点法都是被认为只有超大规模问题才可能有优势的
但是如果有比内点法还快的算法不就好了么？呵呵。
【在 r*****k 的大作中提到】
: 商业软件 诸如Cplex都是用simplex method解决
: 大规模问题的
| g****t
发帖数: 31659 | 5 我以前看过一个做商业软件的人写的非产好的实用文章.
回头我可以查查看.
单纯形要让我写程序,我可能得一周.我不熟悉应用要做的那些
corner case的处理和tuning.
牛顿法一上午就行了.
商业软件 诸如Cplex都是用simplex method解决
大规模问题的
【在 r*****k 的大作中提到】
: 商业软件 诸如Cplex都是用simplex method解决
: 大规模问题的
| r*****k
发帖数: 1281 | 6 不用自己写
都是调用库函数
【在 g****t 的大作中提到】
: 我以前看过一个做商业软件的人写的非产好的实用文章.
: 回头我可以查查看.
: 单纯形要让我写程序,我可能得一周.我不熟悉应用要做的那些
: corner case的处理和tuning.
: 牛顿法一上午就行了.
:
: 商业软件 诸如Cplex都是用simplex method解决
: 大规模问题的
| D*******a
发帖数: 3688 | 7 cplex有几个solver的，会根据问题来选择
【在 r*****k 的大作中提到】
: 商业软件 诸如Cplex都是用simplex method解决
: 大规模问题的
| c****n
发帖数: 21367 | 8 大家回答一下原帖的几个问题吧，多谢了
【在 r*****k 的大作中提到】
: 不用自己写
: 都是调用库函数
|
|
