Row Generation Technique to Solve the Problems of Capital Budgeting Allocation under Combinatorial Constraints
Keywords:
Problem of Capital Budgeting Allocation under Combinatorial Constraints, Row Generation Technique, Large-scale Linear Programming, Mathematical ModelAbstract
This research aims to study capital budgeting allocation under very large combinatorial constraints to consider all alternatives of project investments under limited resources using the row generation technique. The amount of combinatorial constraints in mathematical model of this research is equal to 2N-1 where N is the number of projects. If problems of capital budgeting allocation occur due to many projects, many constraints will follow accordingly. As a result, the mathematical model will consist of a very large N and may have difficulty in solving the problems. Therefore, the researchers apply the row generation technique to reduce a number of constraints of capital budgeting allocation down to the number of constraints necessary to find the answers. The results indicate that the row generation technique uses less processing time than the linear programming with over 12 projects. For example, for 20 projects, the processing time to solve the problems by using the linear programming technique is more than 48 hours. On the other hand, for 50 projects, the processing time to solve the problems by using the row generation technique is less than 5 minutes.
References
[2] G. Dantzig, R. Fulkerson, and S. Jonhson, “Solution of a large-scale travelling-salesman problem”, Journal of the Operation Research Society of America, pp. 393-410, 1954.
[3] C. Gilmore, and E. Gomory, “A linear programming approach to the cutting-stock problem”, Operations Research, Vol. 9, No. 11, pp. 849–859, 1961.
[4] M. Gamache, F. Soumis, G. Marquis, and J. Desrosiers, “A Column generation approach for large-scale aircrew rostering problems”, Operations Research, Vol. 47, pp. 247-263, 1999.
[5] P. Charnsethikul, “A column generations approach for the products mix based semi-infinite linear programming model”. International Journal of Management Science and Engineering Management, Vol. 6, No. 2, 105-108, 2011.
[6] H. M. Weingartner, “Criteria for programming investment project selection”, Journal of Industrial Economics, Vol. 11, pp. 65–76, 1966.
[7] H. M. Weingartner, “Capital budgeting of interrelated projects: survey and synthesis”, Management Science, Vol. 12, pp. 485-516, 1966.
[8] M. Padberg M, M.J. Wilczak, “Optimal project selection when borrowing and lending rates differ”, Mathematical and Computer Modelling, Vol. 29, pp. 63-78, 1999.
[9] P. K. De, D. Acharya, K. C. Sahu, “A chance-constrained goal programming model for capital budgeting”, Journal of the Operational Research Society, Vol. 33, pp. 635-638, 1982.
[10] M. A. Odijk, “A constraint generation algorithm for the construction of periodic railway timetables”, Transportation Research, Vol. 30, No. 6, pp. 455-464, 1995.
[11] L. Williams, J. Fisher, and A. Willsky, “A constraint generation integer programming approach to information theoretic sensor resource management”, IEEE/SP 14th Workshop on Statistical Signal Processing, pp. 59-63, 2007.
[12] F. Croce, C. Koulamas, and V. T'kindt, “A constraint generation approach for the two-machine flow shop problem with jobs selection”, Combinatorial Optimization: Third International Symposium (ISCO 2014), pp. 198-207, 2014.
[13] A. C. Suyabatmaz, G. Sahin. “A column-and-row generation algorithm for a crew planning problem in railways”. Operations Research Proceedings, pp.335-340, 2011.
[14] İ Muter, Ş Birbil, and K. Bülbül, “Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows”, Mathematical Programming, Vol. 142, No. 1-2, pp. 47-82, 2013.
