{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T04:31:28Z","timestamp":1769315488608,"version":"3.49.0"},"reference-count":30,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2023,12,3]],"date-time":"2023-12-03T00:00:00Z","timestamp":1701561600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>A novel approach was developed that combined LP-based row generation with optimization-based sorting to tackle computational challenges posed by budget allocation problems with combinatorial constraints. The proposed approach dynamically generated constraints using row generation and prioritized them using optimization-based sorting to ensure a high-quality solution. Computational experiments and case studies revealed that as the problem size increased, the proposed approach outperformed simplex solutions in terms of solution search time. Specifically, for a problem with 50 projects (N = 50) and 2,251,799,813,685,250 constraints, the proposed approach found a solution in just 1.4 s, while LP failed due to the problem size. The proposed approach demonstrated enhanced computational efficiency and solution quality compared to traditional LP methods.<\/jats:p>","DOI":"10.3390\/computation11120242","type":"journal-article","created":{"date-parts":[[2023,12,4]],"date-time":"2023-12-04T03:40:58Z","timestamp":1701661258000},"page":"242","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["LP-Based Row Generation Using Optimization-Based Sorting Method for Solving Budget Allocation with a Combinatorial Number of Constraints"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4499-8795","authenticated-orcid":false,"given":"Aphisak","family":"Witthayapraphakorn","sequence":"first","affiliation":[{"name":"Department of Industrial Engineering, Faculty of Engineering, University of Phayao, Phayao 56000, Thailand"}]},{"given":"Sasarose","family":"Jaijit","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering, Faculty of Engineering at Kamphaeng Saen, Kasetsart University, Nakhon Pathom 73140, Thailand"}]},{"given":"Peerayuth","family":"Charnsethikul","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering, Faculty of Engineering, Kasetsart University, Bangkok 10900, Thailand"}]}],"member":"1968","published-online":{"date-parts":[[2023,12,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"106046","DOI":"10.1016\/j.cor.2022.106046","article-title":"Optimal budget allocation policy for tabu search in stochastic simulation optimization","volume":"150","author":"Yu","year":"2023","journal-title":"Comput. Oper. Res."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/0022-0000(91)90024-Y","article-title":"Expressing combinatorial optimization problems by linear programs","volume":"43","author":"Yannakakis","year":"1991","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1086\/294232","article-title":"Application of linear programming to financial budgeting and the costing of funds","volume":"32","author":"Charnes","year":"1959","journal-title":"J. Bus."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1080\/001379X6008546907","article-title":"Application of linear programming to financial budgeting and the costing of funds","volume":"5","author":"Norris","year":"1960","journal-title":"Eng. Econ."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"325","DOI":"10.2307\/1237452","article-title":"Use of linear programming in capital budgeting with multiple goals","volume":"53","author":"Candler","year":"1971","journal-title":"Am. J. Agric. Econ."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/BF01386316","article-title":"Partitioning procedures for solving mixed-variables programming problems","volume":"4","author":"Benders","year":"1962","journal-title":"Numer. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"5588486","DOI":"10.1155\/2021\/5588486","article-title":"A comprehensive review on scatter search: Techniques, applications, and challenges","volume":"2021","author":"Kalra","year":"2021","journal-title":"Math. Probl. Eng."},{"key":"ref_8","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, The MIT Press. [3rd ed.]."},{"key":"ref_9","unstructured":"Weingartner, H.M. (1963). Mathematical Programming and the Analysis of Capital Budgeting Problems, Prentice Hall. [1st ed.]."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1080\/05695557008974727","article-title":"Capital budgeting and mixed zero-one integer programming","volume":"2","author":"Unger","year":"1970","journal-title":"AIIE Trans."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1080\/00137917408902772","article-title":"Duality results for discrete capital budgeting models","volume":"19","author":"Unger","year":"1974","journal-title":"Eng. Econ."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1016\/0377-2217(85)90152-3","article-title":"Capital budgeting with benders decomposition","volume":"21","author":"Hummeltenberg","year":"1985","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1143","DOI":"10.1016\/S0305-0548(00)00111-8","article-title":"Row and column generation technique for a multistage cutting stock problem","volume":"29","author":"Zak","year":"2002","journal-title":"Comput. Oper. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.ejor.2017.06.044","article-title":"Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows","volume":"264","author":"Muter","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.ejor.2018.04.042","article-title":"Algorithms for the one-dimensional two-stage cutting stock problem","volume":"271","author":"Muter","year":"2018","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","first-page":"10","article-title":"Row generation technique to solve the problems of capital budgeting allocation under combinatorial constraints","volume":"6","author":"Witthayapraphakorn","year":"2018","journal-title":"TJOR"},{"key":"ref_17","first-page":"1261","article-title":"Budgeting in international humanitarian organizations","volume":"24","author":"Fard","year":"2021","journal-title":"Manuf. Serv. Oper. Manag."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"106972","DOI":"10.1016\/j.epsr.2020.106972","article-title":"Long term transmission expansion planning to improve power system resilience against cascading outages","volume":"192","author":"Qorbani","year":"2022","journal-title":"Electr. Power Syst. Res."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"102498","DOI":"10.1016\/j.omega.2021.102498","article-title":"Optimizing dynamic facility location-allocation for agricultural machinery maintenance using Benders decomposition","volume":"105","author":"Han","year":"2021","journal-title":"Omega"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1007\/s00521-016-2606-z","article-title":"A Benders decomposition for the location-allocation and scheduling model in a healthcare system regarding robust optimization","volume":"29","author":"Karamyar","year":"2018","journal-title":"Neural. Comput. Appl."},{"key":"ref_21","first-page":"3027578","article-title":"SA sorting: A novel sorting technique for large-scale data, Discrete","volume":"2019","author":"Shabaz","year":"2019","journal-title":"J. Comput. Netw. Commun."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"109220","DOI":"10.1016\/j.cie.2023.109220","article-title":"A new hybrid-heuristic for large-scale combinatorial optimization: A case of quadratic assignment problem","volume":"179","author":"Wang","year":"2023","journal-title":"Comput. Ind. Eng."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"6646180","DOI":"10.1155\/2021\/6646180","article-title":"Large-scale storage\/retrieval requests sorting algorithm for multi-I\/O depots automated storage\/retrieval systems","volume":"2021","author":"Song","year":"2021","journal-title":"Discret. Dyn. Nat. Soc."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"100061","DOI":"10.1016\/j.ejco.2023.100061","article-title":"Ranking constraint relaxations for mixed integer programs using a machine learning approach","volume":"11","author":"Weiner","year":"2023","journal-title":"EURO J. Comput. Optim."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1016\/j.ejor.2016.03.002","article-title":"Benders decomposition without separability: A computational study for capacitated facility location problems","volume":"253","author":"Fischetti","year":"2016","journal-title":"Eur. J. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s10732-021-09467-z","article-title":"Enhancing large neighbourhood search heuristics for Benders\u2019 decomposition","volume":"27","author":"Maher","year":"2021","journal-title":"J. Heuristics"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1590\/S0101-74382012005000005","article-title":"Accelerating Benders decomposition with heuristic master problem solutions","volume":"32","author":"Costa","year":"2012","journal-title":"Pesqui. Operacional."},{"key":"ref_28","first-page":"3","article-title":"A Benders decomposition approach for an integrated bin allocation and vehicle routing problem in municipal waste management","volume":"1408","author":"Rossit","year":"2021","journal-title":"Eur. J. Oper. Res."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"105715","DOI":"10.1016\/j.cor.2022.105715","article-title":"Benders decomposition applied to profit maximizing hub location problem with incomplete hub network","volume":"142","author":"Oliveira","year":"2022","journal-title":"Comput. Oper. Res."},{"key":"ref_30","first-page":"37","article-title":"Capital budgeting problem with combinatorial allocation constraints by column generation method","volume":"8","author":"Sangkhasuk","year":"2020","journal-title":"TJOR"}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/12\/242\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:37:04Z","timestamp":1760132224000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/11\/12\/242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,3]]},"references-count":30,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["computation11120242"],"URL":"https:\/\/doi.org\/10.3390\/computation11120242","relation":{},"ISSN":["2079-3197"],"issn-type":[{"value":"2079-3197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,3]]}}}