{"entities":{"Q431008":{"pageid":432775,"ns":120,"title":"Item:Q431008","lastrevid":61779213,"modified":"2026-04-11T01:35:53Z","type":"item","id":"Q431008","labels":{"en":{"language":"en","value":"Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6050444"}},"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":"Q431008$42AF5C96-2650-4FBA-8B1D-5C400E495D02","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6c98fb1da590e04eb143adb4830320aaebda6ee2","datavalue":{"value":{"text":"Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q431008$5BB8675E-D327-42D7-80E7-2593C0DA3E6D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fcd34b236c3296ff156f94ace7c3ac3aba95b9d4","datavalue":{"value":"1270.90045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431008$E13AAEEA-8455-4725-A31D-38904F9A7799","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a3b869b7cd023bf16ecb2b7e7d6f76b9045a2b8","datavalue":{"value":{"entity-type":"item","numeric-id":172145,"id":"Q172145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$DA7D9794-8106-430B-860D-C68483DCBEC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc2276bfead9878d5e4eb68cfdff70ba5ff83ab0","datavalue":{"value":{"entity-type":"item","numeric-id":296967,"id":"Q296967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$B49594E2-56F2-49ED-AA35-4BCB46533080","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$5EDB2220-44D3-4CFA-8471-407A6809D64C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f03a3c04b271440e0460d17b6cd1c270f9267efc","datavalue":{"value":{"time":"+2012-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q431008$11E181F9-D4C9-4F5C-A7B5-8D51063B2823","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1dd0c4589046ced720be2f1a1be16754650b0836","datavalue":{"value":"Semidefinite programming (SDP) bounds for the quadratic assignment problem (QAP) were introduced by \\textit{Q. Zhao} et al. [J. Comb. Optim. 2, No. 1, 71--109 (1998; Zbl 0904.90145)]. Empirically, these bounds are often quite good in practice, but computationally demanding, even for relatively small instances. For QAP instances where the data matrices have large automorphism groups, these bounds can be computed more efficiently, as was shown by \\textit{E. de Klerk} and \\textit{R. Sotirov} [Math. Program. 122, No. 2 (A), 225--246 (2010; Zbl 1184.90120)]. Continuing in the same vein, the authors show how one may obtain stronger bounds for QAP instances where one of the data matrices has a transitive automorphism group. To illustrate their approach, they compute improved lower bounds for several instances from the QAP library QAPLIB.","type":"string"},"datatype":"string"},"type":"statement","id":"Q431008$4DCA89B5-C6DA-4872-809C-84C90062C422","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e163e4f3415749f33672d8f8826866902fa1e334","datavalue":{"value":{"entity-type":"item","numeric-id":586527,"id":"Q586527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$BB04A7B5-9CB2-4BE8-A5FD-D1989F834E61","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"747ca2a29edc80ef77db4b4376cee27cb80d39e3","datavalue":{"value":"90C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431008$E9BC03A4-2BA6-44AA-8652-832CB513CD91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5666730139cd54a76def570b360d5dca402099e8","datavalue":{"value":"70-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431008$79571123-C8AD-4FEA-AB24-319A486D6775","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91448e1b95fa68ae8b9eb55d320ef08abd7e19ae","datavalue":{"value":"6050444","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431008$F68BE5C4-D778-4368-A0B9-B86913662E82","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efa62ae0cc3a97f10cfd90d9a759cd71de2f980b","datavalue":{"value":"quadratic assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q431008$49914483-C47D-42C5-AC8A-A6B16E2CA5E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c0145dbb175f229104a70deaeffc1099143a20d","datavalue":{"value":"semidefinite programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q431008$1888ADFA-57E5-4779-A50B-8ABE7DEB4153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e03f355bae9d662ebeebdf5e7685410cae41cdff","datavalue":{"value":"group symmetry","type":"string"},"datatype":"string"},"type":"statement","id":"Q431008$1F0FFBF8-F262-4CDA-B8A6-D41F2E3E6125","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q431008$75924849-8ACD-4B39-94C3-194BF9B0A578","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"6cfd7ab964326af5be96cef3e62f8debf71291ab","datavalue":{"value":{"entity-type":"item","numeric-id":13502,"id":"Q13502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$8824C33A-FFD3-4CE4-BEE9-D604A7B498C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7c5814a0a3b47b1b5455e3eaa345adcdfd08dbf3","datavalue":{"value":{"entity-type":"item","numeric-id":16192,"id":"Q16192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$77B68503-23BE-4B5D-9295-02F665354682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"83793d2d04b664d34057899871316417b4be46c8","datavalue":{"value":{"entity-type":"item","numeric-id":16766,"id":"Q16766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$D2715F6D-C982-4E3B-ACB9-DBA2EFF8E42E","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":"Q431008$92084C1E-93D1-4EC4-B776-DC3733D5BD5B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d9ea8f44876d145e001e1e7986039e40c6cc3919","datavalue":{"value":"https://doi.org/10.1007/s10107-010-0411-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q431008$9F0CC782-084D-4F28-B36C-33DFD5CECC3A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7083c7f101610daf908484f3088f7e1cab35478a","datavalue":{"value":"W2109156232","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431008$FAD6D00F-9B69-4FDB-9030-0C8B479F4044","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1087b4422a55041aec8240b9764f6b9e405635e","datavalue":{"value":{"entity-type":"item","numeric-id":1403282,"id":"Q1403282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$90FF2624-B0F0-4C59-A6AC-EA1A3EDEABEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"695831e6a22dc8db5e8a4d8f0fb4b2e93bdc8cee","datavalue":{"value":{"entity-type":"item","numeric-id":3546555,"id":"Q3546555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$ADD61FF6-00AC-4A96-AAD1-5D0A327F8AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80a4ef72193cbd63f4d1e1f897e7e2ad0c2f8c57","datavalue":{"value":{"entity-type":"item","numeric-id":5470217,"id":"Q5470217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$6C3F82A9-6492-4146-BDD6-AB63E24D3328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d1ecfdd248b413374736fd893e9b1ced1508f56","datavalue":{"value":{"entity-type":"item","numeric-id":1361076,"id":"Q1361076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$882F0EEC-87C8-4B40-9D72-60E36FB5DDA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fe234b893fe639d56d0ff3a37c6535b70c104f1","datavalue":{"value":{"entity-type":"item","numeric-id":4231664,"id":"Q4231664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$020DE3F8-82C7-492B-94B7-5E2DAFD2D9EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e84fc29e9a2e2ce028e7eeb40f2dcaffa9fb726","datavalue":{"value":{"entity-type":"item","numeric-id":1186944,"id":"Q1186944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$A33E3E9C-4880-4F9B-B383-EF3A2F6DE760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33edac45558a11a5c3028854b5575fd6b9869306","datavalue":{"value":{"entity-type":"item","numeric-id":5470794,"id":"Q5470794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$28479946-5535-4A49-9C4F-CED4F54EF014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e23affce7c764baacc0ec618aafee4a7df76daf4","datavalue":{"value":{"entity-type":"item","numeric-id":847851,"id":"Q847851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$E9954129-27C7-4686-A48C-971DD6D5F8FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4fe65450c4336601ab925e5e1a300be2242c084","datavalue":{"value":{"entity-type":"item","numeric-id":3648520,"id":"Q3648520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$0D650810-E2AC-4340-B928-3F8B22433289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"066d1a7d660d45e9773d314b0eddc69b5f3821f9","datavalue":{"value":{"entity-type":"item","numeric-id":1878418,"id":"Q1878418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$40E62BEE-EECA-4E40-BB32-FF4DBA951411","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"407c1158d82d95ac4061361d9ea545393237fb6b","datavalue":{"value":{"entity-type":"item","numeric-id":3961697,"id":"Q3961697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$F48124E1-5070-4F2F-B343-0A1957D1BB2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dce4985f6cbf3d8009e6b46a8c38dfdc42d02e4","datavalue":{"value":{"entity-type":"item","numeric-id":5627967,"id":"Q5627967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$ECBC8208-6607-42CB-B2CB-F6CFCAF9EAA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f73eb84a543b338a4a079febb7b97c03a91da92f","datavalue":{"value":{"entity-type":"item","numeric-id":5633847,"id":"Q5633847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$148AA016-07D3-4665-945F-D93E54D062EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4586e18d286bc53ff17bd968c9cc311e4cefe19f","datavalue":{"value":{"entity-type":"item","numeric-id":3083337,"id":"Q3083337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$633AA0E1-727C-49F9-B298-D8595E14AD3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c1fb712e68bc2147a8ff83b47dd3a5163a9b42","datavalue":{"value":{"entity-type":"item","numeric-id":2726515,"id":"Q2726515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$A98D8653-3B40-4FE8-A2F8-264C27AE8C04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58db2de6c0a02fb419fec1468e627275970b2a7d","datavalue":{"value":{"entity-type":"item","numeric-id":834180,"id":"Q834180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$7D715671-E614-4793-BC7B-027D749830A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35536d3d9129eb550f8f6f3bd44f07be034b92fa","datavalue":{"value":{"entity-type":"item","numeric-id":3547598,"id":"Q3547598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$D75BC404-4152-41F3-AE18-A75DBC8913E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e5f4133e04bfc3c5f5a968116ba461a1733fc52","datavalue":{"value":{"entity-type":"item","numeric-id":4504796,"id":"Q4504796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$A6750F41-397F-43BB-8105-2A373FAC16CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"238f0b6ea39b4adef622d3d1959e6ddf9dccc1da","datavalue":{"value":{"entity-type":"item","numeric-id":4758117,"id":"Q4758117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$56D50FA9-F3D2-4AF7-A491-18E5AA77D644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0101ecaf7871587ba4d9df0da9e5a32d516452f","datavalue":{"value":{"entity-type":"item","numeric-id":1386486,"id":"Q1386486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$680B5348-F283-40BD-9ED5-7BE5FF9722EE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ca8a2274f16fe40a408a135660864fa033788623","datavalue":{"value":"10.1007/S10107-010-0411-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q431008$367FE0CB-E4EB-4F64-86B3-DBE3D922DF4F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b518b1ad440e845a7a509068a23a3564b08e2d2d","datavalue":{"value":{"entity-type":"item","numeric-id":3466781,"id":"Q3466781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92fe541b8493502e43e4e0105485b629e943d4e0","datavalue":{"value":{"amount":"+0.8997137546539307","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":"Q431008$BA6279F3-60B7-4624-B365-E31E13FE8B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd0060bd5b47045aeae1f8868ca247cbb967f5ef","datavalue":{"value":{"entity-type":"item","numeric-id":847851,"id":"Q847851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb6917dae84dab4a01012883b2d174282fb752ee","datavalue":{"value":{"amount":"+0.8697535395622253","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":"Q431008$BC411A93-51ED-469F-ADC9-28796A1FBB67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cce43333d70c0490662fadee194b118422b9bed","datavalue":{"value":{"entity-type":"item","numeric-id":4801579,"id":"Q4801579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2c5e98198080b40dcdeaeaf411f9a42a1355006","datavalue":{"value":{"amount":"+0.8624790906906128","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":"Q431008$E13E0F72-CACB-4E94-8FAE-3731EEFD71ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9aa6bebcb59b8b08936515a5b5670943266df64","datavalue":{"value":{"entity-type":"item","numeric-id":3169078,"id":"Q3169078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"006666c9f9ba7266aae216ec02e2a5537cea7812","datavalue":{"value":{"amount":"+0.8533841967582703","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":"Q431008$604A08BD-3FFE-4061-9E83-EF3DD9999FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af351b34f78e517f86ec83f97f1730132b261c70","datavalue":{"value":{"entity-type":"item","numeric-id":3083337,"id":"Q3083337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8884ed48b2963379e1e263d9a9e400746fc32f45","datavalue":{"value":{"amount":"+0.8457946181297302","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":"Q431008$9D06497D-55C0-487E-B8B0-82EEB790FBBE","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"bee1ddd2bb542a0e64ca96574e4fab1bba361385","datavalue":{"value":{"entity-type":"item","numeric-id":57074,"id":"Q57074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q431008$4839A5D0-D7B6-43B3-B8BB-6E952FA7CD0E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improved_semidefinite_programming_bounds_for_quadratic_assignment_problems_with_suitable_symmetry"}}}}}