{"entities":{"Q604761":{"pageid":606537,"ns":120,"title":"Item:Q604761","lastrevid":63041418,"modified":"2026-04-11T09:57:24Z","type":"item","id":"Q604761","labels":{"en":{"language":"en","value":"Linear programming formulation of the set partitioning problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5815543"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604761$4085FE15-2CC9-4EDF-A3CE-BABDB041074C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10dc2eae45b711a7407aee30e4c80f4105df5d44","datavalue":{"value":{"text":"Linear programming formulation of the set partitioning problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q604761$AC9462E5-A262-4882-AC8D-453A1196C75B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"240029e497503bf1bb87cfe0d2f1286b0c6bb071","datavalue":{"value":"1205.90244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604761$5B2CB3FA-6B8C-4261-85AE-BA6F237DB87B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e23f6843328b9d752a68092c02e8427f0cc57944","datavalue":{"value":"10.1504/IJOR.2010.034067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604761$1D09F3B5-D720-4FAC-A44C-4A76E7107D8A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd1c10a678296ae0d3c8e792faba63ad420ee5f1","datavalue":{"value":{"entity-type":"item","numeric-id":604760,"id":"Q604760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604761$1593959C-6E95-4C24-8221-C99BCFEE25E2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2416e8a5c76a3e001f6e57b132d70eaeca49c502","datavalue":{"value":{"entity-type":"item","numeric-id":541285,"id":"Q541285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604761$55B55E20-4FB2-48CB-93C4-548D96E92403","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5f9e839d2a997fa299b899aeddb064bd0b055cfd","datavalue":{"value":{"time":"+2010-11-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q604761$3E40E8B3-C0CA-4AB5-8AE3-22758E7714C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9e66620a1269d72b273c57ab9361c4a5efc04c23","datavalue":{"value":"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)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q604761$6D21E810-6869-41D1-9017-E0D94DFBB7DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604761$4CB8BDEF-94A5-4463-B55F-741952071F0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604761$4C991537-E7C2-46FB-A713-E3E19ADB3F19","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68b68c499c06d2a86c8f652107ddf7f7c3710780","datavalue":{"value":"5815543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604761$2698B7DE-C60B-4020-85D3-90B8719AF375","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q604761$E4B110DB-615A-4BF4-BE93-026AC70A6427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"248b10e56fbedd9274c469d28ff709164505189b","datavalue":{"value":"transportation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q604761$3EC61C98-67F3-4508-9FF8-2AAB6DB7EA4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0b397f41b482fa333d94724754f88adfeff0e9a","datavalue":{"value":"reformulation","type":"string"},"datatype":"string"},"type":"statement","id":"Q604761$9B42C4ED-F3A7-4E77-8656-B43D479909EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4ceed1fc554450bfe16853e237e1fb732065a53","datavalue":{"value":"path-based modelling","type":"string"},"datatype":"string"},"type":"statement","id":"Q604761$52464BAD-529F-46D4-A5F2-7B08D163DDD6","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q604761$3354ED70-6845-48DB-8593-FC08A2677E8F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"01aa3ef478d7bc38a7efa6ee3fb0c2d8f64dc129","datavalue":{"value":"https://doi.org/10.1504/ijor.2010.034067","type":"string"},"datatype":"url"},"type":"statement","id":"Q604761$BE0EEFE4-E519-4FBC-862E-E815267DB3A7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"410afbe687c59e970bae5c8b718dd7fdd8ec38a0","datavalue":{"value":"W2105554874","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q604761$00550584-CFBC-411F-94BE-47E0343D769F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b20b01dcc455167376e2e1a7436c8d0b24beed6","datavalue":{"value":{"entity-type":"item","numeric-id":2456638,"id":"Q2456638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"795769869541e8e67b5535cc402df53666759455","datavalue":{"value":{"amount":"+0.7975907325744629","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q604761$D7A4E203-A4C0-4999-9C57-3291D2A81CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0b794d6cba39a9af7e1730fa4da7d8cbb7461f0","datavalue":{"value":{"entity-type":"item","numeric-id":3520785,"id":"Q3520785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c55596e7f16ead9ee2957ef0e57e4dbde3214a1","datavalue":{"value":{"amount":"+0.7906973958015442","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q604761$50C7F930-DBFA-49C9-B9F3-393309F2BF32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e453da044e0cb535c60ce21fdb2aa93955f40a31","datavalue":{"value":{"entity-type":"item","numeric-id":975796,"id":"Q975796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f4ab90273dda89d63befd1df27217ea041cff88","datavalue":{"value":{"amount":"+0.7678146958351135","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q604761$EF6E3EB8-B1D6-4A3D-B5B0-56CF92F1457C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5339f469a70fcb142666d041e156af2f90e0e748","datavalue":{"value":{"entity-type":"item","numeric-id":1265886,"id":"Q1265886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"552671562d466fd74fddac453ceb620e5cb26a31","datavalue":{"value":{"amount":"+0.767299473285675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q604761$256D2AA7-5556-4248-9924-3C46F5D4EA17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de5637f2c114be0330545f7493097f260bddca38","datavalue":{"value":{"entity-type":"item","numeric-id":1123128,"id":"Q1123128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56b3f85a1573dfcd4dc1c12bfac016644e2aeaff","datavalue":{"value":{"amount":"+0.7640999555587769","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q604761$AB718B76-3632-4D26-920B-9488E32DC3FE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Linear programming formulation of the set partitioning problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Linear_programming_formulation_of_the_set_partitioning_problem"}}}}}