SOLVING LARGE SCALE SET PARTITIONING PROBLEM TO OPTIMALITY IN PARALLEL

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.