Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1
Sasarose Jaijit
 -- 1252 2023-12-19 10:00:09 |
2 layout & references
Sirius Huang
 Meta information modification 1252 2023-12-21 09:15:39 |

Video Upload Options

Do you have a full video?
Send video materials Upload full video

Confirm

Are you sure to Delete?
Yes No
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
Witthayapraphakorn, A.; Jaijit, S.; Charnsethikul, P. Budget Allocation with Combinatorial Constraints. Encyclopedia. Available online: https://encyclopedia.pub/entry/52913 (accessed on 17 May 2024).
Witthayapraphakorn A, Jaijit S, Charnsethikul P. Budget Allocation with Combinatorial Constraints. Encyclopedia. Available at: https://encyclopedia.pub/entry/52913. Accessed May 17, 2024.
Witthayapraphakorn, Aphisak, Sasarose Jaijit, Peerayuth Charnsethikul. "Budget Allocation with Combinatorial Constraints" Encyclopedia, https://encyclopedia.pub/entry/52913 (accessed May 17, 2024).
Witthayapraphakorn, A., Jaijit, S., & Charnsethikul, P. (2023, December 19). Budget Allocation with Combinatorial Constraints. In Encyclopedia. https://encyclopedia.pub/entry/52913
Witthayapraphakorn, Aphisak, et al. "Budget Allocation with Combinatorial Constraints." Encyclopedia. Web. 19 December, 2023.
Budget Allocation with Combinatorial Constraints
Edit
This entry is adapted from the peer-reviewed paper 10.3390/computation11120242

Budget allocation problems, commonly referred to as capital budgeting problems, often involve many constraints. Consequently, efficiently and effectively solving these problems becomes increasingly challenging. Advancements in linear programming-based row generation and optimization-based sorting methods offer promising solutions to address these challenges.

row generation sorting method linear programming large-scale problem budget allocation capital budgeting

1. Introduction

Budget allocation problems, commonly referred to as capital budgeting problems, often involve many constraints [1]. These constraints typically consist of 2N investment patterns, which further increase to 2 ✕ (2N − 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]. 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].
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], 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]. 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].

References

  1. Yu, C.; Lahrichi, N.; Matta, A. Optimal budget allocation policy for tabu search in stochastic simulation optimization. Comput. Oper. Res. 2023, 150, 106046.
  2. Yannakakis, M. Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 1991, 43, 441–466.
  3. Charnes, A.; Cooper, W.W.; Miller, M.H. Application of linear programming to financial budgeting and the costing of funds. J. Bus. 1959, 32, 20–46.
  4. Norris, W.T. Application of linear programming to financial budgeting and the costing of funds. Eng. Econ. 1960, 5, 55–56.
  5. Candler, W.; Boehlje, M. Use of linear programming in capital budgeting with multiple goals. Am. J. Agric. Econ. 1971, 53, 325–330.
  6. Benders, J.F. Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 1962, 4, 238–252.
  7. Kalra, M.; Tyagi, S.; Kumar, V.; Kaur, M.; Mashwani, W.K.; Shah, H.; Shah, K. A comprehensive review on scatter search: Techniques, applications, and challenges. Math. Probl. Eng. 2021, 2021, 5588486.
  8. Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. Introduction to Algorithms, 3rd ed.; The MIT Press: London, UK, 2009; pp. 5–15.
  9. Weingartner, H.M. Mathematical Programming and the Analysis of Capital Budgeting Problems, 1st ed.; Prentice Hall: Englewood Cliffs, NJ, USA, 1963; pp. 139–157.
  10. Unger, V.E. Capital budgeting and mixed zero-one integer programming. AIIE Trans. 1970, 2, 28–36.
  11. Unger, V.E. Duality results for discrete capital budgeting models. Eng. Econ. 1974, 19, 237–251.
  12. Hummeltenberg, W. Capital budgeting with benders decomposition. Eur. J. Oper. Res. 1985, 21, 318–329.
  13. Zak, E.J. Row and column generation technique for a multistage cutting stock problem. Comput. Oper. Res. 2002, 29, 1143–1156.
  14. Muter, I.; Birbil, S.I.; Bülbül, K. Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows. Eur. J. Oper. Res. 2018, 264, 29–45.
  15. Muter, I.; Sezer, Z. Algorithms for the one-dimensional two-stage cutting stock problem. Eur. J. Oper. Res. 2018, 271, 20–32.
  16. Witthayapraphakorn, A.; Thavorn, E.; Tippayasak, R.; Charnsethikul, P. Row generation technique to solve the problems of capital budgeting allocation under combinatorial constraints. TJOR 2018, 6, 10–21.
  17. Fard, M.K.; Ljubić, I.; Papier, F. Budgeting in international humanitarian organizations. Manuf. Serv. Oper. Manag. 2021, 24, 1261–1885.
  18. Qorbani, M.; Amraee, T. Long term transmission expansion planning to improve power system resilience against cascading outages. Electr. Power Syst. Res. 2022, 192, 106972.
  19. Han, J.; Zhang, J.; Zeng, B.; Mao, M. Optimizing dynamic facility location-allocation for agricultural machinery maintenance using Benders decomposition. Omega 2021, 105, 102498.
  20. Karamyar, F.; Sadeghi, J.; Yazdi, M.M. A Benders decomposition for the location-allocation and scheduling model in a healthcare system regarding robust optimization. Neural. Comput. Appl. 2018, 29, 873–886.
  21. Shabaz, M.; Kumar, A. SA sorting: A novel sorting technique for large-scale data, Discrete. J. Comput. Netw. Commun. 2019, 2019, 3027578.
  22. Wang, H.; Alidaee, B. A new hybrid-heuristic for large-scale combinatorial optimization: A case of quadratic assignment problem. Comput. Ind. Eng. 2023, 179, 109220.
  23. Song, Y.B.; Mu, H.B. Large-scale storage/retrieval requests sorting algorithm for multi-I/O depots automated storage/retrieval systems. Discret. Dyn. Nat. Soc. 2021, 2021, 6646180.
  24. Weiner, J.; Ernst, A.T.; Li, X.; Sun, Y. Ranking constraint relaxations for mixed integer programs using a machine learning approach. EURO J. Comput. Optim. 2023, 11, 100061.
  25. Fischetti, M.; Ljubić, I.; Sinnl, M. Benders decomposition without separability: A computational study for capacitated facility location problems. Eur. J. Oper. Res. 2016, 253, 557–569.
  26. Maher, S.J. Enhancing large neighbourhood search heuristics for Benders’ decomposition. J. Heuristics 2021, 27, 615–648.
  27. Costa, A.M.; Gendron, B. Accelerating Benders decomposition with heuristic master problem solutions. Pesqui. Operacional. 2012, 32, 3–20.
  28. Mahéo, A.; Rossit, D.G.; Kilby, P. A Benders decomposition approach for an integrated bin allocation and vehicle routing problem in municipal waste management. Eur. J. Oper. Res. 2021, 1408, 3–18.
  29. Oliveira, F.A.; de Sá, E.M.; de Souza, S.R. Benders decomposition applied to profit maximizing hub location problem with incomplete hub network. Comput. Oper. Res. 2022, 142, 105715.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license; additional terms may apply. By using this site, you agree to the Terms and Conditions and Privacy Policy.
Upload a video for this entry
Information
Subjects: Mathematics, Applied
Contributors MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
Aphisak Witthayapraphakorn
,
Sasarose Jaijit
,
Peerayuth Charnsethikul
View Times: 119
Revisions: 2 times (View History)
Update Date: 21 Dec 2023
Table of Contents
    1000/1000
    Hot Most Recent
    Feedback