[問題] 關於ILP GLPK solver問題

作者: cybrog (cybrog)   2016-06-22 16:05:01
想請問像是ILP這類的問題
若是數學定義式已經寫出
那影響執行時間最大的地方在哪?
想說是利用類似圖跟邊與角的方式求解
感覺上變數多對時間影響不大嗎~
作者: cybrog (cybrog)   2016-06-22 16:07:00
補充一下問題 大概就是像300個連續物件 但物件都有一變數變數範圍為5個整數一般來看複雜度為5^300
作者: yr (Sooner Born Sooner Bred)   2016-06-22 16:18:00
在 I 的部分吧....單純的 LP 用 simplex ,大多數的問題polynomial time solvable ,整數的部分就要窮舉
作者: FRAXIS (喔喔)   2016-06-22 20:59:00
變數或是限制愈多一般會需要更長的時間來計算但是如果你限制式設計的比較好 可以有效的消去不可能為最佳解的區域 那或許會減少計算時間

Links booklink

Contact Us: admin [ a t ] ucptt.com