Improvement of the branch and bound algorithm for solving the knapsack linear integer problem

Authors

DOI:

https://doi.org/10.15587/1729-4061.2020.198849

Keywords:

knapsack integer problem, reformulation, branch and bound algorithm, unimodular, computational complexity

Abstract

The paper presents a new reformulation approach to reduce the complexity of a branch and bound algorithm for solving the knapsack linear integer problem. The branch and bound algorithm in general relies on the usual strategy of first relaxing the integer problem into a linear programing (LP) model. If the linear programming optimal solution is integer then, the optimal solution to the integer problem is available. If the linear programming optimal solution is not integer, then a variable with a fractional value is selected to create two sub-problems such that part of the feasible region is discarded without eliminating any of the feasible integer solutions. The process is repeated on all variables with fractional values until an integer solution is found. In this approach variable sum and additional constraints are generated and added to the original problem before solving. In order to do this the objective bound of knapsack problem is quickly determined. The bound is then used to generate a set of variable sum limits and four additional constraints. From the variable sum limits, initial sub-problems are constructed and solved. The optimal solution is then obtained as the best solution from all the sub-problems in terms of the objective value. The proposed procedure results in sub-problems that have reduced complexity and easier to solve than the original problem in terms of numbers of branch and bound iterations or sub-problems.

The knapsack problem is a special form of the general linear integer problem. There are so many types of knapsack problems. These include the zero-one, multiple, multiple-choice, bounded, unbounded, quadratic, multi-objective, multi-dimensional, collapsing zero-one and set union knapsack problems. The zero-one knapsack problem is one in which the variables assume 0 s and 1 s only. The reason is that an item can be chosen or not chosen. In other words there is no way it is possible to have fractional amounts or items. This is the easiest class of the knapsack problems and is the only one that can be solved in polynomial by interior point algorithms and in pseudo-polynomial time by dynamic programming approaches. The multiple-choice knapsack problem is a generalization of the ordinary knapsack problem, where the set of items is partitioned into classes. The zero-one choice of taking an item is replaced by the selection of exactly one item out of each class of items

Author Biography

Elias Munapo, North West University Mmabatho Unit 5, Mahikeng, 2790, Mafikeng, South Africa

PhD, Professor of Operations Research

Department of Statistics and Operations Research

School of Economics and Decision Sciences

References

  1. Al-Rabeeah, M., Munapo, E., Al-Hasani, A., Kumar, S., Eberhard, A. (2019). Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models. International Journal of Mathematical, Engineering and Management Sciences, 4 (5), 1140–1153. doi: https://doi.org/10.33889/ijmems.2019.4.5-090
  2. Beasley, J. E. (1996). Advances in Linear and Integer Programming. Oxford University Press.
  3. Kumar, S., Munapo, E., Jones, B. C. (2007). An Integer Equation Controlled Descending Path to a Protean Pure Integer Program. Indian Journal of Mathematics, 49 (2), 211–237.
  4. Taha, H. A. (2016). Operations Research: An Introduction. Pearson Education Limited, 848.
  5. Winston, W. L. (2003). Operations Research Applications and Algorithms. Duxbury Press, 1440.
  6. Land, A. H., Doig, A. G. (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28 (3), 497. doi: https://doi.org/10.2307/1910129
  7. Dakin, R. J. (1965). A tree-search algorithm for mixed integer programming problems. The Computer Journal, 8 (3), 250–255. doi: https://doi.org/10.1093/comjnl/8.3.250
  8. Munapo, E. (2020). Improving the Optimality Verification and the Parallel Processing of the General Knapsack Linear Integer Problem. Research Advancements in Smart Technology. Optimization, and Renewable Energy. Chap. 3.
  9. Munapo, E., Kumar, S. (2016). Knapsack constraint reformulation: A new approach that significantly reduces the number of sub-problems in the branch and bound algorithm. Cogent Mathematics, 3 (1). doi: https://doi.org/10.1080/23311835.2016.1162372
  10. Vasilchikov, V. V. (2018). On а Recursive-Parallel Algorithm for Solving the Knapsack Problem. Automatic Control and Computer Sciences, 52 (7), 810–816. doi: https://doi.org/10.3103/s014641161807026x
  11. Bhattacharjee, K. K., Sarmah, S. P. (2014). Shuffled frog leaping algorithm and its application to 0/1 knapsack problem. Applied Soft Computing, 19, 252–263. doi: https://doi.org/10.1016/j.asoc.2014.02.010
  12. Simon, J., Apte, A., Regnier, E. (2017). An application of the multiple knapsack problem: The self-sufficient marine. European Journal of Operational Research, 256 (3), 868–876. doi: https://doi.org/10.1016/j.ejor.2016.06.049
  13. Lahyani, R., Chebil, K., Khemakhem, M., Coelho, L. C. (2019). Matheuristics for solving the Multiple Knapsack Problem with Setup. Computers & Industrial Engineering, 129, 76–89. doi: https://doi.org/10.1016/j.cie.2019.01.010
  14. Martello, S., Monaci, M. (2020). Algorithmic approaches to the multiple knapsack assignment problem. Omega, 90, 102004. doi: https://doi.org/10.1016/j.omega.2018.11.013
  15. Bienstock, D., Faenza, Y., Malinović, I., Mastrolilli, M., Svensson, O., Zuckerberg, M. (2020). On inequalities with bounded coefficients and pitch for the min knapsack polytope. Discrete Optimization, 100567. doi: https://doi.org/10.1016/j.disopt.2020.100567
  16. Fampa, M., Lubke, D., Wang, F., Wolkowicz, H. (2020). Parametric convex quadratic relaxation of the quadratic knapsack problem. European Journal of Operational Research, 281 (1), 36–49. doi: https://doi.org/10.1016/j.ejor.2019.08.027
  17. Dahmani, I., Hifi, M., Saadi, T., Yousef, L. (2020). A swarm optimization-based search algorithm for the quadratic knapsack problem with conflict Graphs. Expert Systems with Applications, 148, 113224. doi: https://doi.org/10.1016/j.eswa.2020.113224
  18. Wu, Z., Jiang, B., Karimi, H. R. (2020). A logarithmic descent direction algorithm for the quadratic knapsack problem. Applied Mathematics and Computation, 369, 124854. doi: https://doi.org/10.1016/j.amc.2019.124854
  19. Djeumou Fomeni, F., Kaparis, K., Letchford, A. N. (2020). A cut-and-branch algorithm for the Quadratic Knapsack Problem. Discrete Optimization, 100579. doi: https://doi.org/10.1016/j.disopt.2020.100579
  20. Bandyopadhyay, S., Maulik, U., Chakraborty, R. (2013). Incorporating ϵ-dominance in AMOSA: Application to multiobjective 0/1 knapsack problem and clustering gene expression data. Applied Soft Computing, 13 (5), 2405–2411. doi: https://doi.org/10.1016/j.asoc.2012.11.050
  21. Zouache, D., Moussaoui, A., Ben Abdelaziz, F. (2018). A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem. European Journal of Operational Research, 264 (1), 74–88. doi: https://doi.org/10.1016/j.ejor.2017.06.058
  22. Abdel-Basset, M., El-Shahat, D., Faris, H., Mirjalili, S. (2019). A binary multi-verse optimizer for 0-1 multidimensional knapsack problems with application in interactive multimedia systems. Computers & Industrial Engineering, 132, 187–206. doi: https://doi.org/10.1016/j.cie.2019.04.025
  23. Arin, A., Rabadi, G. (2016). Local search versus Path Relinking in metaheuristics: Redesigning Meta-RaPS with application to the multidimensional knapsack problem. Applied Soft Computing, 46, 317–327. doi: https://doi.org/10.1016/j.asoc.2016.05.016
  24. Wang, L., Yang, R., Ni, H., Ye, W., Fei, M., Pardalos, P. M. (2015). A human learning optimization algorithm and its application to multi-dimensional knapsack problems. Applied Soft Computing, 34, 736–743. doi: https://doi.org/10.1016/j.asoc.2015.06.004
  25. Lai, X., Hao, J.-K., Fu, Z.-H., Yue, D. (2020). Diversity-preserving quantum particle swarm optimization for the multidimensional knapsack problem. Expert Systems with Applications, 149, 113310. doi: https://doi.org/10.1016/j.eswa.2020.113310
  26. Wei, Z., Hao, J.-K. (2019). Iterated two-phase local search for the Set-Union Knapsack Problem. Future Generation Computer Systems, 101, 1005–1017. doi: https://doi.org/10.1016/j.future.2019.07.062
  27. Brunetta, L., Conforti, M., Rinaldi, G. (1997). A branch-and-cut algorithm for the equicut problem. Mathematical Programming, 78 (2), 243–263. doi: https://doi.org/10.1007/bf02614373
  28. Mitchell, J. E. (2001). Branch and cut algorithms for integer programming. Encyclopedia of Optimization. Kluwer Academic Publishers.
  29. Padberg, M., Rinaldi, G. (1991). A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. SIAM Review, 33 (1), 60–100. doi: https://doi.org/10.1137/1033004
  30. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., Vance, P. H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research, 46 (3), 316–329. doi: https://doi.org/10.1287/opre.46.3.316
  31. Savelsbergh, M. (1997). A Branch-and-Price Algorithm for the Generalized Assignment Problem. Operations Research, 45 (6), 831–841. doi: https://doi.org/10.1287/opre.45.6.831
  32. Barnhart, C., Hane, C. A., Vance, P. H. (2000). Using Branch-and-Price-and-Cut to Solve Origin-Destination Integer Multicommodity Flow Problems. Operations Research, 48 (2), 318–326. doi: https://doi.org/10.1287/opre.48.2.318.12378
  33. Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. de, Reis, M., Uchoa, E., Werneck, R. F. (2005). Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem. Mathematical Programming, 106 (3), 491–511. doi: https://doi.org/10.1007/s10107-005-0644-x
  34. Ladányi, L., Ralphs, T. K., Trotter, L. E. (2001). Branch, Cut, and Price: Sequential and Parallel. Computational Combinatorial Optimization, 223–260. doi: https://doi.org/10.1007/3-540-45586-8_6
  35. Meng, F., Chu, D., Li, K., Zhou, X. (2019). Multiple-class multidimensional knapsack optimisation problem and its solution approaches. Knowledge-Based Systems, 166, 1–17. doi: https://doi.org/10.1016/j.knosys.2018.11.006
  36. Gurski, F., Rehs, C., Rethmann, J. (2019). Knapsack problems: A parameterized point of view. Theoretical Computer Science, 775, 93–108. doi: https://doi.org/10.1016/j.tcs.2018.12.019
  37. Khonji, M., Karapetyan, A., Elbassioni, K., Chau, S. C.-K. (2019). Complex-demand scheduling problem with application in smart grid. Theoretical Computer Science, 761, 34–50. doi: https://doi.org/10.1016/j.tcs.2018.08.023
  38. Chakraborty, T., Misra, I. S. (2020). A novel three-phase target channel allocation scheme for multi-user Cognitive Radio Networks. Computer Communications, 154, 18–39. doi: https://doi.org/10.1016/j.comcom.2020.02.026
  39. Samavati, M., Essam, D., Nehring, M., Sarker, R. (2017). A methodology for the large-scale multi-period precedence-constrained knapsack problem: an application in the mining industry. International Journal of Production Economics, 193, 12–20. doi: https://doi.org/10.1016/j.ijpe.2017.06.025
  40. Hassanzadeh, A., Xu, Z., Stoleru, R., Gu, G., Polychronakis, M. (2016). PRIDE: A practical intrusion detection system for resource constrained wireless mesh networks. Computers & Security, 62, 114–132. doi: https://doi.org/10.1016/j.cose.2016.06.007
  41. Oprea, S. V., Bâra, A., Ifrim, G. A., Coroianu, L. (2019). Day-ahead electricity consumption optimization algorithms for smart homes. Computers & Industrial Engineering, 135, 382–401. doi: https://doi.org/10.1016/j.cie.2019.06.023
  42. Amiri, A. (2020). A Lagrangean based solution algorithm for the knapsack problem with setups. Expert Systems with Applications, 143, 113077. doi: https://doi.org/10.1016/j.eswa.2019.113077
  43. Alanne, K. (2004). Selection of renovation actions using multi-criteria “knapsack” model. Automation in Construction, 13 (3), 377–391. doi: https://doi.org/10.1016/j.autcon.2003.12.004
  44. Delgado-Antequera, L., Caballero, R., Sánchez-Oro, J., Colmenar, J. M., Martí, R. (2020). Iterated greedy with variable neighborhood search for a multiobjective waste collection problem. Expert Systems with Applications, 145, 113101. doi: https://doi.org/10.1016/j.eswa.2019.113101
  45. El Yafrani, M., Ahiod, B. (2017). A local search based approach for solving the Travelling Thief Problem: The pros and cons. Applied Soft Computing, 52, 795–804. doi: https://doi.org/10.1016/j.asoc.2016.09.047
  46. Micheli, G., Weger, V. (2019). On Rectangular Unimodular Matrices over the Algebraic Integers. SIAM Journal on Discrete Mathematics, 33 (1), 425–437. doi: https://doi.org/10.1137/18m1177093

Downloads

Published

2020-04-30

How to Cite

Munapo, E. (2020). Improvement of the branch and bound algorithm for solving the knapsack linear integer problem. Eastern-European Journal of Enterprise Technologies, 2(4 (104), 59–69. https://doi.org/10.15587/1729-4061.2020.198849

Issue

Vol. 2 No. 4 (104) (2020): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2020 Elias Munapo

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.