{"entities":{"Q843394":{"pageid":845242,"ns":120,"title":"Item:Q843394","lastrevid":64756632,"modified":"2026-04-11T22:00:51Z","type":"item","id":"Q843394","labels":{"en":{"language":"en","value":"Semidefinite relaxations of the quadratic assignment problem in a Lagrangian framework"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5613388"}},"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":"Q843394$8EB54788-5BF8-427D-8377-260B689D37E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2e2c5b58c7054cb53a0beb1894daa159abc0c38f","datavalue":{"value":{"text":"Semidefinite relaxations of the quadratic assignment problem in a Lagrangian framework","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q843394$4850E724-0347-45C0-A9F5-A7B8DDA8140A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ce725f0e1f5f87a1b52fc2f42577442b71c283e9","datavalue":{"value":"1180.90169","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q843394$FA37BDA4-D3C8-45E9-B2B6-CA684062990C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6e9484ab8bacb76802a94120ed44d7287c0e8835","datavalue":{"value":"10.1504/IJMOR.2009.022879","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q843394$2158BEE0-3CC8-4B55-A899-5BF6850EEA2E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc965ae716c844c126b9098d4bf542f5b333e4ea","datavalue":{"value":{"entity-type":"item","numeric-id":286995,"id":"Q286995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q843394$57635325-5078-45EB-8619-A2DBB42E0E12","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"08904a7410b5f731fa63153720439160d216b374","datavalue":{"value":{"entity-type":"item","numeric-id":548461,"id":"Q548461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q843394$894548D4-39D6-4932-AC2E-A179B37A4600","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"93f647a4ebf59f456db8e4a403723e6cd39fb2e6","datavalue":{"value":{"time":"+2009-10-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":"Q843394$79668CCD-EC7B-4000-9A47-AF229B8C1603","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf1965e3a0b934013fcbbbc0dff63284725ce3ac","datavalue":{"value":"Summary: We consider partial Lagrangian relaxations of continuous quadratic formulations of the quadratic assignment problem (QAP) where the assignment constraints are not relaxed. These relaxations are a theoretical limit for semidefinite relaxations of the QAP using any linearised quadratic equalities made from the assignment constraints. Using this framework, we survey and compare standard semidefinite relaxations of this classical NP-hard problem. In particular, this approach is a simple way to prove that some well-known semidefinite relaxations for the QAP are equivalent. Nevertheless, these relaxations have a different numerical behaviour and practical usefulness depending on the semidefinite programming solver. We discuss such issues by reporting some computational experiments.","type":"string"},"datatype":"string"},"type":"statement","id":"Q843394$B78979B2-59C2-4858-8C8D-AFBFACA8C2A5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ad37711539483f94ecc5e7c9236f6acd7c19a03","datavalue":{"value":"90B80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q843394$BA9B4AF7-F5B3-4CD1-BE97-E97693FCA416","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"747ca2a29edc80ef77db4b4376cee27cb80d39e3","datavalue":{"value":"90C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q843394$4AC26A98-1FE9-4EB2-94BE-E4263D377791","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6443a69a26ff08dad15763135de928780ece79ae","datavalue":{"value":"5613388","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q843394$154FA212-2EAD-4719-8CB4-8CD5327701F9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a59e0c1eb51c50ee8b2be5656da8a2be878f5f1","datavalue":{"value":"Lagrangian relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q843394$547FE971-B9D6-42E3-BC98-D3DA9B83645B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42c0731c6fa4eb4bd4d79343dfa7694b26199649","datavalue":{"value":"QAP","type":"string"},"datatype":"string"},"type":"statement","id":"Q843394$7EB2B9C9-9B95-4B87-B6E9-60EF12E20F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efa62ae0cc3a97f10cfd90d9a759cd71de2f980b","datavalue":{"value":"quadratic assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q843394$680A624F-7E03-46C8-A313-575F830F5C64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"325000c26ecc9d5e0c0a7c69bd8b392e5fcf0b66","datavalue":{"value":"SDP","type":"string"},"datatype":"string"},"type":"statement","id":"Q843394$56B75DDC-A763-4F99-BF5A-730AD7B403EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c0145dbb175f229104a70deaeffc1099143a20d","datavalue":{"value":"semidefinite programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q843394$2797DE6B-A15C-4C83-B45E-7EB09FA0148A","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":"Q843394$89996227-7E20-48AF-85CF-F35D573AEA52","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9c60743661d929f4b18a5725408c04a0a22e1db8","datavalue":{"value":"https://doi.org/10.1504/ijmor.2009.022879","type":"string"},"datatype":"url"},"type":"statement","id":"Q843394$C0F5AA81-9D1E-4046-AF01-BD6E9E821312","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b991108253d084c2a509e1f35aa1f893383bc1f2","datavalue":{"value":"W2128247163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q843394$35EAFED8-0A40-464D-948B-49BB3CAE3FFB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bef88e87f59061ce94580c4043b364f1af8b8d66","datavalue":{"value":{"entity-type":"item","numeric-id":1386486,"id":"Q1386486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d258afb5b83dfa40e6378bff29a6508d691129f","datavalue":{"value":{"amount":"+0.8916611671447754","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":"Q843394$957BBD70-4972-474C-8A76-60B8FE349B51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"945b29709e9a0bcd9d65f473b685f568dfb190a1","datavalue":{"value":{"entity-type":"item","numeric-id":5482472,"id":"Q5482472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d258afb5b83dfa40e6378bff29a6508d691129f","datavalue":{"value":{"amount":"+0.8916611671447754","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":"Q843394$2B27AB2A-67C7-49CD-B7D1-D9A077D57D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be5e0625d3cf51297eba33904be2538e31f40e57","datavalue":{"value":{"entity-type":"item","numeric-id":834180,"id":"Q834180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e5480e67f74309a72411fe67b800295e6b0cef0","datavalue":{"value":{"amount":"+0.8715918064117432","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":"Q843394$B61D78F6-B006-465B-B6B9-F19C715533FE","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":"b6fffd53bc45980f01832cf9874fab997d763023","datavalue":{"value":{"amount":"+0.8692663311958313","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":"Q843394$0D0D23A2-6B2D-4002-A737-797C12998D5D","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":"985782aa4bcb3f1221bfb7aa3e8e4173244fca8f","datavalue":{"value":{"amount":"+0.8611406087875366","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":"Q843394$F62436C5-3F7F-4B6B-8255-45EBC34C4FCE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Semidefinite relaxations of the quadratic assignment problem in a Lagrangian framework","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Semidefinite_relaxations_of_the_quadratic_assignment_problem_in_a_Lagrangian_framework"}}}}}