Otto-von-Guericke-Universität Magdeburg

 
 
 
 
 
 
 
 

12-15

A Graphical Approach to Solve an Investment Optimization Problem

E.R. Gafarov, A. Dolgui, A.A. Lazarev, F. Werner

Preprint series: 12-15 , Preprints

 MSC:

90C27 Combinatorial optimization
90C39 Dynamic programming, See also {49L20}
90C10 Integer programming
90B50 Management decision-making, including multiple objectives, See also {90A05, 90C31, 90D35}

Abstract: We consider a Project Investment problem, where a set of projects and an overall budget are given. For each project, a profit function is known which describes the profit obtained if a specific amount is invested in this project. The objective is to determine the amount invested in each project such that the overall budget is not exceeded and the total profit is maximized. For this problem, we suggest an effective graphical algorithm which improves the pseudo-polynomial time complexity of dynamic programming algorithms. Based on this graphical algorithm, we also derive a fully polynomial time approximation scheme.
In addition, we also consider the related problem of finding lot-sizes and sequencing several products on a single imperfect machine.

Keywords: Investment problem; Dynamic programming; Graphical algorithm, FPTAS

Upload: 2012-12-16-12-16

Letzte Änderung: 10.02.2016 - Ansprechpartner: Pierre Krenzlin