Linear programming formulation of the set partitioning problem (Q604761)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear programming formulation of the set partitioning problem |
scientific article |
Statements
Linear programming formulation of the set partitioning problem (English)
0 references
12 November 2010
0 references
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)].
0 references
computational complexity
0 references
transportation problem
0 references
reformulation
0 references
path-based modelling
0 references