Exact Solution Algorithms for Multi-dimensional Multiple-choice Knapsack Problems

Farhad Ghassemi-Tari; Hamed Hendizadeh; Gary L. Hogg

doi:10.9734/CJAST/2018/40420

Research Article Open access CC BY 4.0

Exact Solution Algorithms for Multi-dimensional Multiple-choice Knapsack Problems

Farhad Ghassemi-Tari, Hamed Hendizadeh, Gary L. Hogg

Current Journal of Applied Science and Technology · pp. 1–21 · Published 6 Apr 2018

10.9734/CJAST/2018/40420

Abstract

We propose a first depth dual approach branch and bound (B&B) routine for solving the general form of multi-dimensional multiple-choice knapsack problems (MMKPs).We call this approach a discriminatory branch and bound method. This name is chosen due to the selection of a node for further branching based on a discriminatory criterion. Three selection mechanisms are developed and are incorporated in an algorithmic procedure to develop three algorithms. An extensive computational experiment is performed, to compare the number of nodes enumerated by the proposed algorithms against the traditional B&B. The results revealed that all the proposed algorithms lead to a considerable node enumeration reduction.

Multiple-dimensional multiple-choice knapsack Branch and bound Exact solution approach Selective branching mechanisms

Cited by 5

Simple strategies that generate bounded solutions for the multiple‐choice multi‐dimensional knapsack problem: a guide for OR practitioners

Anthony Dellinger, Yun Lu, Myung Soon Song · International Transactions in Operational Research · 2022

A Memetic Algorithm with a Novel Repair Heuristic for the Multiple-Choice Multidimensional Knapsack Problem

Jaeyoung Yang, Yong-Hyuk Kim, Yourim Yoon · Mathematics · 2022

Branch-and-Bound and Dynamic Programming Approaches for the Knapsack Problem

Evgenii Burashnikov · Operations Research Forum · 2024

Solving the 0/1 Knapsack Problem Using Metaheuristic and Neural Networks for the Virtual Machine Placement Process in Cloud Computing Environment

Mohamed Abid, Said El Kafhali, Abdellah Amzil · Mathematical Problems in Engineering · 2023

Efficient Multi-resource, Multi-unit VCG Auction

Liran Funaro, Orna Agmon Ben-Yehuda, Assaf Schuster · Lecture Notes in Computer Science · 2019

Access this article

View at publisher

Cite this article

Farhad Ghassemi-Tari, Hamed Hendizadeh, Gary L. Hogg (2018). Exact Solution Algorithms for Multi-dimensional Multiple-choice Knapsack Problems. Current Journal of Applied Science and Technology , 1–21. https://doi.org/10.9734/CJAST/2018/40420

Affiliations

Farhad Ghassemi-Tari — Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran.
Hamed Hendizadeh — Department of Mechanical and Manufacturing Engineering, Faculty of Engineering, University of Manitoba, Winnipeg, Manitoba, Canada.
Gary L. Hogg — Department of Industrial Engineering, Arizona State University, USA.

Metrics

7
Views: 0
Downloads: 5
Citations: 0
Outbound

Full metrics

Article metrics

Real usage data collected on this platform.

7

Page views

0

PDF downloads

0

Outbound clicks

5

Citations

Views over time

Views by country

Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".

Traffic sources

Referring site, by host.

Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.