{"entities":{"Q1099783":{"pageid":1110535,"ns":120,"title":"Item:Q1099783","lastrevid":66129273,"modified":"2026-04-12T07:44:47Z","type":"item","id":"Q1099783","labels":{"en":{"language":"en","value":"Surrogate duality in a branch-and-bound procedure for integer programming"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4041628"}},"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":"Q1099783$6E0A4C8A-DB5B-4459-9876-F1A2A16BBBB9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a3bb7fe0e5f0bb07b44778e04cea3c0b0af9a4a8","datavalue":{"value":{"text":"Surrogate duality in a branch-and-bound procedure for integer programming","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099783$337F9A9D-D047-4336-9AB5-9A2C09304DF1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c872df6efececeb7e43ca16c0de7e3253679d128","datavalue":{"value":"0638.90072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099783$89E63384-5B65-420F-BFA3-E7B5196CA301","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c80c83eaa496034f339cffccddd46a9c63218813","datavalue":{"value":"10.1016/0377-2217(88)90176-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099783$F566A67E-ECAB-4FEF-8251-7A5F7D406CFB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"867b8edd83068c92432d2d14d17a19925598c45c","datavalue":{"value":{"entity-type":"item","numeric-id":1089256,"id":"Q1089256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$AED025ED-B3A2-465A-AC2C-9A1DF0CA919F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3281315511a08fa49f23682b2a7f1118b1cc922d","datavalue":{"value":{"entity-type":"item","numeric-id":502469,"id":"Q502469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$BBBCC420-9537-4504-A2A7-89F30F5EDDF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"18441abbbfacd00ffeec8f699d30907ba8ad216b","datavalue":{"value":{"entity-type":"item","numeric-id":204963,"id":"Q204963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$CD514342-97FC-47F5-B4DA-C56BD036105F","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":"Q1099783$463D5C99-5497-450E-BF2C-314148AE60C1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1099783$5DDD3B87-A5E1-44D4-97A2-8AF4863A3B4D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f5263379e9eeac11f5e95d224a73668fdade2b66","datavalue":{"value":"The existence of efficient techniques such as subgradient search for solving Lagrangean duals has led to some very successful applications of Lagrangean duality in solving specially structured discrete problems. While surrogate duals have been theoretically shown to provide stronger bounds, the complexity of surrogate dual multiplier search has discouraged their employment in solving integer programs. We have recently suggested a new strategy for computing surrogate dual values that allows us to directly use established Lagrangean search methods for exploring surrogate dual multipliers. This paper considers the problem of incorporating surrogate duality within a branch-and-bound procedure for solving integer programming problems. Computational experience with randomly generated multiconstraint knapsack problems is also reported.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099783$B2A87C5F-8F8F-4F07-9798-9A561B6D5A9B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099783$AD8508D2-F497-4FD0-9733-72B8D0EA2956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099783$D6E6B636-3D6F-4512-820C-95C0F6C2A9F7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7a882d10eac4de446b71f303236c31df91ab11d","datavalue":{"value":"4041628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099783$E4CCDAAC-F0A2-4D9A-9862-0C6C26E489DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20fabb422257ab6a2a8e9a1ae74240067834ad40","datavalue":{"value":"surrogate dual values","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099783$88A895A8-1C93-4DB8-A4B6-A726C6EDCAD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65d9bda2ed9ce894723c03d07a0a9fbada631f0d","datavalue":{"value":"Lagrangean search methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099783$D2267274-1AFA-495F-B4A1-8274FFBCB483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4162cdc694d833f762199ea9ed41745c2e7bc6d","datavalue":{"value":"surrogate dual multipliers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099783$C5516128-1E34-4032-AC12-DB131CB2F168","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099783$05F714B0-D015-409B-8456-AA293ECD7DCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"173104de17f6dd629f2d07b7432e31cdf5c4c38f","datavalue":{"value":"multiconstraint knapsack problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099783$E5DBDA54-EBF5-4AAD-BA03-0D3F2B72B37E","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":"Q1099783$A25FCEF1-6B54-46CF-9950-8761B1C9732D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"56b779fb485400110b01f845d1c3c1ca560f7a2a","datavalue":{"value":"https://doi.org/10.1016/0377-2217(88)90176-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099783$2A8E5413-4455-4668-A087-58294ED2BB4A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ab5f40d1ef34249e93e17f2f9815ec70a823a22c","datavalue":{"value":"W2012394102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099783$6B82E92C-0F73-4E12-A6FB-532C740EB6A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c390ff2c9cd278e7cb5f1ba1f4d79089541c7957","datavalue":{"value":{"entity-type":"item","numeric-id":5589736,"id":"Q5589736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$880F1B8B-B2F0-4751-A946-9912E3B66657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8227e8a300b94cadd33e2448f08ff3cf864d8fa0","datavalue":{"value":{"entity-type":"item","numeric-id":4133397,"id":"Q4133397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$F94E62BE-5BA1-4082-A773-3838D469E1DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"966c56938197c564dd05b370cd9d1c76d53106a3","datavalue":{"value":{"entity-type":"item","numeric-id":4158836,"id":"Q4158836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$EB9F8560-BAF5-4AD9-84C3-D3F316F9CD42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60a7800d0b1679f0be07c5a634f462cb88c03db3","datavalue":{"value":{"entity-type":"item","numeric-id":3916382,"id":"Q3916382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$6BB15576-942D-4532-A984-8591D6C4EB7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"083d97e730faf90a4132402a3f045bdbf076bc3c","datavalue":{"value":{"entity-type":"item","numeric-id":3919449,"id":"Q3919449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$A944A1E6-CE63-4F1A-9FEB-26529119ACED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2d136934a1211ce761616ab078f76e0c5f28b1b","datavalue":{"value":{"entity-type":"item","numeric-id":3688105,"id":"Q3688105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$42615D19-A19B-4D37-891F-EE15E120FB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e83ad2e630b5e849177d93c477af804fb70a3bf","datavalue":{"value":{"entity-type":"item","numeric-id":5562361,"id":"Q5562361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$F1B41E96-F613-4376-92B9-F425B694833F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f57cb52d5b46d9b84e5c5fdecf79231c1f4f0138","datavalue":{"value":{"entity-type":"item","numeric-id":4178782,"id":"Q4178782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$19851E54-3C0B-4D9E-9A0E-EA79B3AC07B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49a0bd85a49f397b03b6a1c5dd842bb85e51a86d","datavalue":{"value":{"entity-type":"item","numeric-id":5548075,"id":"Q5548075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$8DCE030E-59A2-4D2D-A96D-6FC997A451FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbb2f6832ecec3187400c340b0dfea10ceb51b7d","datavalue":{"value":{"entity-type":"item","numeric-id":4074702,"id":"Q4074702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$0F93368B-0519-47DE-BB76-010FEA90D6FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf71894ddcef4cf6408de5bd1d5b7072ba4d50c0","datavalue":{"value":{"entity-type":"item","numeric-id":5641028,"id":"Q5641028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$B00C31D2-A6DD-4873-BB06-65855C777B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ace368663b7d4f32922f2daa8d6b6627d8daad2","datavalue":{"value":{"entity-type":"item","numeric-id":4401741,"id":"Q4401741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$076AFB63-2AEA-4DE6-B9A3-68F3AC1F1657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"768f318bf6c49337dca965d936f82bf20453c0b8","datavalue":{"value":{"entity-type":"item","numeric-id":3854930,"id":"Q3854930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$4972A7B1-DEC6-43F1-B560-4E909F7FC9C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8993651072f61cc41c4ddf321c3ce7e5e717cfa","datavalue":{"value":{"entity-type":"item","numeric-id":3325464,"id":"Q3325464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$BED4E7BA-7434-4B36-A76C-D3D7FF7B53E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e9ec6746bffa5455d742c2854edf36053a58fe2","datavalue":{"value":{"entity-type":"item","numeric-id":3885516,"id":"Q3885516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$123E0E61-0FB3-43C9-BF84-970444FEB512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a72c10ba3bf4a89c4f60f3d4e8d49a60c34ccca","datavalue":{"value":{"entity-type":"item","numeric-id":3804448,"id":"Q3804448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099783$2EE2FE15-9E2A-4E92-81E1-9C1CFBC6C96C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49d4947cac01de932006d3cccd4e1038e3b26f71","datavalue":{"value":{"entity-type":"item","numeric-id":3804448,"id":"Q3804448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49f405ab9812a7c8cb29744c71e8dcf76dea0b24","datavalue":{"value":{"amount":"+0.9352000951766968","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":"Q1099783$3E386D01-E922-43E5-AA8C-AF91001537C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27e13da5191687d0d85b28867408b16f5bd19485","datavalue":{"value":{"entity-type":"item","numeric-id":3778544,"id":"Q3778544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f12b5cfdc34db52d577c813313b801bfc6723f3e","datavalue":{"value":{"amount":"+0.8654102087020874","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":"Q1099783$E4B60B95-BAC4-4153-BB70-8483473513E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"146d0846b2e4b48557c920d83b55f3d7e000c93e","datavalue":{"value":{"entity-type":"item","numeric-id":4206317,"id":"Q4206317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3f9cca9fe1abebbc2da9d84842dbef0859355e9","datavalue":{"value":{"amount":"+0.849529504776001","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":"Q1099783$0C73DB7E-ADD1-4123-89C4-542E194FB5F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03d841cc07b26d0b4d084c048cd7286f9e63ed49","datavalue":{"value":{"entity-type":"item","numeric-id":1389081,"id":"Q1389081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19890884e57e950caedc00d78e2167c754a707c8","datavalue":{"value":{"amount":"+0.8262119889259338","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":"Q1099783$EA9CC336-BCF5-45A8-9E86-D788CAA17D66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c310b0570804e2507cb5eb9da71a66eae61642f","datavalue":{"value":{"entity-type":"item","numeric-id":3725870,"id":"Q3725870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19890884e57e950caedc00d78e2167c754a707c8","datavalue":{"value":{"amount":"+0.8262119889259338","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":"Q1099783$3AEF6A91-7DF3-44A4-8B81-1D567B2A289A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Surrogate duality in a branch-and-bound procedure for integer programming","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Surrogate_duality_in_a_branch-and-bound_procedure_for_integer_programming"}}}}}