[問題] 徵求演算法求解整數非線性規劃問題

作者: celestialgod (天)   2017-07-13 23:57:40
比喻法:
我現在有重量不一的金塊要用三個背包一起帶走,背包載重是無限大
我要怎麼讓每個背包的重量最平均 [(每個背包重量 - 總重除上背包個數)的平方和最小]
實際問題:
我有34000個task,我知道它們的運算成本(上面的weights),其正比於時間
我現在要用MPI,總共660個threads去執行這些task,讓總執行時間最小
簡單例子:
金塊各別重2, 3, 4, 3, 4, 5, 5, 4公斤,有3個背包
求怎麼放到背包裡面重量最平均
衡量方式: sum_i( 背包i的重量 - 10 ) ^ 2 (10是金塊總重量除以背包個數)
這個問題的其中一種最佳解是 背包1: 5,5 ; 背包2: 2,4,4 ; 背包3: 3,3,4
嘗試過程:
我有試過用一個integer nonlinear programming的solver (NOMAD)
但是他只能支援1000個金塊,我的實際問題是34000個
所以目前沒有什麼特別的想法可以解這個問題...
我不需要太好的解,只需要一個不算太差的解 (不知道怎樣描述)
至少比輪盤法或是直接隨機亂分好就好....
不知道是否可以發在這裡,如果發錯會自行砍文,謝謝
作者: LPH66 (-6.2598534e+18f)   2017-07-14 00:13:00
作者: DJWS (...)   2017-07-14 04:19:00
有個類似關鍵字是 greedy load balancing 可以做到 2-approx只是objective function跟你的問題有點不同...
作者: FRAXIS (喔喔)   2017-07-14 09:42:00
如果是要讓總執行時間最小 應該是 minimize makespan?https://goo.gl/E3RXNw
作者: edwardboy (魯蛇)   2017-10-19 11:14:00
如果只是要近似解要不要試試看parallel machine scheduling 中近似 minimize makespan 的 longest processing time first rule?因為其實minimize makespan 就很像是平衡 machine 之load balancing

Links booklink

Contact Us: admin [ a t ] ucptt.com