{"entities":{"Q2640438":{"pageid":2651181,"ns":120,"title":"Item:Q2640438","lastrevid":49463467,"modified":"2026-01-07T05:08:01Z","type":"item","id":"Q2640438","labels":{"en":{"language":"en","value":"Global optimization of a quadratic function subject to a bounded mixed integer constraint set"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4187453"}},"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":"Q2640438$02AFC178-36D6-483D-BF01-D56D60F12653","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa2101b02719161b8dd54145df732ebcc76c4295","datavalue":{"value":{"text":"Global optimization of a quadratic function subject to a bounded mixed integer constraint set","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2640438$63199D16-78FB-4423-B85E-32EC04E18C1E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aca1f8d81e3785ed4286c04b0371e246c9508c06","datavalue":{"value":"0719.90050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640438$1A0A09C3-9E07-45F8-8098-7827A82B403A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"828bc313f0596e19581b8958713353adcd01c945","datavalue":{"value":"10.1007/BF02283693","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640438$78303673-4D3A-4C89-A63A-02AF71CBE3BF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c134d57277306b4c398c21aa6c6eeea91d78f6bc","datavalue":{"value":{"entity-type":"item","numeric-id":1068730,"id":"Q1068730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$BF825D04-9B99-487E-AB0F-F80D3FCC3934","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa1021f0d1926e7d99f3ecfee0317ee4193d1d36","datavalue":{"value":{"entity-type":"item","numeric-id":222919,"id":"Q222919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$90641EEC-38F6-4CD1-A448-008DA7959858","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8f57d1123ebbbd10d621b3552a672e7729202712","datavalue":{"value":{"entity-type":"item","numeric-id":59875,"id":"Q59875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$68EA5BD1-5B85-4E6A-8467-9984E9872FB6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q2640438$83B0D77E-46E6-4270-BC9F-91015B6E93F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d3f51b20552f128da2d30bcc60428bcf079c4e8e","datavalue":{"value":"This paper deals with the NP-hard problem of finding a global solution to a mixed integer nonconvex quadratic program. A branch and bound algorithm is presented which requires the solution of linear programming subproblems at each node. The method is based on underestimation of the objective function and relaxation of the integer restriction. Two piecewise affine underestimating functions are developed for the function \\(x^ tQx+c^ tx\\) over a rectangular set \\(\\ell \\leq x\\leq L\\). Noting that \\(x^ ty=x^ tQx+c^ tx\\) for \\(y=Qx+c\\), bounds \\(m\\leq y\\leq M\\) are given by \\(m_ i=\\min \\{Q_ ix+c_ i:\\ell \\leq x\\leq L\\}\\) and \\(M_ i=\\max \\{Q_ ix+c_ i:\\ell \\leq x\\leq L\\}\\), where \\(Q_ i\\) denotes the ith row of Q. Taking the convex envelope of \\(x^ ty\\) over \\(\\ell \\leq x\\leq L\\), \\(m\\leq y\\leq M\\), and projecting gives an affine underestimate for \\(x^ tQx+c^ tx\\). Alternatively, substituting \\(y_ i=Q_ ix+c_ i\\) into the expression for the convex envelope yields a piecewise affine and convex underestimate. For the pure 0-1 integer case, the latter underestimate reduces to a reformulation of a quadratic binary program due to \\textit{F. Glover} [Management Sci. 22 (1975), 455-460 (1976; Zbl 0318.90044)]. Overestimating functions based on concave envelopes are also derived. These are useful in establishing error bounds on the approximations and thereby ensuring finite convergence for a given tolerance.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640438$22397BCC-524A-4955-9F61-2DE8D5587101","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bf44f3ad3a2f88c9b2a45e4395030d611f0589bf","datavalue":{"value":"90C11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640438$7FE9BE34-F4D1-47F3-9EE8-788C8E98E698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640438$CB4DD937-0FF5-4D76-B458-35A8E9318C42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ed10a41ec587cb61dc683f25ef4b3e827c7fee2f","datavalue":{"value":"90C26","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640438$65E1517B-C65B-49A6-8903-FB1F4BE4CF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4d4b880941bb65ec306ce9d3141ff7e82566f56","datavalue":{"value":"90C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640438$40DDCBBC-4EF2-4E27-AFF7-F9CDF1E90C17","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"66678b3c9392fc869725e95c68bb4596a5c64387","datavalue":{"value":"4187453","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640438$5A03D277-AF62-4933-B543-B695341D17CF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640438$58F89982-6E1D-438F-A4B9-B343F52D50DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bee0d0540e3b00c99857f93cb144426307304327","datavalue":{"value":"global solution","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640438$10B05C0F-6819-4BAC-BF0A-C3BAC1A91D3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb178e37221020f57785e4825ce407bc045caf5a","datavalue":{"value":"mixed integer nonconvex quadratic program","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640438$96E26C3F-5B36-4572-8A14-0B10E649C1D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640438$99FE0681-26F8-47B4-B0F2-BBBD59FBE44A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0af6d01e3382ec38296633ca960bb22b18f6469","datavalue":{"value":"underestimation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640438$E26F46E6-FD04-439D-851B-00001548B4C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9675bb37dbeeee484cb314a4abd71e5ae4600c0","datavalue":{"value":"relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640438$4EBF58E1-4C35-4FF7-81E1-0F22EF357781","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":"Q2640438$D79C3E2B-BDBC-4774-8E2C-64A6E053BB86","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bc36cde5a0d525109dbbb2b17760ccdae81f612","datavalue":{"value":{"entity-type":"item","numeric-id":3762072,"id":"Q3762072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$82B965D8-4404-44CD-AF41-AB07767DA84D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"681c179b0bd0e34911d4a10c5ca317bb0f4316d5","datavalue":{"value":{"entity-type":"item","numeric-id":918873,"id":"Q918873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$AC52976E-4293-4A3F-8E3B-85843B678D29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58d42b0da8e8b6439dce8b581304ec66d4dc34e1","datavalue":{"value":{"entity-type":"item","numeric-id":3671770,"id":"Q3671770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$16A21241-3B94-4087-B4F9-9EE7CED00E55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa17b62d0636820ab1431b9b3e25f3205f9b7f47","datavalue":{"value":{"entity-type":"item","numeric-id":3808112,"id":"Q3808112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$921E26CE-FC75-425B-9B87-B91F540CD477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86f1036f52c9d084642933ae13a25638be140f18","datavalue":{"value":{"entity-type":"item","numeric-id":3039039,"id":"Q3039039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$C53C64F8-9CAC-4BB7-9DF3-F212C82DEDBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bc52c634408cea781c9a89772dd9e142cfaba78","datavalue":{"value":{"entity-type":"item","numeric-id":757431,"id":"Q757431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$1026179C-5567-41F5-B3BE-9C853541D97E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e3c092fff175044584821adddc628ab2c7d1dac","datavalue":{"value":{"entity-type":"item","numeric-id":2641219,"id":"Q2641219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$B60B5CC7-1C1F-46A7-A464-4D7593F024B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbab0346485edb37abe10d23c4aef3f79f4f4648","datavalue":{"value":{"entity-type":"item","numeric-id":4081009,"id":"Q4081009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$9061BA22-6C00-4907-AF62-D361BB9F3F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae43d2d5688d592d9a32149264bddece64f2be70","datavalue":{"value":{"entity-type":"item","numeric-id":1067978,"id":"Q1067978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$8E422A4C-7A07-4406-8108-D4C15B028AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaa2269bb9b59c0b6a3702790991518d9aab8883","datavalue":{"value":{"entity-type":"item","numeric-id":4197634,"id":"Q4197634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$2F2C7E4C-AA86-40FF-8D2F-AFFE237E70BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9952d77ba92ecf9c3436c114b5fc3da39ffd6fd1","datavalue":{"value":{"entity-type":"item","numeric-id":3720300,"id":"Q3720300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$FE92E283-E6E4-413A-8363-65A78DBA76D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1e8c199d0a3738b5df7039fa423628b9c9f24f","datavalue":{"value":{"entity-type":"item","numeric-id":4040221,"id":"Q4040221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$34C580A9-F079-4727-81DA-D988923AD3B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d9278c22c170fbf7ab2ef157aff9ab68ae2346b","datavalue":{"value":{"entity-type":"item","numeric-id":1099780,"id":"Q1099780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640438$891C0D9B-FD57-414F-B76A-DA7F6F94599C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"da3512cabb2b3fe9ac829e903d45b137848dbd3e","datavalue":{"value":"https://doi.org/10.1007/bf02283693","type":"string"},"datatype":"url"},"type":"statement","id":"Q2640438$49BDD0FB-B534-41D7-BE85-B358928C617F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"64aa87678e42e798c5209892898eae2bfd9ca8e2","datavalue":{"value":"W2052220497","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640438$010B05ED-E8F7-40D2-A201-5488F8AC61F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8822c3f5b257c831f3375858ff0f49d5ca5e51f6","datavalue":{"value":{"entity-type":"item","numeric-id":1384092,"id":"Q1384092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbcf5ebbfa4208f3a17f0cd82a4bd1f34bc97869","datavalue":{"value":{"amount":"+0.8226097226142883","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":"Q2640438$5F41CE40-6F14-415F-8D8D-7669257A77BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d668ae301344470fb941883363f13f8b25787867","datavalue":{"value":{"entity-type":"item","numeric-id":3680608,"id":"Q3680608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d959bf640362cd1e83bbce0884b378da59df558","datavalue":{"value":{"amount":"+0.8052400946617126","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":"Q2640438$97AE77CD-27B8-46A6-8686-2E9DC0847541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11c6ebdc5e3343eec9e72ca2f7f520d2be931f0c","datavalue":{"value":{"entity-type":"item","numeric-id":2713937,"id":"Q2713937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60943d1e5fbd69ab375fc9a92d690e314e8a1a63","datavalue":{"value":{"amount":"+0.8040928840637207","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":"Q2640438$56F409A1-6E09-4774-99DE-0BCFF55145BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e1c89b501864528ab1118dc9a2da434571207fa","datavalue":{"value":{"entity-type":"item","numeric-id":3635703,"id":"Q3635703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cce64614960aace2de351c1078bc4e526ee770ea","datavalue":{"value":{"amount":"+0.8032552599906921","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":"Q2640438$4BE8F254-3E67-46E6-9E63-E702A34BE6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cf584e1b15d0e1d55a256bb5a27c4525fa89c96","datavalue":{"value":{"entity-type":"item","numeric-id":1575066,"id":"Q1575066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13c291aeddedf7f5593b29271cd78b1c392072a3","datavalue":{"value":{"amount":"+0.8021568655967712","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":"Q2640438$44290F6E-1F2C-4B81-AB63-5D4CAEADB624","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2640438","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2640438"}}}}}