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.

DOI: 10.1504/IJOR.2010.034067

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