{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T17:46:44Z","timestamp":1740160004540,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T00:00:00Z","timestamp":1630454400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Syst Assur Eng Manag"],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.1007\/s13198-021-01232-6","type":"journal-article","created":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T10:03:20Z","timestamp":1630490600000},"page":"1087-1093","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reducing the complexity of the knapsack linear integer problem by reformulation techniques"],"prefix":"10.1007","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6279-3729","authenticated-orcid":false,"given":"Elias","family":"Munapo","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9321-5622","authenticated-orcid":false,"given":"Santosh","family":"Kumar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,1]]},"reference":[{"key":"1232_CR1","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.cie.2019.04.025","volume":"132","author":"M Abdel-Basset","year":"2019","unstructured":"Abdel-Basset M, El-Shahat D, Faris H, Mirjalili S (2019) A binary multi-verse optimizer for 0\u20131 multidimensional knapsack problems with application in interactive multimedia systems. Comput Ind Eng 132:187\u2013206","journal-title":"Comput Ind Eng"},{"issue":"5","key":"1232_CR2","first-page":"1140","volume":"4","author":"M Al-Rabeeah","year":"2019","unstructured":"Al-Rabeeah M, Munapo E, Al-Hasani A, Kumar S, Ebehard A (2019) Computational enhancement in the application of the branch and bound method for linear integer programs and related models. IJMEM 4(5):1140\u20131153","journal-title":"IJMEM"},{"key":"1232_CR3","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1287\/opre.46.3.316","volume":"46","author":"C Barnhart","year":"1998","unstructured":"Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch and price column generation for solving huge integer programs. Oper Res 46:316\u2013329","journal-title":"Oper Res"},{"key":"1232_CR4","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1287\/opre.48.2.318.12378","volume":"48","author":"C Barnhart","year":"2000","unstructured":"Barnhart C, Hane CA, Vance P (2000) Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems. Oper Res 48:318\u2013326","journal-title":"Oper Res"},{"key":"1232_CR5","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0167-5060(08)70351-0","volume":"5","author":"EML Bealie","year":"1979","unstructured":"Bealie EML (1979) Branch and bound methods for mathematical programming xj\u00a0=\u00a0100 xj0+101 xj1+102 xj2+\u2026+10k xjK systems. Ann Discrete Math 5:201\u2013219","journal-title":"Ann Discrete Math"},{"volume-title":"Advances in linear and integer programming","year":"1996","key":"1232_CR6","unstructured":"Beasley JE (ed) (1996) Advances in linear and integer programming. Oxford University Press, Oxford"},{"key":"1232_CR7","first-page":"243","volume":"78","author":"L Brunetta","year":"1997","unstructured":"Brunetta L, Conforti M, Rinaldi G (1997) A branch and cut algorithm for the equicut problem. Math Program 78:243\u2013263","journal-title":"Math Program"},{"key":"1232_CR8","doi-asserted-by":"publisher","first-page":"113224","DOI":"10.1016\/j.eswa.2020.113224","volume":"14815","author":"I Dahmani","year":"2020","unstructured":"Dahmani I, Hifi M, Saadi T, Yousef L (2020) A swarm optimization-based search algorithm for the quadratic knapsack problem with conflict graphs. Expert Syst Appl 14815:113224","journal-title":"Expert Syst Appl"},{"key":"1232_CR9","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1093\/comjnl\/8.3.250","volume":"8","author":"RJ Dakin","year":"1965","unstructured":"Dakin RJ (1965) A tree search algorithm for mixed integer programming problems. Comput J 8:250\u2013255","journal-title":"Comput J"},{"issue":"16","key":"1232_CR10","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.ejor.2019.08.027","volume":"281","author":"M Fampa","year":"2020","unstructured":"Fampa M, Lubke D, Wang F, Wolkowicz H (2020) Parametric convex quadratic relaxation of the quadratic knapsack problem. Eur J Oper Res 281(16):36\u201349","journal-title":"Eur J Oper Res"},{"key":"1232_CR11","doi-asserted-by":"publisher","unstructured":"Fomeni FD, Kaparis K, Letchford AN (2020) A cut-and-branch algorithm for the Quadratic Knapsack Problem. Discrete Optim 100579, ISSN 1572\u20135286. https:\/\/doi.org\/10.1016\/j.disopt.2020.100579","DOI":"10.1016\/j.disopt.2020.100579"},{"key":"1232_CR12","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/s10107-005-0644-x","volume":"106","author":"R Fukasawa","year":"2006","unstructured":"Fukasawa R, Longo H, Lysgaard J, Poggi de Aragao M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-price for the capacitated vehicle routing problem. Math Progr Ser A 106:491\u2013511","journal-title":"Math Progr Ser A"},{"key":"1232_CR13","volume-title":"Operations research models and methods","author":"PA Jensen","year":"2003","unstructured":"Jensen PA, Bard JF (2003) Operations research models and methods. John Wiley & Sons Inc, Hoboken"},{"key":"1232_CR14","volume-title":"Computational optimal or provably near-optimal solutions combinatorial optimization","author":"L Ladanyi","year":"2001","unstructured":"Ladanyi L, Ralphs TS, Trotter LE (2001) Branch, Cut, and Price: sequential and parallel, lecture notes in computer science. In: J\u00fcnger M, Naddef D (eds) Computational optimal or provably near-optimal solutions combinatorial optimization. Springer, Berlin"},{"key":"1232_CR15","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.cie.2019.01.010","volume":"129","author":"R Lahyani","year":"2019","unstructured":"Lahyani R, Chebil K, Khemakhem M, Coelho LC (2019) Metaheuristics for solving the multiple Knapsack problem with setup. Comput Ind Eng Vol 129:76\u201389","journal-title":"Comput Ind Eng Vol"},{"key":"1232_CR16","doi-asserted-by":"publisher","first-page":"113310","DOI":"10.1016\/j.eswa.2020.113310","volume":"1491","author":"X Lai","year":"2020","unstructured":"Lai X, Jin-Kao Hao FuZH, Yue D (2020) Diversity-preserving quantum particle swarm optimization for the multidimensional knapsack problem. Expert Syst Appl 1491:113310","journal-title":"Expert Syst Appl"},{"key":"1232_CR17","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1910129","volume":"28","author":"AH Land","year":"1960","unstructured":"Land AH, Doig AG (1960) An automatic method for solving discrete programming problems. Econometrica 28:497\u2013520","journal-title":"Econometrica"},{"key":"1232_CR18","doi-asserted-by":"publisher","first-page":"102004","DOI":"10.1016\/j.omega.2018.11.013","volume":"90","author":"S Martello","year":"2020","unstructured":"Martello S, Monaci M (2020) Algorithmic approaches to the multiple knapsack assignment problem. Omega 90:102004","journal-title":"Omega"},{"key":"1232_CR19","volume-title":"Encyclopedia of Optimization","author":"JE Mitchell","year":"2001","unstructured":"Mitchell JE, Lee EK (2001) Branch and bound methods for integer programming. In: Floudas CA, Pardalos PM (eds) Encyclopedia of Optimization. Kluwer Academic Publishers, Norwell"},{"key":"1232_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4236\/ajor.2016.61001","volume":"6","author":"E Munapo","year":"2016","unstructured":"Munapo E (2016) Solving the binary linear programming model in polynomial time. Am J Oper Res 6:1\u20137. https:\/\/doi.org\/10.4236\/ajor.2016.61001","journal-title":"Am J Oper Res"},{"key":"1232_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/s13198-019-00821-w","author":"E Munapo","year":"2019","unstructured":"Munapo E (2019) The equal tendency algorithm: a new heuristic for the reliability model. Int J Syst Assur Eng Manag. https:\/\/doi.org\/10.1007\/s13198-019-00821-w","journal-title":"Int J Syst Assur Eng Manag"},{"key":"1232_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/23311835.2016.1162372","volume":"3","author":"E Munapo","year":"2016","unstructured":"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 Math 3:1\u201313. https:\/\/doi.org\/10.1080\/23311835.2016.1162372","journal-title":"Cogent Math"},{"key":"1232_CR23","doi-asserted-by":"crossref","unstructured":"Munapo, E. (2020). Improvement of the branch and bound algorithm for solvingthe knapsack linear integer problem, Eastern-European Journal of Enterprise Technologies, pp 59\u201369","DOI":"10.15587\/1729-4061.2020.198849"},{"issue":"1","key":"1232_CR24","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M Padberg","year":"1991","unstructured":"Padberg M, Rinaldi G (1991) A branch and cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev 33(1):60\u2013100","journal-title":"SIAM Rev"},{"key":"1232_CR25","first-page":"381","volume":"45","author":"MWP Salvelsbergh","year":"1997","unstructured":"Salvelsbergh MWP (1997) A branch and price algorithm to solve the generalized assignment problem. Oper Res 45:381\u2013841","journal-title":"Oper Res"},{"issue":"31","key":"1232_CR27","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.ejor.2016.06.049","volume":"256","author":"J Simon","year":"2017","unstructured":"Simon J, Aruna A, Regnier E (2017) An application of the multiple knapsack problem: the self-sufficient marine. Eur J Oper Res 256(31):868\u2013876","journal-title":"Eur J Oper Res"},{"key":"1232_CR29","unstructured":"Taha (2017) Operations research an introuduction, Pearson, Prentice Hall, New Jersey"},{"key":"1232_CR30","doi-asserted-by":"publisher","first-page":"810","DOI":"10.3103\/S014641161807026X","volume":"52","author":"V Vasilchikov","year":"2018","unstructured":"Vasilchikov V (2018) On a recursive-parallel algorithm for solving the Knapsack problem. Autom Control Comput Sci 52:810\u2013816. https:\/\/doi.org\/10.3103\/S014641161807026X","journal-title":"Autom Control Comput Sci"},{"key":"1232_CR31","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1016\/j.asoc.2015.06.004","volume":"34","author":"L Wang","year":"2015","unstructured":"Wang L, Yang Y, Ni H, Ye We, Pardalos PM (2015) A human learning optimization algorithm and its application to multi-dimensional knapsack problems. Appl Soft Comput 34:736\u2013743","journal-title":"Appl Soft Comput"},{"key":"1232_CR32","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1016\/j.future.2019.07.062","volume":"101","author":"Z Wei","year":"2019","unstructured":"Wei Z, Hao JK (2019) Iterated two-phase local search for the set-union Knapsack problem. Futur Gener Comput Syst 101:1005\u20131017","journal-title":"Futur Gener Comput Syst"},{"key":"1232_CR33","volume-title":"Operations research applications and algorithms","author":"WL Winston","year":"2004","unstructured":"Winston WL (2004) Operations research applications and algorithms, 4th edn. Duxbury Press, Pacific Grove","edition":"4"},{"key":"1232_CR34","first-page":"124854","volume":"36915","author":"Z Wu","year":"2020","unstructured":"Wu Z, Jiang B, Karimi HR (2020) A logarithmic descent direction algorithm for the quadratic knapsack problem. Appl Math Comput 36915:124854","journal-title":"Appl Math Comput"},{"issue":"11","key":"1232_CR35","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.ejor.2017.06.058","volume":"264","author":"D Zouache","year":"2018","unstructured":"Zouache D, Moussaoui A, Abdelaziz FB (2018) A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem. Eur J Oper Res 264(11):74\u201388","journal-title":"Eur J Oper Res"}],"container-title":["International Journal of System Assurance Engineering and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13198-021-01232-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13198-021-01232-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13198-021-01232-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,29]],"date-time":"2021-10-29T08:26:58Z","timestamp":1635496018000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13198-021-01232-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,1]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["1232"],"URL":"https:\/\/doi.org\/10.1007\/s13198-021-01232-6","relation":{},"ISSN":["0975-6809","0976-4348"],"issn-type":[{"type":"print","value":"0975-6809"},{"type":"electronic","value":"0976-4348"}],"subject":[],"published":{"date-parts":[[2021,9,1]]},"assertion":[{"value":"7 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Authors declare that there is no conflict of interest in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of interest"}}]}}