Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 31113
A Comparison of Exact and Heuristic Approaches to Capital Budgeting

Authors: Jindřiška Šedová, Miloš Šeda


This paper summarizes and compares approaches to solving the knapsack problem and its known application in capital budgeting. The first approach uses deterministic methods and can be applied to small-size tasks with a single constraint. We can also apply commercial software systems such as the GAMS modelling system. However, because of NP-completeness of the problem, more complex problem instances must be solved by means of heuristic techniques to achieve an approximation of the exact solution in a reasonable amount of time. We show the problem representation and parameter settings for a genetic algorithm framework.

Keywords: Genetic Algorithm, Capital Budgeting, knapsack problem, GAMS, heuristic method

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1436


[1] J. T. Alander, "On Optimal Population Size of Genetic Algorithms," in Proceedings of CompEuro 92, IEEE Computer Society Press, pp. 65-70, 1992.
[2] R. Battiti and G. Tecchioli, "Local Search with Memory: Benchmarking RTS," Operations Research Spectrum, vol. 17, no. 2/3, pp. 67-86, 1996.
[3] A. Brooke, D. Kendrick and A. Meeraus, GAMS, release 2.25. A User-s Guide. Danvers, Massachussetts: Boyd & Fraser Publishing Company, 1992.
[4] A. Chandra, N.M. Menon and B.K. Mishra, "Budgeting for Information Technology," International Journal of Accounting Information Systems, vol. 8, issue 4, pp. 264-282, 2007.
[5] P. Chu, "A Genetic Algorithm Approach for Combinatorial Optimisation Problems," PhD thesis, The Management School Imperial College of Science, Technology and Medicine, London, 1997.
[6] L. Eldenburg and R. Krishnan, "Management Accounting and Control in Health Care: An Economics Perspective," Handbooks of Management Accounting Research, vol. 2, pp. 859-883, 2006.
[7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Company, 1997 (19th printing).
[8] X. Huang, "Mean-variance Model for Fuzzy Capital Budgeting," Computers & Industrial Engineering, vol. 55, issue 1, pp. 34-47, 2008.
[9] F. Glover and M. Laguna, Tabu Search. Boston: Kluwer Academic Publishers, 1997.
[10] D. Kim, "Capital Budgeting for New Projects: On the Role of Auditing in Information Acquisition," Journal of Accounting and Economics, vol. 41, issue 3, pp. 257-270, 2006.
[11] J. Klapka, J. Dvoř├ík and P. Popela. Methods of Operational Research (in Czech). Brno: VUTIUM, 2001.
[12] R. Liang and J. Gao, "Dependent-Chance Programming Models for Capital Budgeting in Fuzzy Environments," Tsinghua Science & Technology, vol. 13, issue 1, pp. 117-120, 2008.
[13] Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics. Berlin: Springer-Verlag, 2000.
[14] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer Verlag, 1996.
[15] C.R. Reeves, Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publications, 1993.
[16] M. Šeda, "Solving Resource-Constrained Project Scheduling Problem As a Sequence of Multi-Knapsack Problems," WSEAS Transactions on Information Science and Applications, vol. 3, issue 10, pp. 1785-1791, 2006.
[17] M.A. Trick, "A Tutorial on Integer Programming",, 1997.