Linear programming formulation of the set partitioning problem
type: Item
instance of: scholarly article
title: Linear programming formulation of the set partitioning problem
zbMATH Open document ID: 1205.90244
DOI: 10.1504/IJOR.2010.034067
author: Moustapha Diaby
published in: International Journal of Operational Research
publication date: 2010-11-12T00:00:00Z
review text: Summary: 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 [the author, WSEAS Trans. Math. 6, No.~6, 745--754 (2007; Zbl 1168.90580)] to formulate the proposed LP model. The approach is illustrated with a numerical example. Editorial remark: We caution the reader that the author has claimed to provide a proof of the P=NP problem; see also the review of [\textit{M. Diaby} and \textit{M. H. Karwan}, Advances in combinatorial optimization. Linear programming formulations of the traveling salesman and other hard combinatorial optimization problems. Hackensack, NJ: World Scientific (2016; Zbl 1371.90002)].
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 5815543
zbMATH Keywords: computational complexity
zbMATH Keywords: transportation problem
zbMATH Keywords: reformulation
zbMATH Keywords: path-based modelling
MaRDI profile type: Publication
full work available at URL: ijor.2010.034067
OpenAlex ID: W2105554874
description: scientific article; zbMATH DE number 5815543