{"corpus_id":158863359,"paper_sha":"bddf12ad8225583c9b88ed776781c7d0984097c9","doi":"10.1016/J.OMEGA.2018.11.013","arxiv_id":null,"pmid":null,"pmcid":null,"mag_id":2901122828,"dblp_id":null,"acl_id":null,"title":"Algorithmic approaches to the multiple knapsack assignment problem","year":2020,"publication_date":null,"venue":"","journal":{"name":"Omega-international Journal of Management Science","pages":"102004","volume":"90"},"journal_issn":null,"journal_title":null,"publication_types":[],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Business","Computer Science"],"reference_count":20,"citation_count":29,"influential_citation_count":2,"is_open_access":true,"arxiv_categories":null,"arxiv_license":null,"arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":"https://www.sciencedirect.com/science/article/am/pii/S030504831830149X","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/bddf12ad8225583c9b88ed776781c7d0984097c9","s2_open_access_license":"publisher-specific-oa","s2_open_access_status":"BRONZE","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"We consider a variant of the multiple knapsack problem in which some assignment-type side constraints have to be satisfied. The problem finds applications in logistics sectors related, e.g., to transportation and maritime shipping. We derive upper bounds from Lagrangian and surrogate relaxations of a mathematical model of the problem. We introduce a constructive heuristic and a metaheuristic refinement. We study the computational complexity of the proposed methods and evaluate their practical performance through extensive computational experiments on benchmarks from the literature and on new sets of randomly generated instances.","claims":[{"public_id":"cl_5a2f010bc53b6aca446c039dec1ce11d","status":"active","text":"A constructive heuristic and a metaheuristic refinement are introduced for the multiple knapsack assignment problem.","confidence":0.96,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_5a2f010bc53b6aca446c039dec1ce11d"},{"public_id":"cl_f15a2c5c27814508ba5114651f0186b8","status":"active","text":"Practical performance is evaluated through extensive computational experiments on literature benchmarks and randomly generated instances.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_f15a2c5c27814508ba5114651f0186b8"},{"public_id":"cl_764e0d75d2e2c13f422a6e852bf0736a","status":"active","text":"The computational complexity of the proposed methods is studied.","confidence":0.9,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_764e0d75d2e2c13f422a6e852bf0736a"},{"public_id":"cl_2d65a2e42485ef9e412067a1fe0a7eeb","status":"active","text":"Upper bounds are derived from Lagrangian and surrogate relaxations of a mathematical model of the multiple knapsack assignment problem.","confidence":0.97,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_2d65a2e42485ef9e412067a1fe0a7eeb"}],"concepts":[{"public_id":"co_07f0fba5d900c346396c43da0ebe0173","status":"active","name":"metaheuristic refinement","description":"An improvement phase that enhances solutions using a higher-level search strategy.","types":["algorithm"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_07f0fba5d900c346396c43da0ebe0173"},{"public_id":"co_0be16a75cf6591df0186948f35688b70","status":"active","name":"multiple knapsack assignment problem","description":"A variant of the multiple knapsack problem that includes assignment-type side constraints.","types":["optimization problem"],"aliases":["MKAP"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_0be16a75cf6591df0186948f35688b70"},{"public_id":"co_10842dab3c675c86f8f0fca17c982f44","status":"active","name":"randomly generated instances","description":"Synthetic test instances generated at random for evaluation.","types":["dataset","benchmark"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_10842dab3c675c86f8f0fca17c982f44"},{"public_id":"co_1448843517f5f6791f5d17e0ad9ff698","status":"active","name":"surrogate relaxation","description":"A relaxation method that combines multiple constraints into a single aggregated constraint.","types":["relaxation method"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1448843517f5f6791f5d17e0ad9ff698"},{"public_id":"co_32db06eee4198470b45851b532150f4d","status":"active","name":"computational experiments","description":"Experimental evaluation of the proposed methods on test instances.","types":["evaluation"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_32db06eee4198470b45851b532150f4d"},{"public_id":"co_536e1b47996111708511b2482841a96c","status":"active","name":"computational complexity","description":"The resource requirements of the proposed methods as analyzed in the paper.","types":["analysis"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_536e1b47996111708511b2482841a96c"},{"public_id":"co_8efdb36c20d065e32c550b901b34e0b9","status":"active","name":"assignment-type side constraints","description":"Additional constraints requiring items to satisfy assignment relationships in the knapsack model.","types":["constraint"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_8efdb36c20d065e32c550b901b34e0b9"},{"public_id":"co_a2bade3d24718d06b6aa51eb92fa27cc","status":"active","name":"Lagrangian relaxation","description":"An optimization relaxation technique that incorporates constraints into the objective with penalty multipliers.","types":["relaxation method"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_a2bade3d24718d06b6aa51eb92fa27cc"},{"public_id":"co_c12a6489c20b6d3632eb6b2a77455120","status":"active","name":"mathematical model","description":"A formal optimization model used to represent the multiple knapsack assignment problem.","types":["model"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c12a6489c20b6d3632eb6b2a77455120"},{"public_id":"co_db08b3d9935fa7d31ebe0f436a13db26","status":"active","name":"benchmarks from the literature","description":"Previously published benchmark instances used for performance comparison.","types":["dataset","benchmark"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_db08b3d9935fa7d31ebe0f436a13db26"},{"public_id":"co_e8ab73526316a545fcbe5694f3b415bf","status":"active","name":"logistics sectors","description":"Application domains involving planning and allocation of goods or resources.","types":["application domain"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_e8ab73526316a545fcbe5694f3b415bf"},{"public_id":"co_fe320974a99c0e48115ec453418fc30c","status":"active","name":"constructive heuristic","description":"A heuristic that builds feasible solutions directly from scratch.","types":["algorithm"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_fe320974a99c0e48115ec453418fc30c"}],"external_ids":{"DOI":"10.1016/J.OMEGA.2018.11.013","ArXiv":null,"PubMed":null,"PubMedCentral":null,"MAG":2901122828,"DBLP":null,"ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://www.sciencedirect.com/science/article/am/pii/S030504831830149X","landing_url":"https://www.semanticscholar.org/paper/bddf12ad8225583c9b88ed776781c7d0984097c9","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":"publisher-specific-oa","status":"BRONZE","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":false,"full_text_source":null,"count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":631775,"paper_uid":"f1e4155a-dbac-45ca-a4fa-a5102fbd7e8f","canonical_identity":{"paper_id":631775,"paper_uid":"f1e4155a-dbac-45ca-a4fa-a5102fbd7e8f","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/158863359"}