Data Structure and Algorithm for Large-Scale Generalized Assignment Problem Which Considers Priority Orders

摘要

In this paper, the author proposes a data structure and approximate solution for solving a large-scale generalized assignment problem, being a constraint satisfaction problem. To find a desired solution from among many executable solutions, the proposed algorithm sets a priority order for resources and repeatedly solves an integer programming problem in order to reduce the nonexecutable sum of constraints. This study is an analysis of what type of data structure may be effective in raising the cache memory hit rate when a two-dimensional matrix 0-1 assignment variable x{sub}(ij), which frequently crops up in the field of operations research, has large-scale sparsity. The proposed algorithm constructs multiple search trees, makes searches and examines which resource assignments must be changed, and retains information from the search as an arc. Two-fold "garbage collection" is performed to avoid the fragmentation of the memory necessary for the search, when performing a state space search using multiple search trees. Furthermore, a data structure necessary for the searches, in order to apply the proposed algorithm to a real large-scale problem, is described.