作者cybrog (cybrog)
看板Prob_Solve
标题[问题] 关於ILP GLPK solver问题
时间Wed Jun 22 16:05:01 2016
想请问像是ILP这类的问题
若是数学定义式已经写出
那影响执行时间最大的地方在哪?
想说是利用类似图跟边与角的方式求解
感觉上变数多对时间影响不大吗～
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.9.159.180
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1466582703.A.13B.html
1F：→ cybrog: 补充一下问题 大概就是像300个连续物件 但物件都有一变数 06/22 16:07
2F：→ cybrog: 变数范围为5个整数 06/22 16:07
3F：→ cybrog: 一般来看复杂度为5^300 06/22 16:07
4F：→ yr: 在 I 的部分吧....单纯的 LP 用 simplex ，大多数的问题 06/22 16:18
5F：→ yr: polynomial time solvable ，整数的部分就要穷举 06/22 16:19
6F：推 FRAXIS: 变数或是限制愈多一般会需要更长的时间来计算 06/22 20:59
7F：→ FRAXIS: 但是如果你限制式设计的比较好 可以有效的消去不可能为最 06/22 20:59
8F：→ FRAXIS: 佳解的区域 那或许会减少计算时间 06/22 21:00