[问题] 征求算法求解整数非线性规划问题

楼主: 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