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

[celestialgod (天)]

比喻法：

我現在有重量不一的金塊要用三個背包一起帶走，背包載重是無限大

我要怎麼讓每個背包的重量最平均 [(每個背包重量 - 總重除上背包個數)的平方和最小]


實際問題：

我有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個

所以目前沒有什麼特別的想法可以解這個問題...

我不需要太好的解，只需要一個不算太差的解 (不知道怎樣描述)

至少比輪盤法或是直接隨機亂分好就好....


不知道是否可以發在這裡，如果發錯會自行砍文，謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.232.188.7
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1499961462.A.BD6.html
推 LPH66: https://en.wikipedia.org/wiki/Partition_problem 這個?
Partition Problem是用最小箱子裝全部，可是我是要用固定數量的箱子裝到最平均
※ 編輯: celestialgod (36.232.188.7), 07/14/2017 00:17:19
推 DJWS: 有個類似關鍵字是 greedy load balancing 可以做到 2-approx
推 DJWS: 只是objective function跟你的問題有點不同...
推 FRAXIS: 如果是要讓總執行時間最小 應該是 minimize makespan?
→ FRAXIS: https://goo.gl/E3RXNw
推 edwardboy: 如果只是要近似解要不要試試看parallel machine sched
→ edwardboy: uling 中近似 minimize makespan 的 longest processi
→ edwardboy: ng time first rule?
→ edwardboy: 因為其實minimize makespan 就很像是平衡 machine  之
→ edwardboy:  load balancing