作者celestialgod (天)
看板Prob_Solve
标题Fw: [问题] 徵求演算法求解整数非线性规划问题
时间Thu Jul 13 23:57:40 2017
比喻法：
我现在有重量不一的金块要用三个背包一起带走，背包载重是无限大
我要怎麽让每个背包的重量最平均 [(每个背包重量 - 总重除上背包个数)的平方和最小]
实际问题：
我有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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1499961462.A.BD6.html
Partition Problem是用最小箱子装全部，可是我是要用固定数量的箱子装到最平均
※ 编辑: celestialgod (36.232.188.7), 07/14/2017 00:17:19
2F：推 DJWS: 有个类似关键字是 greedy load balancing 可以做到 2-approx 07/14 04:19
3F：推 DJWS: 只是objective function跟你的问题有点不同... 07/14 04:22
4F：推 FRAXIS: 如果是要让总执行时间最小 应该是 minimize makespan? 07/14 09:42
6F：推 edwardboy: 如果只是要近似解要不要试试看parallel machine sched 10/19 11:14
7F：→ edwardboy: uling 中近似 minimize makespan 的 longest processi 10/19 11:14
8F：→ edwardboy: ng time first rule? 10/19 11:14
9F：→ edwardboy: 因为其实minimize makespan 就很像是平衡 machine 之 10/19 11:16
10F：→ edwardboy: load balancing 10/19 11:16