[問題] 關於ILP GLPK solver問題

看板Prob_Solve作者 (cybrog)時間9年前 (2016/06/22 08:05), 編輯推噓1(1推 0噓 7→)
留言8則, 3人參與, 最新討論串1/1
想請問像是ILP這類的問題 若是數學定義式已經寫出 那影響執行時間最大的地方在哪? 想說是利用類似圖跟邊與角的方式求解 感覺上變數多對時間影響不大嗎～ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.9.159.180 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1466582703.A.13B.html
→
06/22 16:07, , 1F
補充一下問題 大概就是像300個連續物件 但物件都有一變數
06/22 16:07, 1F
→
06/22 16:07, , 2F
變數範圍為5個整數
06/22 16:07, 2F
→
06/22 16:07, , 3F
一般來看複雜度為5^300
06/22 16:07, 3F
→
06/22 16:18, , 4F
在 I 的部分吧....單純的 LP 用 simplex ，大多數的問題
06/22 16:18, 4F
→
06/22 16:19, , 5F
polynomial time solvable ，整數的部分就要窮舉
06/22 16:19, 5F
推
06/22 20:59, , 6F
變數或是限制愈多一般會需要更長的時間來計算
06/22 20:59, 6F
→
06/22 20:59, , 7F
但是如果你限制式設計的比較好 可以有效的消去不可能為最
06/22 20:59, 7F
→
06/22 21:00, , 8F
佳解的區域 那或許會減少計算時間
06/22 21:00, 8F
‣ 更多 cybrog 的文章
文章代碼(AID): #1NQaQl4x (Prob_Solve)