A Graphical Approach to Solve an Investment Optimization Problem

Abstract : We consider a project investment problem, where a set of projects and an overall budget are given. For each project, a piecewise linear profit function is known which describes the profit obtained if a specific amount is invested into this project. The objective is to determine the amount invested into each project such that the overall budget is not exceeded and the total profit is maximized. For this problem, a graphical algorithm (GrA) is presented which is based on the same Bellman equations as the best known dynamic programming algorithm (DPA) but the GrA has several advantages in comparison with the DPA. Based on this GrA, a fully-polynomial time approximation scheme is proposed having the best known running time. The idea of the GrA presented can also be used to solve some similar scheduling or lot-sizing problems in a more effective way, e.g., the related problem of finding lot-sizes and sequencing several products on a single imperfect machine.
Type de document :
Article dans une revue
Journal of Mathematical Modelling and Algorithms in Operations Research, Springer Netherlands, 2014, 〈10.1007/s10852-013-9248-2〉
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00926121
Contributeur : Florent Breuil <>
Soumis le : jeudi 9 janvier 2014 - 10:28:44
Dernière modification le : dimanche 28 janvier 2018 - 15:22:05

Identifiants

Citation

Evgeny R. Gafarov, Alexandre Dolgui, Alexander Lazarev, Frank Werner. A Graphical Approach to Solve an Investment Optimization Problem. Journal of Mathematical Modelling and Algorithms in Operations Research, Springer Netherlands, 2014, 〈10.1007/s10852-013-9248-2〉. 〈emse-00926121〉

Partager

Métriques

Consultations de la notice

320