Budget allocation problems, commonly referred to as capital budgeting problems, often involve many constraints [1]. These constraints typically consist of 2^N investment patterns, which further increase to 2 ✕ (2^N − 1) patterns when considering upper and lower bounds. Consequently, efficiently and effectively solving these problems becomes increasingly challenging, particularly when considering the total number of projects represented by N. Traditional optimization techniques may struggle to handle the combinatorial explosion of constraints, often resulting in time-consuming computations and no guarantee of optimal solutions within a reasonable timeframe [2]. However, recent advancements in linear programming-based row generation and optimization-based sorting methods offer promising solutions to address these challenges.

Linear programming (LP) provides a powerful framework for modeling and solving optimization problems with linear constraints. By formulating the budget allocation problem as an LP model, decision makers can systematically allocate resources to various activities while considering multiple objectives and constraints ^[3][4][5][3,4,5]. However, when faced with many combinatorial constraints, the traditional LP formulation may become computationally intractable.

An innovative approach combines linear programming-based row generation to overcome this challenge. Row generation involves iteratively generating new constraints (rows) added to the problem formulation, effectively expanding the solution space and refining the solution quality [6]. By iteratively adding constraints that are most relevant to the current solution, the row generation process enables efficient exploration of the combinatorial constraint space.

Furthermore, optimization-based sorting methods enhance the row-generation process by incorporating sorting algorithms tailored to the specific constraints and objectives of the budget allocation problem. This algorithm employs intelligent search strategies to efficiently discover the optimal solutions. With a focus on practical applications, the optimization-based sorting method has demonstrated the ability to generate optimal solutions within a reasonable timeframe ^[7][8][7,8].

The combination of linear programming-based row generation and optimization-based sorting methods offers a powerful approach to solving budget allocation problems with a combinatorial number of constraints. This integrated methodology allows decision makers to handle large-scale optimization problems, allocate resources efficiently, and identify optimal budget allocation strategies.

2. Solving Budget Allocation Problems with Combinatorial Constraints

Budget allocation problems with combinatorial constraints are complex optimization models originating from the study by Weingartner [9], which has found applications in various fields such as resource allocation and project planning. Linear programming (LP) is a widely used technique to solve such problems efficiently. However, when dealing with a large number of constraints, the computational complexity of LP becomes time-consuming to solve. This section explores the application of the row-generation techniques to enhance the efficiency of solving budget allocation problems with combinatorial constraints using sorting methods. Row generation, a sub-technique within Benders decomposition, is a powerful approach initially proposed by Unger ^[10][11][10,11], which offers an application for solving large-scale LP problems in budget allocation. It focuses on generating a subset of constraints, known as “rows”, dynamically during the optimization process. Hummeltenberg [12], Zak [13], Muter et al. [14], Muter and Sezer [15] and Witthayapraphakorn et al. [16] consistently highlight the advantages of employing a row generation algorithm that incorporates a warm-start strategy and an approximation scheme, surpassing the performance of linear programming, particularly in scenarios involving a substantial number of constraints. These compelling findings affirm the efficacy of row-generation technique as an effective approach for addressing linear programming problems characterized by a comprehensive set of constraints. According to the literature reviews over the past decade, a limited number of studies have investigated the application of row-generating techniques in the context of budget allocation problems; however, notable research by Fard et al. [17] has contributed to this area. Their study presents a model employing the bender decomposition method for budgeting purposes within international humanitarian organizations and provides analytical insights into the optimal solution. Additional scholarly studies employ the row generation method to allocate various types of resources, such as energy [18] and location ^[19][20][19,20]. Although the row generation method accelerates solution discovery in large linear problems, its efficacy may diminish with an abundance of constraints, leading to slower solution times. Consequently, researchers are exploring additional methods, such as sorting techniques [21], to enhance the effectiveness of row generation in addressing very large-scale problems. However, there is no observed research integrating heuristics into row generation to address problem solving in large-scale linear programming problems, existing heuristics for solving LP problems with combinatorial constraints prioritize finding the best solution without guaranteeing optimization [22]. The possibility of utilizing effective heuristic methods to generate initial starting points in combinatorial optimization motivates the exploration of applying sorting techniques, specifically in budget allocation problems known for their exceptional efficiency in identifying feasible solutions [21]. Sorting is a technique that aims to prioritize constraints based on their potential impact on the solution quality. This approach involves assigning weights or scores to constraints and ordering them in a way that maximizes the likelihood of finding a feasible solution quickly. Sorting has been successfully employed in various allocation problems. For example, Song and Mu [23] propose a heuristic algorithm based on assignment to solve the sequence sorting problem of large-scale automated storage requests in multiple input/output (multi-I/O) depots. The proposed algorithm considers equivalent merging and minimum cost merging methods of subloops to eliminate subloops that emerged in the sorting process. Their proposed algorithm offers a solution to optimize the sequence of storage requests in multi-I/O depots, which can improve efficiency and cost-effectiveness in practice. Weiner et al. [24] provide valuable insights into the utilization of sorting in subproblems optimization and highlight its potential for solving large-scale mixed-integer programs (MIPs). Specifically, their research demonstrates the effective utilization of machine learning (ML) for ranking constraint relaxations of MIPs. Their proposed method outperforms existing heuristic and ML-based methods in terms of solution quality and computational time. The authors suggest that their approach has the potential to be applied to other optimization problems beyond MIPs. The feasibility of using row generation methods (i.e., Benders decomposition) is hindered by the complexity of combinatorial constraints and the limited time availability for solution generation. Consequently, the utilization of sorting techniques is motivated by the intricate nature of combinatorial constraints while also taking into account the potential implementation of row-generation methods within the available computational time and the problem size to be solved. The current literature on budget allocation problems lacks evidence supporting the effectiveness of combining heuristics and LP approaches (i.e., integer programming, Benders decomposition, and row generation) in achieving optimal solutions. Moreover, studies in related fields, like location allocation and network allocation, provide insights into the comparative speed of solution discovery using mixed methods. Fischetti et al. [25] demonstrate the practical effectiveness and straightforward implementation of their proposed approach, which applies Benders decomposition to solve the facility allocation master problem with non-separable subproblems. By employing a simple sorting application on Benders cut, their study showcases the successful application of generalized Benders cuts for convex problems. Furthermore, numerous studies have explored alternative heuristics beyond sorting to identify optimal solutions in combination with the Benders decomposition method. For example, Maher [26] reveals how large neighborhood search heuristics can enhance Benders decomposition algorithms and improve mixed-integer programming solvers. Costa and Gendron [27], Maheo et al. [28], and Oliveira et al. [29] employ heuristic techniques, such as branch-and-cut, local search, Pareto-optimal cuts, and multiple cuts, to generate additional cuts when solving the master problem through Benders decomposition. Their respective studies focus on fixed-charge network design [27], bin allocation for waste management [28], and multiple allocation hub network design [29].