Title: Linear programming formulation of the set partitioning problem

 

Author: Moustapha Diaby

 

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

 

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

 

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: http://dx.doi.org/10.1504/IJOR.2010.034067

 

Available online 07 Jul 2010

 

 

Editors Full Text AccessAccess for SubscribersPurchase this articleComment on this article