A Comparison of Exact and Heuristic Approaches to Capital Budgeting

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

Abstract:

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: Capital budgeting, knapsack problem, GAMS, heuristic method, genetic algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085471

References:

[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", http://mat.gsia.cmu.edu/orclass/integer/integer.html, 1997.