Using general-purpose integer programming software to generate bounded solutions for the multiple knapsack problem: a guide for or practitioners
DOI:
https://doi.org/10.12928/ijio.v4i1.6446Keywords:
bounded solutions, Integer Programming, Multiple Knapsack Problem, Simple Sequential Increasing, Tolerance (SSIT)Abstract
An NP-Hard combinatorial optimization problem that has significant industrial applications is the Multiple Knapsack Problem. If approximate solution approaches are used to solve the Multiple Knapsack Problem there are no guarantees on solution quality and exact solution approaches can be intricate and challenging to implement. This article demonstrates the iterative use of general-purpose integer programming software (Gurobi) to generate solutions for test problems that are available in the literature. Using the software package Gurobi on a standard PC, we generate in a relatively straightforward manner solutions to these problems in an average of less than a minute that are guaranteed to be within 0.16% of the optimum. This algorithm, called the Simple Sequential Increasing Tolerance (SSIT) algorithm, iteratively increases 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. This approach is attractive to management for solving industrial problems because it is both cost and time effective and guarantees the quality of the generated solutions. Finally, comparing SSIT results for 480 large multiple knapsack problem instances to results using published multiple knapsack problem algorithms demonstrates that SSIT outperforms these specialized algorithms.
References
M. Dell’Amico, M. Delorme, M. Lori, S. Martello, “Mathematical Models and Decomposition Methods for the Multiple Knapsack Problem”, Eur. J. Oper. Res, vol. 274, 886–899, 2019.
I. Ketykó, L. Kecskés, C. Nemes, C. L. Farkas, “Multi-user Computation Offloading as Multiple Knapsack Problem for 5G Mobile Edge Computing”, European Conference on Networks and Communications (EuCNC), Athens, Greece, pp. 225–229, 27–30 June 2016.
M. Labbe, G. Laporte, and S. Martello, “Upper Bounds and Algorithms for the Maximum Cardinality Bin Packing Problem”, Eur. J. Oper. Res., vol. 149, pp. 490–498, 2003.
P. Cappanera, F. Paganelli, F. Paradiso, “VNF Placement for Service Chaining in a Distributed Cloud Environment with Multiple Stakeholders”, Comput. Commun. vol. 133, pp. 24–40, 2019.
F. J. Vasko, D. D. Newhart, K. L. Stott,” A Hierarchical Approach for One-dimensional Cutting Stock Problems in the Steel Industry that Maximizes Yield and Minimizes Overgrading”, Eur. J. Oper. Res, vol. 114, no. 1, pp. 72-82, 1999.
A. S. Fukunaga, “A Branch-and-bound Algorithm for Hard Multiple Knapsack Problems”, Annals of Operations Research, vol. 184, no. 1, pp. 97–119, 2011.
S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Chichester, 1990. (available online at www.or.deis.unibo.it).
H. Kellerer, D. Pisinger, U. Pferschy, Knapsack Problems. Springer, Berlin, 2004.
G. Sur, S. Y. Ryu, J. Kim, H. Lim, “A deep reinforcement learning-based scheme for solving multiple knapsack problems”, Appl. Sci. vol. 12, pp. 3068, 2022. https://doi.org/ 10.3390/app12063068
D. Pisinger, “An Exact Algorithm for Large Multiple Knapsack Problems”, Eur. J. Oper. Res. vol. 114, no. 3, pp. 528–541, 1999.
A. S. Fukunaga, “A New Grouping Genetic Algorithm for the Multiple Knapsack Problem”, Proceedings of the 2008 IEEE Congress on Evolutionary Computation, Hong Kong, China, pp. 2225–22321, 6 June 2008.
A. S. Fukunaga, S. Tazoe, “Combining Multiple Representations in a Genetic Algorithm for the Multiple Knapsack Problem”, 2009 IEEE Congress on Evolutionary Computation, pp. 2423–2430, 2009.
B. McNally, A Simple Sequential Increasing Tolerance Metaheuristic that Generates Bounded Solutions for Combinatorial Optimization Problems. Master’s Thesis, Kutztown University of Pennsylvania, 2021.
B. McNally, Y. Lu, E. Shively-Ertas, M.S. Song, F. J. Vasko, “A Simple and Effective Methodology for Generating Bounded Solutions for the Set K-covering and Set Variable K-covering Problems: A Guide for OR Practitioners”, Review of Computer Engineering Research, vol. 8, no. 2, pp. 76-95, 2021.
Y. Lu, B. McNally, E. Shively-Ertas, F. J. Vasko, “A Simple and Efficient Technique to Generate Bounded Solutions for the Multidimensional Knapsack Problem: a Guide for OR Practitioners”, International Journal of Circuits, Systems, and Signal Processing, vol. 15, pp. 1650-1656, 2021.
A. Dellinger, Y. Lu, B. McNally, M. S. Song, F. J. Vasko,” A Simple and Efficient Technique to Generate Bounded Solutions for the Generalized Assignment Problem: a Guide for OR Practitioners”, Research Reports on Computer Science, pp. 13-34, 2021.
M. S. Song, B. Emerick, Y. Lu, F. J. Vasko, “When to Use Integer Programming Software to Solve Large Multi-Demand Multidimensional Knapsack Problems: A Guide for Operations Research Practitioners,” Engrg. Optim vol. 54, no. 5, pp. 894-906, 2022.
A. Dellinger, Y. Lu, M.S. Song, F. J. Vasko, “Generating Bounded Solutions for Multi-demand Multidimensional Knapsack Problems: a Guide for Operations Research Practitioners,” International Journal of Industrial Optimization, vol. 3, no. 1, pp. 1-21, 2022.
A. Dellinger, Y. Lu, M. S. Song, F. J. Vasko, “Simple Strategies that Generate Bounded Solutions for the Multiple-choice Multi-dimensional Knapsack Problem: A Guide for OR Practitioners”, International Transactions in Operational Research, vol. 0, pp. 1-17, 2022.
F. J. Vasko, “A Computational Note on the Martello-Toth Knapsack Algorithm”, European Journal of Operational Research, vol. 73, no. 1, pp. 169-171, 1994.
J. Tukey, “Comparing Individual Means in the Analysis of Variance”, Biometrics 1949, vol. 5, pp. 99-114, 1949.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Emre Shively-Ertas, Yun Lu, Myung Song, Francis Vasko
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
License and Copyright Agreement
In submitting the manuscript to the journal, the authors certify that:
- They are authorized by their co-authors to enter into these arrangements.
- The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read the International Journal of Industrial Optimization (IJIO) Author Guidelines at http://journal2.uad.ac.id/index.php/ijio/about/submissions#onlineSubmissions
- That it is not under consideration for publication elsewhere,
- That its publication has been approved by all the author(s) and by the responsible authorities tacitly or explicitly of the institutes where the work has been carried out.
- They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
- They agree to the following license and copyright agreement.
Copyright
Authors who publish with the International Journal of Industrial Optimization (IJIO) agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
