{"entities":{"Q1109683":{"pageid":1120432,"ns":120,"title":"Item:Q1109683","lastrevid":66451071,"modified":"2026-04-12T10:09:54Z","type":"item","id":"Q1109683","labels":{"en":{"language":"en","value":"A new dominance procedure for combinatorial optimization problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070642"}},"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":"Q1109683$1197DB9B-B5E7-46B6-A023-8C3AE7897794","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ddc457e75ee5a4a018c67708b39f44df4a5d83e3","datavalue":{"value":{"text":"A new dominance procedure for combinatorial optimization problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109683$6C468063-EA45-47B1-A98B-5F6AFEDBB37F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3d16dcd5eb0004ab426e53dc6500f8d7801df74f","datavalue":{"value":"0655.90064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109683$AC2BCE00-E8DF-47D1-9979-E4D1771702C5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a379383e387cb68060553ee4cd1246ed489ab30","datavalue":{"value":"10.1016/0167-6377(88)90025-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109683$8F744A3E-9C8D-42A8-A73B-EA44CC5C9B45","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6848f64fee6b23a31800e804f2d7bce7c1792806","datavalue":{"value":{"entity-type":"item","numeric-id":181213,"id":"Q181213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$B0C837B8-7F6A-4EA1-88F5-10129219DB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4f4e50ab5ff3e3fa6e97103b12136833b436f53","datavalue":{"value":{"entity-type":"item","numeric-id":181212,"id":"Q181212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$C680C9CC-EDD7-40AB-ABF7-2755264669C1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$E19271BE-98C9-4650-A820-1B388B100098","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":"Q1109683$A1F0F8F6-6820-4752-ADEA-C8188DCD52A1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"94c985ae65fbd6a4d92941513e7a1f31c4930ca3","datavalue":{"value":"The effectiveness of branch and bound algorithms can be improved by dominance criteria which allow fathomings of large solution subsets. The authors consider a branch and bound algorithm for solving the combinatorial optimization problem (P): \\(v(P)=\\min c\\) Tx subject to \\(x\\in F(P)\\), and the corresponding branch-decision tree. For each feasible node k of the tree, let \\(J^{(k)}\\) be the set containing the indices of the fixed variables \\(x_ j=x_ j^{(k)}\\), any feasible solution \\(\\tilde x\\in F(P)\\) with the partial solution \\(\\tilde x_ j=x_ j^{(k)}\\) for \\(j\\in J^{(k)}\\) defines a completion for node k given by values \\(\\tilde x_ j\\) for \\(j\\not\\in J^{(k)}\\). A node \\(\\beta\\) dominates a node \\(\\alpha\\) iff:    (1) \\(J^{(\\beta)}\\) \\(=\\) \\(J^{(\\alpha)}\\)    (2) \\(\\sum_{j\\in J^{(\\beta)}}c_ jx_ j^{(\\beta)}\\leq\\) \\(\\sum_{j\\in J^{(\\alpha)}}c_ jx_ j^{(\\alpha)}\\)    (3) any completion for node \\(\\alpha\\) is also a completion for node \\(\\beta\\).    In order to check dominance, the authors introduce the neighborhood set \\(N^{(\\alpha)}\\) containing all the nodes \\(\\beta\\) satisfying conditions (1) and (3) and they consider the auxiliary problem:  \\[  v\\quad =\\quad \\min \\quad \\sum_{j\\in J^{(\\alpha)}}c_ jx_ j  \\]  where \\(\\{x_ j:\\) \\(j\\in J^{(\\alpha)}\\}\\) defines a partial solution associated with a node in \\(N^{(\\alpha)}.\\)    The auxiliary problems can be solved exactly or by heuristics. The authors consider the multiple knapsack problem and give several heuristics which are used in the algorithm by \\textit{S. Martello} and the second author [ACM Trans. Math. Software 11, 135-140 (1985; Zbl 0562.90061)]. The computational results show that the dominance procedures reduce both the number of nodes and the computing time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109683$874C5B06-B73B-4C15-9242-2284A37179FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109683$5B6F5A92-877A-4BF6-8E66-763D3D47ED18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109683$24EFE95C-2284-4A9D-B111-FD37C475C7AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109683$F46F477D-E65B-4171-B9F1-EA7049729EB2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"01b6f0b11ce0fec6486067e4084b8d03982691f5","datavalue":{"value":"4070642","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109683$C7B98FA3-3E49-4298-9360-8C267CC3927C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd0e2c0b577ccfe5cefb4e1ba544da7f0e8a2030","datavalue":{"value":"dominance criteria","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109683$7CC58327-013E-42E6-B7B0-726461568805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109683$47E140B3-C627-4648-84CB-EEACC40438D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39c4805435a99761d1c4ec6cd11243a1bc570c29","datavalue":{"value":"multiple knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109683$167A86B3-4283-4BAF-99B5-9971C773C8E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ffcc3545bd7b0f94969c35c641231860a38c51","datavalue":{"value":"heuristics","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109683$F2E2A6E6-AB07-4964-A6F8-A233CDC3DB10","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f6ea406ef36e1810d468b672efc85eebb5f97473","datavalue":{"value":{"entity-type":"item","numeric-id":566922,"id":"Q566922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$53FE77E8-8269-41EF-A0B5-416E1E9AF82D","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"dd06c42f1b8bc571491a59f2bdb51c2d87ab2a1a","datavalue":{"value":{"entity-type":"item","numeric-id":35542,"id":"Q35542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$3143C08B-AD19-411E-B7ED-04B7DF080ED9","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":"Q1109683$58F4DD77-3F72-4114-A440-E87020D8FF04","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb837b0b1faff8d315939daa27ddca6d4c9d274a","datavalue":{"value":"https://doi.org/10.1016/0167-6377(88)90025-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109683$E6662325-2645-45A5-888E-FB68902290E8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b63e8b062178807fad546ae8d2852e9f66509891","datavalue":{"value":"W2017548615","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109683$E44ACCE2-2DC3-4558-948A-84369F293CB2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aec018040917e41f973d88f33f07a03c3798a890","datavalue":{"value":{"entity-type":"item","numeric-id":3826354,"id":"Q3826354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$5FEF6B4C-3C82-44DE-A678-6AE8DD233313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e47e6386afaa17190943becc239760ab7ca2a65b","datavalue":{"value":{"entity-type":"item","numeric-id":3675904,"id":"Q3675904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$390E3B0C-E010-4F1D-B52B-AFEAE681E22A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d3ad6fbc9d544f63cef170de23284269dffa20","datavalue":{"value":{"entity-type":"item","numeric-id":3751378,"id":"Q3751378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$EDFE4D02-54F1-4E7D-B8EC-C60E32100A37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109683$376A9200-C561-4394-9C8A-39C984AAD6F8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e5c3dd3b55e6653d7e5225f329f8c8b2f2baf0e","datavalue":{"value":{"entity-type":"item","numeric-id":3374248,"id":"Q3374248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf9a603b24910bc101e6443835b46cf6d10cb2da","datavalue":{"value":{"amount":"+0.92533886","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":"Q1109683$AE669CB9-F86A-4433-939D-166B1439318C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9997cef320f4c2d3b31a882b6b8b26ba5af49ae","datavalue":{"value":{"entity-type":"item","numeric-id":421551,"id":"Q421551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18cb5095341999ad502398a2503cb16d0061c99e","datavalue":{"value":{"amount":"+0.9234988","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":"Q1109683$1C2F2C2E-8A22-4066-A5BA-E6D9C7D707D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe2a8acfb20010a4820a0543eced2110b9566419","datavalue":{"value":{"entity-type":"item","numeric-id":2315578,"id":"Q2315578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb7f35af6c3d9afd6f00f7a57f9a833de343db46","datavalue":{"value":{"amount":"+0.9195555","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":"Q1109683$00A7E649-3FDC-4222-8BEF-C6ACD35CFE79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce76e1661f6fc997b763e8fcb3782948b13850d0","datavalue":{"value":{"entity-type":"item","numeric-id":1406045,"id":"Q1406045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee11dabf9c80d3e4a80a01a7626479271168ecba","datavalue":{"value":{"amount":"+0.91344863","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":"Q1109683$2F82331C-9054-41E2-BDA3-81547F241F37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53c0c36c899253dba5dd62f60dd07975d961d755","datavalue":{"value":{"entity-type":"item","numeric-id":2923563,"id":"Q2923563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f4d7800020aad11a10cfda5431542568f95dc18","datavalue":{"value":{"amount":"+0.89511096","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":"Q1109683$FE888376-064D-44BA-A502-00A9DFA5993D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0d02d2400b25075b515e7617ecae9f9a6e43eaf","datavalue":{"value":{"entity-type":"item","numeric-id":3576755,"id":"Q3576755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6a56478d781f666970728a828ae96feb7f6ab63","datavalue":{"value":{"amount":"+0.8934503","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":"Q1109683$168EA4D8-DD9B-4C8E-90BF-94C42A196785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d567e78e156abac8d88993a8bbd5a8df92b9016","datavalue":{"value":{"entity-type":"item","numeric-id":4679680,"id":"Q4679680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54fd387d32557a7d9c9add60ffe3f6a0a939e054","datavalue":{"value":{"amount":"+0.8923429","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":"Q1109683$710D30D3-6043-4914-A3DA-C6E64540F274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be475d41ddfed5b19a290eb8e6804cec83e2e1ad","datavalue":{"value":{"entity-type":"item","numeric-id":5398169,"id":"Q5398169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e8740355573c591807f960653bf5312c62c8911","datavalue":{"value":{"amount":"+0.8896755","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":"Q1109683$8CB0FB95-E86A-459C-BE76-676F231087DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0c0c4cd2c8e50602017ab446b723263356276df","datavalue":{"value":{"entity-type":"item","numeric-id":1001381,"id":"Q1001381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1414f9dbc094beb2894912df826147eeba0361ba","datavalue":{"value":{"amount":"+0.8836054","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":"Q1109683$F6EE151D-D4B2-4039-A013-816BBC8F2F1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c8668fcb8a929284ac641da37d5002fd3dd6f2d","datavalue":{"value":{"entity-type":"item","numeric-id":3167608,"id":"Q3167608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ab14ec6dadf822af9ad4bae5e2df2886649ddae","datavalue":{"value":{"amount":"+0.882738","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":"Q1109683$B048C486-2502-43D9-A780-E0CF3F33C2F8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A new dominance procedure for combinatorial optimization problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_new_dominance_procedure_for_combinatorial_optimization_problems"}}}}}