Combinatorial approaches to the capital-budgeting problem

• Autorzy: Pichugina O.
• Języki publikacji: EN

Abstrakty

EN

Optimization approaches, combinatorial and continuous, to a capital-budgeting problem (CBP) are presented. This NP-hard problem, traditionally modelled as a linear binary problem, is represented as a biquadratic over an intersection of a sphere and a supersphere. This allows applying nonlinear optimization to it. Also, the method of combinatorial and surface cuttings (MCSC) is adopted to (CBP). For the single constrained version (1CBP), new combinatorial models are introduced based on joint analysis of the constraint, objective function, and feasible region. Equivalence of (1CBP) to the multichoice knapsack problem (MCKP) is shown. Peculiarities of Branch&Bound techniques to (1CBP) are described.

Słowa kluczowe

EN

capital-budgeting problem; integer programming; knapsack problem; combinatorial optimization; Branch and Bound

• Wydawca: Polish Academy of Sciences, Branch in Lublin
• Czasopismo: ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes
• Rocznik: 2016
• Tom: Vol. 5, No 4
• Strony: 29--36
• Opis fizyczny: Bibliogr. 24 poz., wz.

Twórcy

autor

Pichugina O.

• Kharkiv National University of Radio Electronics

Bibliografia

• 1. Paranchuk S., Korbutyak A., 2013. Problems investment support innovative development of the national economy and solutions. Econtechmod. An Internetional Quaterly Journal, 2(4), 53–60.
• 2. Podolchak N., Melnyk L. and Chepil B., 2014. Improving administrative management costs using optimization modeling. Econtechmod. An Internetional Quaterly Journal, 1(1), 75–80.
• 3. Markowitz H., Manne A., 1957. On the Solution of Discrete Programming Problems. Econometrica, (1), 84-110.
• 4. Hoffman K., Padberg M., 2001. Combinatorial and Integer Optimization. Encyclopedia of Operations Research & Management Science, 94–102.
• 5. Bradley S., Hax A. and Magnanti T., 1977. Applied Mathematical Programming. Reading, Mass: Addison-Wesley, 716.
• 6. Schrijver A., 1998. Theory of Linear and Integer Programming. Chichester, New-York: Wiley, 484.
• 7. Wolsey L. and Nemhauser G., 1999. Integer and Combinatorial Optimization (1 edition). New York: Wiley-Interscience, 763.
• 8. Papadimitriou C., Steiglitz K., 2013. Combinatorial Optimization: Algorithms and Complexity. New York: Dover Publications, 528.
• 9. Taha H., 2014. Integer Programming: Theory, Applications, and Computations. New York: Academic Press, 392.
• 10. Martello S. and Toth P., 1990. Knapsack Problems: Algorithms and Computer Implementations. Chichester, New York: Wiley, 308.
• 11. Kellerer H., Pferschy U., Pisinger D., 2010. Knapsack Problems (Softcover reprint of hardcover 1st ed. 2004 edition). Berlin, New York: Springer, 548.
• 12. Hiroshi I., 2014. Some Thoughts on the 2- Approximation Algorithm for Knapsack Problems: A Survey. Far East Journal of Applied Mathematics, 87(3), 257–267.
• 13. Escudero L., Martello S. and Toth P., 1998. On tightening 0-1 programs based on extensions of pure 0-1 knapsack and subset-sum problems. Annals of Operations Research, 81(1–4), 379–404.
• 14. Shaheen A., Sleit A., 2016. Comparing between different approaches to solve the 0/1 Knapsack problem. International Journal of Computer Science and Network Security, 16(7), 1–10.
• 15. Lust T., Teghem J., 2012. The multiobjective multidimensional knapsack problem: a survey and a new approach. International Transactions in Operational Research, 19(4), 495–520.
• 16. Öncan T., 2007. A Survey of the Generalized Assignment Problem and Its Applications. INFOR, 45(3), 123–141.
• 17. Stoyan Y., Yakovlev S., 1986. Mathematical models and optimization methods in Geometric Design. Kiev: Naukova Dumka, 268. (in Russian).
• 18. Stoyan Y., Yemets O., 1993. Theory and methods of Euclidean combinatorial optimization. Kiev: ISSE, 188. (in Ukrainian).
• 19. Pichugina O., Yakovlev S., 2016. Continuous Approaches to the Unconstrained Binary Quadratic Problems. In: Bélair, J. et al. (eds.) Mathematical and Computational Approaches in Advancing Modern Science and Engineering, Springer International Publishing, Switzerland, 689-700.
• 20. Pichugina O., Yakovlev S., 2016. Convex Extensions and Continuous Functional Representations in Optimization, with Their Applications. J. Coupled Syst. Multiscale Dyn. 4(2), 129–152.
• 21. Pichugina O., 2016. Surface and Combinatorial Cuttings in Euclidean Combinatorial Optimization Problems. Mathematical and computer modeling. The Series: Physics and Mathematics. 1(13), 144–160. (in Russian).
• 22. Pichugina O., 1996. The methods and algorithms for a solution of some problems of optimization on arrangements and combinations (Ph.D. dissertation). Institute for Mechanical Engineering Problems, Kharkiv, Ukraine. (in Russian).
• 23. Bertsekas D., 1999. Nonlinear Programming, 2nd edn. Belmont: Athena Scientific, 708.
• 24. Trick M., 2003. A Dynamic Programming Approach for Consistency and Propagation for Knapsack Constraints. Annals of Operations Research, 118(1–4), 73–84.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).