A Comparison of Exact and Heuristic Approaches to Capital Budgeting

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.

Authors:

• Jindřiška Šedová
• Miloš Šeda

Keywords:

• Capital budgeting
• knapsack problem
• GAMS
• heuristic method
• genetic algorithm.

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.