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.
Int. J. of Operational Research, 2010 Vol.8, No.4, pp.399 - 427
Available online: 07 Jul 2010