The multiple discrete resource allocation problem (MDRAP) explores how the decision maker allocates a number of resources of different types among agents in order to achieve the aggregate maximum utility. The MDRAP belongs in the NP-hard category of time complexity, which requires excessive efforts to obtain the optimal solution even for a moderate problem size. Partial enumeration techniques such as dynamic programming and branch-and-bound are available to tackle this complexity issue to some degree. In this paper, a new partial enumeration method based on divide-and-conquer is proposed. The pronounced distinction of this divide-and-conquer approach lies in its potential ability to parallelize the solving process, and hence can obtain the optimal solution more quickly. A simulation study on a dedicated computer is conducted and presented.
Shao, Benjamin and Rao, Raghav, "Using Divide-and-Conquer to Solve the Multiple Discrete Resource Allocation Problem" (1998). AMCIS 1998 Proceedings. 75.