{"entities":{"Q1067975":{"pageid":1078727,"ns":120,"title":"Item:Q1067975","lastrevid":69557019,"modified":"2026-04-13T07:49:28Z","type":"item","id":"Q1067975","labels":{"en":{"language":"en","value":"An exact algorithm for the general quadratic assignment problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3930717"}},"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":"Q1067975$166EB744-3645-4C42-B5DA-3FC1504C8017","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ea2247a542da5bcd754deb70e7e74814ce9d052f","datavalue":{"value":{"text":"An exact algorithm for the general quadratic assignment problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1067975$1ACBE852-71C4-4874-A68B-2CC901DB1602","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cee7cbb1bb7102fc284a571bf913e9e29cc1c43c","datavalue":{"value":"0581.90054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067975$388A38DF-D4DF-43B5-8FC9-2AD88DBFA1F1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b31abe175243ba8edbd0e08916fd9c0f42c601ac","datavalue":{"value":"10.1016/0377-2217(86)90303-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067975$5F0E59AF-E600-4200-8A6B-E50D718A2B8F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd6c20a0e894a37cd95da4b72242256723f3ffe2","datavalue":{"value":{"entity-type":"item","numeric-id":1067974,"id":"Q1067974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$93434E86-6BC4-4CD1-9037-017B01D30AC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ed9c22a7870a733e2823f96d22dde015e7d09a09","datavalue":{"value":{"entity-type":"item","numeric-id":595501,"id":"Q595501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$E21A66E9-0A70-4598-BD17-6A8FDDDEAF40","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$69CB3892-70D5-4CE1-9F9A-AFEF4767E5EC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1067975$403BB532-6F7D-445A-898E-6EDAEA7BD7E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d35b304848f72356eb6972107e9b604aca3c0a4a","datavalue":{"value":"We develop an algorithm that is based on the linearization and decomposition of a general quadratic assignment problem of size n into \\(n^ 2\\) linear assignment problems of size (n-1). The solutions to these subproblems are used to calculate a lower bound for the original problem, and this bound is then used in an exact branch and bound procedure. These subproblems are similar to the 'minors' defined by Lawler, but permit us to calculate tighter bounds. Computational experience is given for solution to optimality of general quadratic assignment problems of sizes up to \\(n=10\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$27012EA6-524C-4B62-BD85-B6B881B9CE58","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067975$37A564C2-FC67-4053-839E-F9B953A6B8C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067975$4DD8D35C-291D-420B-A7B5-C388BEFE22A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067975$C634A9B6-FB59-48B1-A5F2-0415482CDC7D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1896d6b23eb0323141cb79047284aca4d1b075e8","datavalue":{"value":"3930717","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067975$D6F4D4C4-0FD2-4213-BE93-DF20384C0443","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95dc85bae11a31fd457cd4c048f448c7257323e4","datavalue":{"value":"design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$3F2A99BD-3BF0-4DDE-8EA0-46AB4028B836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb19deb4ad7feb1ad8a88cce5a5e48f0e5a75812","datavalue":{"value":"location","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$862A959E-2113-4306-A240-43094080F57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"081b79b4adfd295e5dab936c22cabd29ef04eede","datavalue":{"value":"linearization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$4ED256BE-D616-462E-BC74-CAB987936094","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$4DFE88F9-7AD1-4F7B-971D-5ABA05D9C736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58ff8e8cfd34e94b2ac9a5d60bd899481f04e4dd","datavalue":{"value":"quadratic assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$EA955D4D-0433-482C-8885-85CBA803C5DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ad76496c40ff2bf1c5db485da43d2e8a617ea17","datavalue":{"value":"linear assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$EEFD40E6-0FCD-4917-80FE-9D6746A1FE5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$364E5966-A6A5-406E-A952-ADE026409EF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef9f24f01ae2ac90279d8e83c1aee0f4f7c88432","datavalue":{"value":"subproblems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$8EBF4354-7289-49BE-B5A0-F6E9D690B434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eef6d82b681f54b02898fc4286ed1dbb302fdb8c","datavalue":{"value":"Computational experience","type":"string"},"datatype":"string"},"type":"statement","id":"Q1067975$311D4423-B70B-4464-80EA-BAF89B6246F3","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":"Q1067975$CE40B813-7807-41EE-B107-C061DEBA47FA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7ce11a00c45d4fade46aed50016d0181df12efe0","datavalue":{"value":"https://doi.org/10.1016/0377-2217(86)90303-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1067975$0BC45737-1B1C-47EA-9DB6-A647C17DD1D9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"70df5051af02dc1435201e7890418e6f7544870f","datavalue":{"value":"W2024640194","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1067975$EE6F8CA1-753B-44E3-9B33-2660878AA179","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7a7b577cc6c7e3999f1721c7f68d14b8c3f5773","datavalue":{"value":{"entity-type":"item","numeric-id":3870675,"id":"Q3870675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$42A6CDA8-40ED-4474-B365-DCAC88E87718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751eb5a89cb0feb891593293f8f74031111be3d4","datavalue":{"value":{"entity-type":"item","numeric-id":4767119,"id":"Q4767119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$92B4A417-AEAC-40FE-86A9-CA28A79A6372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3dd6e2f0dd1e4341a97e3c82bc98a187197a7be","datavalue":{"value":{"entity-type":"item","numeric-id":4173192,"id":"Q4173192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$217BB3DA-2FCE-4149-8E4E-8A1F2BA94063","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15ccd1c6e44d65eb4acbc8daad6efebdf54c3737","datavalue":{"value":{"entity-type":"item","numeric-id":1141079,"id":"Q1141079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$6D688048-4D32-4EAF-809B-5E36CAA69068","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"728e84fd2a1f3982a31c27f837c91f2801ad905c","datavalue":{"value":{"entity-type":"item","numeric-id":2265947,"id":"Q2265947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$5653B2FB-03F3-4BAA-9474-CD252A8B7EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00c054224ddea95e6641758de7a70e53e4192923","datavalue":{"value":{"entity-type":"item","numeric-id":5728874,"id":"Q5728874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$E18EE10A-CBF1-4FAF-B271-905AF3E4B150","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a5c70f7e3e4d9c90aee687699a4a111d219cef0","datavalue":{"value":{"entity-type":"item","numeric-id":5588266,"id":"Q5588266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$253544AB-F8D9-4B97-BD83-BA7A1B0DE0D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f37b4000e7530ae7a4cb32dbd2daa3d71f806a5b","datavalue":{"value":{"entity-type":"item","numeric-id":1247369,"id":"Q1247369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$E6A6C207-E8C5-406A-9F60-527FD9E10AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e16f06f2872411f18eb374dd952035d531edb31","datavalue":{"value":{"entity-type":"item","numeric-id":3277809,"id":"Q3277809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$90A466E7-717A-46B0-8161-555997F769FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a81de77e22d968911af238e7f6037ed40ec38e74","datavalue":{"value":{"entity-type":"item","numeric-id":2778995,"id":"Q2778995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$0BEB99E2-7970-478B-8329-7BB565EB0A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78f0515351befe734f97e0de13c5536c5f29664d","datavalue":{"value":{"entity-type":"item","numeric-id":4194705,"id":"Q4194705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$B3CB218F-7502-41C8-9973-FD6E64BFCFBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2020388ea3bf9bf832846ba1c4b4c2a4a4cfd62","datavalue":{"value":{"entity-type":"item","numeric-id":3902819,"id":"Q3902819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$94724D5A-5DC3-4CF5-9A5E-CDF1F4613678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00aa6a55b9359046fa0039dd5eb6421b713c2cc7","datavalue":{"value":{"entity-type":"item","numeric-id":5620476,"id":"Q5620476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$D6BBE6D0-7CC0-4A5C-9726-410F7F10B095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"638c7a1a5cb58e09f525705218fe52337dc92a08","datavalue":{"value":{"entity-type":"item","numeric-id":5666155,"id":"Q5666155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$D504B2AE-2434-48E0-9B6E-0DAD69696FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8806df00f54946879e96f1e822c7709775a3f7bb","datavalue":{"value":{"entity-type":"item","numeric-id":3276270,"id":"Q3276270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1067975$317133CB-B6E3-437C-80DD-55C17EE64689","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f067921fb309f840ead2005ae66d3119f70434bc","datavalue":{"value":{"entity-type":"item","numeric-id":1343146,"id":"Q1343146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4382390a4a9dce611846983f781cf5492f325858","datavalue":{"value":{"amount":"+0.8907890915870667","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":"Q1067975$1A3FC179-A037-450F-81C3-C8BC3B994A4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a77c63e4b936bc03ee1c948eb2d59a1acf81878","datavalue":{"value":{"entity-type":"item","numeric-id":3475126,"id":"Q3475126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cf02634f8b4739584d5e9d16e84a51793ded0ad","datavalue":{"value":{"amount":"+0.8810272812843323","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":"Q1067975$C5F81EC8-D3F7-4E84-B3EE-27FA3689F914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56e529618c43727ccba2335d7a18702f00a81d68","datavalue":{"value":{"entity-type":"item","numeric-id":976396,"id":"Q976396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"158af954da976b6690f473a39910d46149abee29","datavalue":{"value":{"amount":"+0.8592870235443115","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":"Q1067975$224378CD-366E-41CE-98C5-1B989C898BFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dec593ae8721ad4d00664f1c94d3a1017d905591","datavalue":{"value":{"entity-type":"item","numeric-id":4247462,"id":"Q4247462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b328206491fc87e0cbe5a98ad78e8a1193fa1711","datavalue":{"value":{"amount":"+0.8541349172592163","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":"Q1067975$69C25FF3-2772-4955-A7F3-F36569521D55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0b29932e7e783778ea67c0e7e1948c98108bd6e","datavalue":{"value":{"entity-type":"item","numeric-id":1001198,"id":"Q1001198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31cbd9769ce64487af4e90e5b7469d113cf5cb9d","datavalue":{"value":{"amount":"+0.8539305329322815","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":"Q1067975$0A4C5E37-99A9-4E04-84C5-4A681865C325","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An exact algorithm for the general quadratic assignment problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_exact_algorithm_for_the_general_quadratic_assignment_problem"}}}}}