作者cybrog (cybrog)
看板Prob_Solve
標題[問題] 關於ILP GLPK solver問題
時間Wed Jun 22 16:05:01 2016
想請問像是ILP這類的問題
若是數學定義式已經寫出
那影響執行時間最大的地方在哪?
想說是利用類似圖跟邊與角的方式求解
感覺上變數多對時間影響不大嗎～
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.159.180
※ 文章網址: https://webptt.com/m.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