Article ID: | iaor20105259 |
Volume: | 8 |
Issue: | 4 |
Start Page Number: | 399 |
End Page Number: | 427 |
Publication Date: | Jul 2010 |
Journal: | International Journal of Operational Research |
Authors: | Diaby Moustapha |
Keywords: | programming: linear |
In this paper, we present a linear programming (LP) model of the set partitioning problem (SPP). The number of variables and the number of constraints of the proposed model are bounded by (third-degree) polynomial functions of the number of non-zero entries of the SPP input matrix, respectively. Hence, the model provides a new affirmative resolution to the all-important ‘P vs. NP’ question. We use a transportation problem-based reformulation that we develop, and a path-based modelling approach similar to that used in Diaby (2007) to formulate the proposed LP model. The approach is illustrated with a numerical example.