{"entities":{"Q2204628":{"pageid":2215371,"ns":120,"title":"Item:Q2204628","lastrevid":53846084,"modified":"2026-01-25T19:55:56Z","type":"item","id":"Q2204628","labels":{"en":{"language":"en","value":"A two-phase heuristic for set covering"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7261727"}},"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":"Q2204628$D8019F95-FE58-4A01-A97F-D0A6B5C04495","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2536fbd4597447ed47e9968bec9e9d6dc77a9664","datavalue":{"value":{"text":"A two-phase heuristic for set covering","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2204628$EC19AC47-7587-4EEB-A55C-9A7B04831E75","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"129ea68db4e6bd693334fdc4450d4fd539f6c8ed","datavalue":{"value":"1452.90221","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2204628$95857F7E-66F7-4CC7-97DB-F00D21DC3FB1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"072e44e422bc0fd42b19ca0b2ceec6031c8ba119","datavalue":{"value":"10.1504/IJMOR.2018.092962","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2204628$F3BEFDF3-70F8-4B96-804F-E022774E6791","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8c072500dd24fdd8461d405f45f1e2776736e829","datavalue":{"value":{"entity-type":"item","numeric-id":975426,"id":"Q975426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2204628$3377EA40-25B8-4CBE-B14F-307BD64FDE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b51c0a8ab53109811fd7d426c3e2882d67545702","datavalue":{"value":{"entity-type":"item","numeric-id":2204627,"id":"Q2204627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2204628$35D94BDF-6E0A-4591-B162-859C43157DB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0fa9ceec9f354f5f8c0f75a4c29b25c79227b93","datavalue":{"value":{"entity-type":"item","numeric-id":1721230,"id":"Q1721230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2204628$39A2EAC8-3A94-44E0-B016-B170EAC3F404","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"08904a7410b5f731fa63153720439160d216b374","datavalue":{"value":{"entity-type":"item","numeric-id":548461,"id":"Q548461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2204628$D1F155E3-4822-401B-9942-D37E8E99BC48","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"74f969d0fb9bfcdfa4b8edd3d369bcf872715087","datavalue":{"value":{"time":"+2020-10-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2204628$F7240425-4D42-4153-A878-50CFE3EB042F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"af171eee86e8fc6b6d2ec56c5db89474af6c987c","datavalue":{"value":"Summary: The set covering problem (SCP) is a well-known computationally intractable problem. We suggest here a two-phase heuristic to solve it. The first phase reduces substantially the size of the given SCP by removing some variables; the second phase applies a simple Lagrangian heuristic applied to the reduced problem. Construction and improvement heuristics are embedded in the Lagrangian solution approach. The construction heuristic provides good covers by solving small SCPs. The improvement heuristic inserts these covers into larger ones from which better covers are extracted, again by solving different but also small SCPs. The novelty lies in the reduction of the problem size by an effective variable-fixing heuristic, which, in practice, eliminates up to 95\\% of the variables of the problem without sacrificing the solution quality. Extensive computational and comparative results are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2204628$38FF2D84-8A07-449B-BA7D-384B1BAC6E93","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2204628$684B8C2F-52A9-4FD4-909C-4C0AED5AA244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d42ae7884b9335550c4d21f090798ce9c56a9bf","datavalue":{"value":"90C59","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2204628$E804D9FC-1D5C-4AAE-84E8-3827B196A09B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dbd7164e0456bf014c073e9861a9ae74b9dddaa7","datavalue":{"value":"7261727","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2204628$CBF72331-B276-4CE4-B05B-260219C189DC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b48dcd8674ea4b480794d89ebf926d674813248","datavalue":{"value":"set covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q2204628$3575F770-E6DB-4DBA-8A64-0B4461644483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7275c1296aa9f01bd7def2fef018783f65750fae","datavalue":{"value":"variable-fixing heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2204628$0A8C908F-139B-406D-AFA8-A8C7316049F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"740455c639c40f3068aec06ff93195d6d756b18b","datavalue":{"value":"greedy heuristic with regret","type":"string"},"datatype":"string"},"type":"statement","id":"Q2204628$76D86A82-49A7-4922-9065-EEF63DD4F1CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3efa615ce4ced679129d99ecd77e0f6a889087bd","datavalue":{"value":"Lagrangian heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2204628$977C2A35-138E-4512-9946-D5622BA95EE1","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":"Q2204628$64607835-1C32-4DAA-8C87-BE8DCC49D023","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"6a13b68ef6af813d873d2858c8be7465a9ea0aea","datavalue":{"value":"Q129581964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2204628$81656EF4-E568-47AE-955C-311EAB02B72B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37d7767a81c9ceed171b4e306dbea53d3f2e51fd","datavalue":{"value":{"entity-type":"item","numeric-id":4645914,"id":"Q4645914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a08a25cb570a36072f89187250eb9ecd23031f4c","datavalue":{"value":{"amount":"+0.8945471048355103","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":"Q2204628$37253526-D4EE-4196-AE24-49A98D78F7A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54d6e4d95be29577a100820b3e61d2b79f1688b4","datavalue":{"value":{"entity-type":"item","numeric-id":4950819,"id":"Q4950819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b7fa7010f99ab8fafb5b9cec70f2395384f8dc4","datavalue":{"value":{"amount":"+0.8586786389350891","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":"Q2204628$9FDDCDDE-B713-484E-9DC9-64913CD7BE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d460777987c6702cecfae5f24acadbf45c1fc27","datavalue":{"value":{"entity-type":"item","numeric-id":5385039,"id":"Q5385039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97d1a682d277f302f7a39fc9461addb1d01a2c02","datavalue":{"value":{"amount":"+0.8454556465148926","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":"Q2204628$1BFF3103-2CA8-4D35-918A-72672A01CF77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aeab0137b5652883e22c4d4c4c22cbf403052e2b","datavalue":{"value":{"entity-type":"item","numeric-id":4735035,"id":"Q4735035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0f6d199ff67651bd11cff0c460b572f0db3e151","datavalue":{"value":{"amount":"+0.8428575396537781","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":"Q2204628$652E074A-36B6-44DE-8F1C-1C543357A82D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c844e368a55aee834322e37689461793654eb6fe","datavalue":{"value":{"entity-type":"item","numeric-id":1278602,"id":"Q1278602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"190956c820da5e46882517d5fd4e1a5075883b4b","datavalue":{"value":{"amount":"+0.8411598801612854","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":"Q2204628$A91EBD15-2D96-428B-81B2-B6FB4BB6A363","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2204628","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2204628"}}}}}