{"entities":{"Q1774170":{"pageid":1784912,"ns":120,"title":"Item:Q1774170","lastrevid":48472663,"modified":"2026-01-04T22:34:02Z","type":"item","id":"Q1774170","labels":{"en":{"language":"en","value":"A branch-and-cut algorithm for nonconvex quadratic programs with box constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2162528"}},"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":"Q1774170$CD130E3E-9105-4187-A513-EA4B5966639C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f242a7f016da2730bcfafeb5f199ef7404aa22d3","datavalue":{"value":{"text":"A branch-and-cut algorithm for nonconvex quadratic programs with box constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1774170$2E33F3A5-FCDA-414A-80B8-9CFB5B897C6A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5bffccecdef9379cac95a9db3a5f197d67041787","datavalue":{"value":"1137.90010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774170$294F947D-D510-40C8-96A5-77D3C42228AC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ebd64c22a6722e04e3196f1cec7fbc8078a36cbb","datavalue":{"value":{"entity-type":"item","numeric-id":839488,"id":"Q839488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$9192AC84-0E48-4DC2-9C5E-25E0893DF72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1c26346d40b730bc09009d003fb3565eb0646e5","datavalue":{"value":{"entity-type":"item","numeric-id":163009,"id":"Q163009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$5A2A0B3A-907D-4B84-9981-DEB5DC5C42BB","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":"Q1774170$D1B6AD19-2465-4FC6-9C36-354A1DC60044","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cfdd76c6ace7e0d57b8524faf2ffe47b441fd852","datavalue":{"value":{"time":"+2005-04-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1774170$C5A9E169-96B8-4F6C-9107-3F47478726CE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a2fbc690f1acc82ab2ff24a353ac5b6e3f2e3624","datavalue":{"value":"The aim of this paper is to design an efficient branch-and-cut algorithm for solving linear programs with complementarity constraints of type  \\[  \\begin{align*}{& \\! \\max {1 \\over 2} \\sum_{i=1}^n (c_ix_i + y_i) \\cr & \\text{subject to} \\cr & y_i-\\sum_{j=1}^n q_{ij}x_j - z_i = c_i, i=\\overline{1,n} \\cr & y_i(1-x_i)=0, i=\\overline{1,n} \\cr & z_ix_i=0, i=\\overline{1,n} \\cr & x_i \\leq 1, i=\\overline{1,n} \\cr & x_i,y_i,z_i \\geq 0, i=\\overline{1,n}, \\cr}\\end{align*}  \\]  obtained by reformulating quadratic programs with box constraints of type  \\[  \\begin{align*}{& \\! \\max {1 \\over 2} x^T Q x + c^T x\\cr & \\text{subject to} \\cr & x \\in [0,1]^n,\\cr}\\end{align*}  \\]  where \\(Q=[q_{ij}]\\) is an \\(n \\times n\\) symmetric matrix. The proposed algorithm uses cutting planes defined by valid inequalities obtained by the authors in their paper [ibid. 102, No. 3 (A), 531--557 (2005; Zbl 1137.90009)]. Considering several branching strategies, the effectiveness of the algorithm is confirmed by computational experiments.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1774170$4A023051-3551-4940-AC02-982BE21F6EE3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0e725cd970719c38218b44202c303af82cf65700","datavalue":{"value":{"entity-type":"item","numeric-id":210606,"id":"Q210606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$DED07712-BEAA-4C8F-803F-D37A6609094C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774170$4A4F3A10-6296-4895-B2F6-4654A60BDB61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774170$53591741-CCB0-4AA2-8480-0861B070A944","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3491599545054385db68791047ff63268842c34c","datavalue":{"value":"2162528","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774170$A4180D87-52DF-4B36-A097-D72AEFFCE3F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e69e213b51557cc1d7697165bed961e402ad508","datavalue":{"value":"quadratic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1774170$F289ECF1-73D0-44CD-914C-457C6165BAFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e426c76ea5087dd38d7b968ac114b76a6b40fe9","datavalue":{"value":"branch-and-cut algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1774170$D6DFED6F-D0BA-4C02-8175-FFA8102B5B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6d34af1581bb061728dd8b21b1d1a37b3e03690","datavalue":{"value":"strong branching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1774170$A47111F1-557D-42C0-AF91-EFE5D67267CA","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"fbd65dd6dc2572a50934cf024dbc54d2f1bf6479","datavalue":{"value":{"entity-type":"item","numeric-id":12838,"id":"Q12838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$037E928A-5959-4029-BB8F-8218D8DF0821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"593a89f4e8d8ace6f8311a7a449f6303610259e9","datavalue":{"value":{"entity-type":"item","numeric-id":16758,"id":"Q16758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$2D5586ED-2835-4B8E-84DA-29C3AAE7B32E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4d0306a541ac4d64d413698a8167f6dce4fa4ce8","datavalue":{"value":{"entity-type":"item","numeric-id":16269,"id":"Q16269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$4394034D-EAD2-4685-A8E6-2EF1259EF21C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"a709ac7c97c67049e241e0b036253f1d955c589a","datavalue":{"value":{"entity-type":"item","numeric-id":13313,"id":"Q13313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$B43F0D1E-E12F-45A0-9AD1-07828C684FBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"7c72232bf803200903292e8d91395c8441ec640c","datavalue":{"value":{"entity-type":"item","numeric-id":17125,"id":"Q17125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$ECC5275B-CCEF-493B-A45A-4B4A51F74DAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"b42d4a8ff78b1dff5eaa3dec29c31bcecbe27dc8","datavalue":{"value":{"entity-type":"item","numeric-id":22782,"id":"Q22782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$7E43B984-D81D-429B-8C33-D86A367F0C98","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":"Q1774170$674EE471-58F3-4B51-A0AA-18D7FC44C708","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9af3d745263fdcd5ead3010e2177a3411720dea","datavalue":{"value":"https://doi.org/10.1007/s10107-004-0550-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1774170$65EF76D3-41C1-4F88-AC74-936784D30BDD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"510f403b4d1526860c84bf1606f8c29a77996721","datavalue":{"value":"W2000642309","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774170$D3F4943E-A6F2-4034-A9F4-9A4A5395CB90","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d45fa841a6a5a6e49fe7dc5b973e71a214489c6","datavalue":{"value":{"entity-type":"item","numeric-id":3896840,"id":"Q3896840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$9404AADF-03A2-4660-842B-FCBA76F4E3AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6e542ad4466feefe53a7b29acc11e0ecb26a84c","datavalue":{"value":{"entity-type":"item","numeric-id":4884044,"id":"Q4884044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$1FCBA118-C3B5-417D-A5C5-E460B747DAE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4527347f0be766413373142e027a71f126594136","datavalue":{"value":{"entity-type":"item","numeric-id":4697332,"id":"Q4697332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$57494C15-C41E-4F5D-8C53-F385EF0FAFA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e7585ecb66700fdd6a9d8fa3c7d85a631230795","datavalue":{"value":{"entity-type":"item","numeric-id":4427374,"id":"Q4427374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$19F5F66A-A292-4E70-A74E-16E9E7F744D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c954e4940f0bf231910823c671a3692745749a28","datavalue":{"value":{"entity-type":"item","numeric-id":1331882,"id":"Q1331882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$C658223D-087B-44B0-B4E7-8D8BD6EF635B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a788e7e74c5851ec3a1ae2701caa10e60cf2e6e7","datavalue":{"value":{"entity-type":"item","numeric-id":1924072,"id":"Q1924072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$662C0CF7-FD5D-4BA9-91A2-1D9198282C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53cd3dc7786f2d1b7e553469eb46d293de51f42f","datavalue":{"value":{"entity-type":"item","numeric-id":1774169,"id":"Q1774169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1774170$0F904E15-AA34-4173-B15A-1063717704CE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"edf6df8e8e9b8205905f06dfa194317f375212dc","datavalue":{"value":"10.1007/S10107-004-0550-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1774170$88E3B460-4A0E-49FF-A966-4CF42BB464F5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a449d4b7084dfc0cb1a5c1256a93988d628d9509","datavalue":{"value":{"entity-type":"item","numeric-id":1970300,"id":"Q1970300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfca2a313e3160c9aa4cc1384ccd164ab54ea4ff","datavalue":{"value":{"amount":"+0.8606410026550293","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":"Q1774170$C7418A6D-4777-4F9A-9CC2-E711E4A9A74E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fee0e1b2c505aa4119fd78ae599e7790c182961","datavalue":{"value":{"entity-type":"item","numeric-id":839489,"id":"Q839489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2970fbcdfcfedf49e8fdb3ff960beefe7c3a27a","datavalue":{"value":{"amount":"+0.8555197715759277","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":"Q1774170$FA2EAB47-C106-4856-886E-6145E85058D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7623590055b9f2901ec3ebe49f27f6d38d8c7503","datavalue":{"value":{"entity-type":"item","numeric-id":4639134,"id":"Q4639134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b88c3557f5d43d47b3c0a6a547f86a852396c04","datavalue":{"value":{"amount":"+0.8507897257804871","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":"Q1774170$C6367B15-A1D3-4891-B075-0DCA05F28BA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff54c8531c988265ee587d7d4507f8b4122a9a7c","datavalue":{"value":{"entity-type":"item","numeric-id":3431139,"id":"Q3431139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3035da9c30779e40f945b53328ab6f7a3d9e4f83","datavalue":{"value":{"amount":"+0.8355783224105835","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":"Q1774170$44CB4CB0-429F-44BA-874A-43B8C4E966EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"875278a0dd3035381634eb90722fbe862299a0e9","datavalue":{"value":{"entity-type":"item","numeric-id":820743,"id":"Q820743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2abcdbc64a3476aa20fc9e7960f83d17f8122d13","datavalue":{"value":{"amount":"+0.8233506679534912","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":"Q1774170$9E35DCCF-D754-4E16-A9D9-13A53F78466E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1774170","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1774170"}}}}}