A Multiplier Adjustment Method for the Generalized Assignment Problem
提出一种分支定界算法求解广义分配问题，通过拉格朗日松弛和启发式乘数调整获取界，在随机小问题及车辆路径大问题上计算时间合理，分支节点数比竞争算法少两个数量级。
We describe a branch and bound algorithm for the generalized assignment problem in which bounds are obtained from a Lagrangian relaxation with the multipliers set by a heuristic adjustment method. The algorithm was tested on a large sample of small random problems and a number of large problems derived from a vehicle routing application. Computation times were reasonable in all cases and the branch and bound trees generated had nearly two orders of magnitude fewer nodes than for competing algorithms. Although comparison of running times on different machines is difficult, the multiplier adjustment method appears to be about one order of magnitude faster than the best previously existing algorithms for this problem.