Solving Large Scale Set Partitioning Problem to Optimality in Parallel

Van Hoai Tran
Faculty of Computer Science and Engineering, HCMC University of Technology

Abstract
Various practical applications can be modeled as a set partitioning (SP) problem. Instead of modeling the problem as an assignment model, in which variables correspond to a mapping of demands to resources, all possibilities of assignment are generated explicitly or implicitly in a systematic way. Then, a solution method to the generated SP problem is to choose the best subset of them to cover all demands. The obstacle is that the SP problem is NP-Hard. This paper presents a research to computationally solve the problem on parallel computers. The parallelism is performed on a sequential branch-and-cut based solver which employs advanced methods and techniques to the problem. Computational results solving solve large scale instances generated from different practical applications on a cluster of workstations show that optimality can be reached within a reasonable computation time.