Commenced in January 2007
Paper Count: 30172
A Comparison of Exact and Heuristic Approaches to Capital Budgeting
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.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085471Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1366
 J. T. Alander, "On Optimal Population Size of Genetic Algorithms," in Proceedings of CompEuro 92, IEEE Computer Society Press, pp. 65-70, 1992.
 R. Battiti and G. Tecchioli, "Local Search with Memory: Benchmarking RTS," Operations Research Spectrum, vol. 17, no. 2/3, pp. 67-86, 1996.
 A. Brooke, D. Kendrick and A. Meeraus, GAMS, release 2.25. A User-s Guide. Danvers, Massachussetts: Boyd & Fraser Publishing Company, 1992.
 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.
 P. Chu, "A Genetic Algorithm Approach for Combinatorial Optimisation Problems," PhD thesis, The Management School Imperial College of Science, Technology and Medicine, London, 1997.
 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.
 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).
 X. Huang, "Mean-variance Model for Fuzzy Capital Budgeting," Computers & Industrial Engineering, vol. 55, issue 1, pp. 34-47, 2008.
 F. Glover and M. Laguna, Tabu Search. Boston: Kluwer Academic Publishers, 1997.
 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.
 J. Klapka, J. Dvoř├ík and P. Popela. Methods of Operational Research (in Czech). Brno: VUTIUM, 2001.
 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.
 Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics. Berlin: Springer-Verlag, 2000.
 Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer Verlag, 1996.
 C.R. Reeves, Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publications, 1993.
 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.
 M.A. Trick, "A Tutorial on Integer Programming", http://mat.gsia.cmu.edu/orclass/integer/integer.html, 1997.