[問題] 關於ILP GLPK solver問題

[cybrog (cybrog)]

想請問像是ILP這類的問題
若是數學定義式已經寫出

那影響執行時間最大的地方在哪?

想說是利用類似圖跟邊與角的方式求解
感覺上變數多對時間影響不大嗎～




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.159.180
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1466582703.A.13B.html
→ cybrog: 補充一下問題 大概就是像300個連續物件 但物件都有一變數
→ cybrog:  變數範圍為5個整數
→ cybrog: 一般來看複雜度為5^300
→ yr: 在 I 的部分吧....單純的 LP 用 simplex ，大多數的問題
→ yr: polynomial time solvable ，整數的部分就要窮舉
推 FRAXIS: 變數或是限制愈多一般會需要更長的時間來計算
→ FRAXIS: 但是如果你限制式設計的比較好 可以有效的消去不可能為最
→ FRAXIS: 佳解的區域 那或許會減少計算時間