Title: Linear programming formulation of the set partitioning problem
Authors: Moustapha Diaby
Addresses: 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.
International Journal of Operational Research, 2010 Vol.8 No.4, pp.399 - 427
Published online: 07 Jul 2010 *
Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article