{"entities":{"Q2627686":{"pageid":2638429,"ns":120,"title":"Item:Q2627686","lastrevid":44525049,"modified":"2025-11-23T13:39:00Z","type":"item","id":"Q2627686","labels":{"en":{"language":"en","value":"Probabilistic multistart with path relinking for solving the unconstrained binary quadratic problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6724925"}},"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":"Q2627686$699588D4-C1B2-44AB-B7A1-FF27E6C4C0BC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1d91da04af4477704e727df7ebc83ff1592d837b","datavalue":{"value":{"text":"Probabilistic multistart with path relinking for solving the unconstrained binary quadratic problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2627686$4655EEC6-0FA9-4EB2-919C-4CD42E32AC8F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8efb6c4c201b0103926f31a3fc7156ccc5d2332b","datavalue":{"value":"1362.90308","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627686$91587FEE-7916-4C48-84D5-95662E84A592","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9c6807d0e618ee19efa7e7a4014cf710150913fa","datavalue":{"value":"10.1504/IJOR.2016.075647","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627686$4F97BC14-E442-4950-951E-D46BE8DAA05F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbaaecaef2dfa668ea21477d02b4828ae0a87bbe","datavalue":{"value":{"entity-type":"item","numeric-id":405666,"id":"Q405666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627686$4B960854-1558-4F26-AE39-1AAE9E4C06AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"27250f49d9c3d87280064d228a43b748b71314df","datavalue":{"value":{"entity-type":"item","numeric-id":206978,"id":"Q206978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2627686$42042B61-2AC9-4AED-8E67-0B4C4684081F","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":"Q2627686$062B482E-09DF-45B9-80F2-35DE76F37D56","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7d49858a0afe4b614990a77fa152712e1ae2b828","datavalue":{"value":{"time":"+2017-05-31T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2627686$E34DB8CF-24E0-417D-A096-FCB04B7B1208","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"149f51160900b162b5174cf029022e14dc78c17c","datavalue":{"value":"Summary: The unconstrained binary quadratic problem (UBQP) has been shown to be an excellent framework from which to solve many types of problems, both constrained and unconstrained. In this paper we investigate a solution technique for UBQP that is based on perturbing a solution by drawing from the distribution of variables' estimated effect as determined via an unbiased design of experiments (DOE) sampling of the solution space. Solution perturbation is followed by a steepest ascent local search with path relinking. A simple implementation on benchmark problems compares well in time and solution quality with published results on benchmark problems of size up to 7,000 variables. A new set of larger problems having up to 15,000 variables and with non-uniform magnitude distributions of the elements in Q are also investigated and provide evidence that magnitude distributions of \\(Q\\) values affect problem difficulty. These large difficult problem instances required a more sophisticated path relinking approach as well as dynamic adjustments to perturbation sampling.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$1B44036B-52A8-4824-9DC9-B146A07262AA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627686$66BF7FDE-5252-4A8F-8A97-9BC403AA9AA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e038e5e16128fe63d90643b4c4804d63f3db1339","datavalue":{"value":"90C06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627686$1E3BEBAC-9315-4A41-A22B-6773867CE67B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627686$36652362-2E39-4133-9D3C-38078FF24210","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"148ce879e3dee4af517b4a003298ac5e726eeebb","datavalue":{"value":"6724925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627686$AB2FFF83-11CC-4E2E-8821-CC0F73D8C3C3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7a2a708c2266b35df0ca8aa213080d5f6635090","datavalue":{"value":"multi-start heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$7674E1C8-B94C-4F85-AF34-4C926995E40C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d1714889db0e81aa4538972a2f136ecd908d120","datavalue":{"value":"path relinking","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$6C8DBC5A-5D75-45EF-ADEC-CC4CAC1A9046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5eb6eade9f2ab11e24f7afe7274dc5f1ce06497c","datavalue":{"value":"unconstrained binary quadratic problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$BCE63258-DC73-45AC-86B1-921B7D21B7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ce42fd8ceea18a453e24b93b8e6c9c2672a1af8","datavalue":{"value":"UBQP","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$6731123D-9EFB-4F3D-9452-213B2CE7DC02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36957d7e632ee938df3990fd3662ec253f74cca5","datavalue":{"value":"preprocessing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$360789C0-59CD-4252-B3B1-230436F2702B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea1ff5a5e657abc0a392084b74b3342d23f2f4c9","datavalue":{"value":"local search","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$A85D84D0-CEA5-43B8-895A-9076FCC1A0BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac6b6db170f19496302d24710afa5c418e801105","datavalue":{"value":"design of experiments","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$F5888EE6-CFDD-47D4-90CB-2734B65FFBDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3eea3a23482e6c6d2e7f9c4859735b9486a85adc","datavalue":{"value":"DOE","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$31C75A27-4363-4A28-AF68-FE476DF23F39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e0b62190bc9e1d125dd1db5ec7a5c1e64c1358a","datavalue":{"value":"benchmark problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$4287B0AD-3C4E-499D-B082-E61DD304C857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3134a52ad2ddbcf0c56fe51f7d45f8bb331625ef","datavalue":{"value":"solution perturbation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$F9CDC0B9-FFB1-4457-8370-CCC535B2674A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb25bddfac6e1ec33a628008c9f0e674c6069a00","datavalue":{"value":"probabilistic multistart","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$C86C3E6A-77A8-4301-B01B-8796D08E52F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e17123d3082e5cb0276a9eabb5573672486a89f6","datavalue":{"value":"perturbation sampling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2627686$BF69B428-886D-4D48-90AA-37E1EA3438C4","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":"Q2627686$66505427-775B-4B9A-8FB5-6936AD1E037D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d98da5d909e4802859b71cc3a632f1d57d506c1","datavalue":{"value":"https://doi.org/10.1504/ijor.2016.075647","type":"string"},"datatype":"url"},"type":"statement","id":"Q2627686$970AF501-8CB8-49EE-BEAA-5D8879C21B15","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"437e129a1d7dcc6835abc186c083ac7797c0c888","datavalue":{"value":"W2320503935","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2627686$91A26E29-871B-4BC1-98E9-FC618014D31A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"014852e9a5f8c87cd0b4da6140df163e257f9069","datavalue":{"value":{"entity-type":"item","numeric-id":2253377,"id":"Q2253377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4aa8f9779f2cb111cb731458d71831546207410","datavalue":{"value":{"amount":"+0.9048057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2627686$C3CF979D-B796-4603-BF91-0D326DED3E49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6be8cd379ba7b5e9965763d2a71991d112cad78d","datavalue":{"value":{"entity-type":"item","numeric-id":702730,"id":"Q702730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"271ac646861fc9f4c5de57c2d96d7aedc2973d73","datavalue":{"value":{"amount":"+0.8897269","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2627686$17CBA66B-D1E7-4EDA-A0FB-FC95E75A3DB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fee95fbcf64acdcd249f4ca219a671cd88d999ae","datavalue":{"value":{"entity-type":"item","numeric-id":405668,"id":"Q405668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4231fae28e0af7efc37865bc36082f0c76be03a3","datavalue":{"value":{"amount":"+0.8570585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2627686$A8836FAE-2AE2-4010-A452-7A7C35EC97BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2986998dd7213f13a77ed379d385474dee7df3c","datavalue":{"value":{"entity-type":"item","numeric-id":5082240,"id":"Q5082240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6f5b67cc1e60877ffe951b6ffa85df217f42b33","datavalue":{"value":{"amount":"+0.8539336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2627686$10A1DBFD-2317-4F40-AD5C-C5C2CB325618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"abe03f0c0f2b87c9fba65877cbbebed18bc7d986","datavalue":{"value":{"entity-type":"item","numeric-id":5429295,"id":"Q5429295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"094b4ecd6a97e08e86a1463a26e0399888171996","datavalue":{"value":{"amount":"+0.8480965","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2627686$ADE7E03B-B2D0-4EB3-B6CA-0D5D51B74081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c1e48add161bd84144a961664d7f950e7014916","datavalue":{"value":{"entity-type":"item","numeric-id":5246827,"id":"Q5246827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2d19c7007804dfd1793de5b269f02a91f118677","datavalue":{"value":{"amount":"+0.8480263","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2627686$5851E49A-4735-4E6B-B719-C440CBC6A91E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80659a00b30cb92cb1b1a7501776d686eff0a315","datavalue":{"value":{"entity-type":"item","numeric-id":5491984,"id":"Q5491984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45e0b44c85b1c28d355523285733aa595e0da16f","datavalue":{"value":{"amount":"+0.84698457","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2627686$C6226CAC-72B2-45A9-A91F-1F73A9450731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa5a4e2317f609916ec7049d6d5a24cdcbebab8d","datavalue":{"value":{"entity-type":"item","numeric-id":464982,"id":"Q464982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cae7bc27c5d5e0239458baf1eec09d94fe7df1d","datavalue":{"value":{"amount":"+0.84578824","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2627686$D4318B54-2D63-4964-A3A5-39CE5A5798CD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2627686","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2627686"}}}}}