Exact Solution Methods for a Generalized Assignment Problem with Location/Allocation Considerations
研究了一类带有选址/分配考虑的一般化分配问题，每个背包被离散化为吸引力不同的连续段，决策者需同时决定物品分配、位置和空间分配，提出了分支定价算法并验证其计算效率。
We investigate modeling approaches and exact solution methods for a generalized assignment problem with location/allocation (GAPLA) considerations. In contrast with classical generalized assignment problems, each knapsack in GAPLA is discretized into consecutive segments having different levels of attractiveness. To maximize a total reward function, the decision maker decides not only about item knapsack assignments, but also the specific location of items within their assigned knapsacks and their total space allocation within prespecified lower and upper bounds. Mathematical programming formulations are developed for single and multiple knapsack variants of this problem along with valid inequalities, preprocessing routines, and model enhancements. Further, a branch-and-price algorithm is devised for a set partitioning reformulation of GAPLA, and is demonstrated to yield substantial computational savings over solving the original formulation using branch-and-bound/cut solvers such as CPLEX over challenging problem instances.