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

Автор(и)

DOI:

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

Ключові слова:

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

Анотація

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

Біографія автора

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

Посилання

  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

##submission.downloads##

Опубліковано

2020-04-30

Як цитувати

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

Номер

Том 2 № 4 (104) (2020): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2020 Elias Munapo

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.