Int. J. of Operational Research   »   2010 Vol.8, No.4



Title: Linear programming formulation of the set partitioning problem


Author: Moustapha Diaby


Address: Operations and Information Management, University of Connecticut, Storrs, CT 06268, USA


Abstract: 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.


Keywords: SPP; set partitioning problem; linear programming; computational complexity; combinatorial optimisation; transportation problem; reformulation; path-based modelling.


DOI: 10.1504/IJOR.2010.034067


Int. J. of Operational Research, 2010 Vol.8, No.4, pp.399 - 427


Available online: 07 Jul 2010



Editors Full text accessPurchase this articleComment on this article