Linear programming formulation of the set partitioning problem (Q604761)

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)].