{"entities":{"Q4946717":{"pageid":6976299,"ns":120,"title":"Item:Q4946717","lastrevid":108570614,"modified":"2026-11-07T00:49:41Z","type":"item","id":"Q4946717","labels":{"en":{"language":"en","value":"A variable depth search algorithm with branching search for the generalized assignment problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1422772"}},"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":"Q4946717$FAAF16CC-98FD-4FA9-8BF8-C5DE04F729D6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef9f68ab9c5946a0acad487406cb55551a0c995b","datavalue":{"value":{"text":"A variable depth search algorithm with branching search for the generalized assignment problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4946717$CAE739D9-0447-490C-8DF4-83E73FDFA7CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e0eac340fca829b77da6732222aba911d2c88d7e","datavalue":{"value":"0947.90070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946717$767BEC24-E6BC-4E9D-9AA7-8F9EAFEA22DC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"41a7d74fe288fca2ac5064effbef4d0a25e9a62a","datavalue":{"value":"10.1080/10556789808805722","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946717$1E18E8A2-E977-42C6-8AB3-67DFC28C02D8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5ea748ba8002b10a36a7fe3649476814953fa14","datavalue":{"value":{"entity-type":"item","numeric-id":402944,"id":"Q402944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4946717$447C68DD-8C0C-41D4-9109-A56C7E91D067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"746535ddb96ae77c4a55cf2874e59b3bf4f00d57","datavalue":{"value":{"entity-type":"item","numeric-id":171928,"id":"Q171928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4946717$824C1334-C13E-4FF5-A805-74591E23ED44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"694f8e5b23289ba4bcc1a45a25bce07de03f3270","datavalue":{"value":{"entity-type":"item","numeric-id":535011,"id":"Q535011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4946717$44DAA304-19AB-4AF4-B266-62D26032B882","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e57d2131b7ebb7a4275a76b56508e22fc13f4990","datavalue":{"value":{"time":"+2000-10-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":"Q4946717$C2197F44-B459-4FBA-AAFE-BA08F6770E07","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946717$3CF93068-2678-4FE1-8A0D-F86212A2B99F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"33ce2902e949183aaad044c64afe8db5cdfcba41","datavalue":{"value":"1422772","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946717$CEE99979-38BB-4101-857C-F8456D27D4FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9374ed2d3172dd37d5ebf823ec4347cfa78fc4b7","datavalue":{"value":"assignment problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4946717$563AD09E-1408-4B0C-8514-53E58542B29C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q4946717$D585C8FA-ED70-4C8B-9ACB-5400B3423BAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea1ff5a5e657abc0a392084b74b3342d23f2f4c9","datavalue":{"value":"local search","type":"string"},"datatype":"string"},"type":"statement","id":"Q4946717$701D2840-D6A1-4D9E-8DC1-BA9E7B1ADA84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ada89b5aac2ab12c2d97d398ab2e767725f3ba8","datavalue":{"value":"variable depth search procedure","type":"string"},"datatype":"string"},"type":"statement","id":"Q4946717$46BCE2EF-24BD-45CC-A75E-3AF8DF2AA9E9","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":"Q4946717$B5B5F78C-35D1-4731-BFD7-2B23E2C53926","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b72908a90aae940d213a8eb7993fa2e1a8c901c3","datavalue":{"value":"https://doi.org/10.1080/10556789808805722","type":"string"},"datatype":"url"},"type":"statement","id":"Q4946717$95BC6C8D-3E52-48C6-9023-D56512F49C7F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"72d14c3da3138374bbf504f6cff4153ed2302bbc","datavalue":{"value":"W2032982020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4946717$7E0018C5-A7A7-4CC1-AA63-B6191EC7F454","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ece56173b7186930c6a2471566566ba3cd24f908","datavalue":{"value":{"entity-type":"item","numeric-id":6585816,"id":"Q6585816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4946717$0FC48BD7-7C5F-4CD7-A00E-33A0BAF3DBDA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4872e95827d4c3c97832baa43c0b06d9422b0916","datavalue":{"value":{"entity-type":"item","numeric-id":4495204,"id":"Q4495204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33dec88fc9fa8bf4754dbcfb5559a9036607ff5e","datavalue":{"value":{"amount":"+0.8926134705543518","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":"Q4946717$F59D3EBE-A73A-44F3-809C-5DF610C57251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21eed8f4c4fe94f249c91e8fb9bb43312b56b658","datavalue":{"value":{"entity-type":"item","numeric-id":2752253,"id":"Q2752253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3011955c0856ae53738ca5ce17ac618b867be3ca","datavalue":{"value":{"amount":"+0.8284638524055481","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":"Q4946717$2E6636A9-0A8B-41AD-94BA-2B66EBA0CFC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d484ea077865a9bc77c6b0c469d87e317e0c84b","datavalue":{"value":{"entity-type":"item","numeric-id":1339150,"id":"Q1339150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d705a1d093b8eff6573b6a1e7a86e71ab3bea46","datavalue":{"value":{"amount":"+0.8179804086685181","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":"Q4946717$2AF224E5-DEDB-4503-BC33-879FF21D54A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26a4a1fc4d6257972ba46e86a9093c353d794998","datavalue":{"value":{"entity-type":"item","numeric-id":3604030,"id":"Q3604030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c83ed6fefc678de05b8889a6d15df2b6de3e920","datavalue":{"value":{"amount":"+0.8062049746513367","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":"Q4946717$8E199901-2244-441F-AB8E-C4C8CAED0618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7e067823028e1ff75d43fab9cbb82f626b72a4f","datavalue":{"value":{"entity-type":"item","numeric-id":4834242,"id":"Q4834242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3022162185b291e0a5af43b626aebaf34ee04d34","datavalue":{"value":{"amount":"+0.7977176308631897","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":"Q4946717$310B8D2F-4B5B-450A-B6F2-0033E965E10B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ca635224686268066ee1dad7d895ee2af96e3197","datavalue":{"value":"A heuristic procedure for an assignment problem with restrictions is proposed. A base of the algorithm is a variable depth search (VDS) is described by \\textit{B. W. Kernighan} and \\textit{S. Lin} [Bell Syst. Tech. J. 49, 291-307 (1970; Zbl 0333.05001)]; it is a specification of a branch-and-bound approach. VDS performs locally optimal search in a neigborhood of a current solution. To expedite matters, both feasible and infeasible solutions are accepted to a neigborhood. The authors adjust VDS method to assignment problem with restrictions on resources of agents. A job selected for an agent is not allowed to violate given bound on resource, for example, time to the place of work. The authors define two kinds of neighborhoods of a current assignment, the first contains all solutions (feasible and infeasible) differ from the assignment by only one assigned job, the second contains permutations of any two jobs of the assignment. To simplify the procedure, all restrictions are carried to objective function as penalties. It is notorious that local search does not provide global extremum; therefore to improve procedure authors extend search area to nieghborhoods of several successive points. This trick initiates some negative effects, for example, cycling of solutions. The authors have overcome them and describe algorithms of branching and searching in details. Parameters of the algorithms are appointed to provide on the one hand polynomial time (linear by the size of initial matrix of the problem), and on the other hand closeness to optimal solution. Comparison with different modifications of VDS, tabu search, and random local search demonstrates advantage of the proposed algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4946717$C663F1DA-853D-483E-8187-D5A4BE8B715E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A variable depth search algorithm with branching search for the generalized assignment problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_variable_depth_search_algorithm_with_branching_search_for_the_generalized_assignment_problem"}}}}}