Linear programming formulation of the set partitioning problem

Moustapha Diaby

International Journal of Operational Research, 2010, vol. 8, issue 4, 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. (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=34067 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:8:y:2010:i:4:p:399-427

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().