International Journal of Circuits, Systems and Signal Processing

   
E-ISSN: 1998-4464
Volume 15, 2021

Notice: As of 2014 and for the forthcoming years, the publication frequency/periodicity of NAUN Journals is adapted to the 'continuously updated' model. What this means is that instead of being separated into issues, new papers will be added on a continuous basis, allowing a more regular flow and shorter publication times. The papers will appear in reverse order, therefore the most recent one will be on top.

Main Page

Submit a paper | Submission terms | Paper format

Volume 15, 2021

Title of the Paper: A Simple and Efficient Technique to Generate Bounded Solutions for the Multidimensional Knapsack Problem: a Guide for OR Practitioners

Authors: Yun Lu, Bryan McNally, Emre Shively-Ertas, Francis J. Vasko

Pages: 1650-1656 

DOI: 10.46300/9106.2021.15.178     XML

Certificate

Abstract: The 0-1 Multidimensional Knapsack Problem (MKP) is a NP-Hard problem that has important applications in business and industry. Approximate solution approaches for the MKP in the literature typically provide no guarantee on how close generated solutions are to the optimum. This article demonstrates how general-purpose integer programming software (Gurobi) is iteratively used to generate solutions for the 270 MKP test problems in Beasley’s OR-Library such that, on average, the solutions are guaranteed to be within 0.094% of the optimums and execute in 88 seconds on a standard PC. This methodology, called the simple sequential increasing tolerance (SSIT) matheuristic, uses a sequence of increasing tolerances in Gurobi to generate a solution that is guaranteed to be close to the optimum in a short time. This solution strategy generates bounded solutions in a timely manner without requiring the coding of a problem-specific algorithm. The SSIT results (although guaranteed within 0.094% of the optimums) when compared to known optimums deviated only 0.006% from the optimums—far better than any published results for these 270 MKP test instances.