Microsoft Word - Issue-1_Vol-10.docx
101
Dynamic Programming and Greedy Algorithm Strategy for Solving Several
Classes of Graph Optimization Problems
Manana Chumburidze
Akaki Tsereteli State University
4600, Georgia, Kutaisi, 59 Tamar Mephe St.
Phone: (+995 431) 24 00 36
maminachumb02@gmail.com
Irakli Basheleishvili
Akaki Tsereteli State University
4600, Georgia, Kutaisi, 59 Tamar Mephe St.
Phone: (+995 431) 24 00 36
basheleishvili.irakli@gmail.com
Anano Khetsuriani
Akaki Tsereteli State University
4600, Georgia, Kutaisi, 59 Tamar Mephe St.
Phone: (+995 431) 24 00 36
anano.khecuriani@yahoo.com
Abstract
This article is devoted to the development of the scientific methods of dynamic programming
and greedy algorithms to expose the software of innovation methods of mathematical and
computational approaches in advancing modern science and teaching. The tools applied in this
development are based on the graph theory, generalized approximate dynamical programming
method and greedy algorithms. The results are presented on both the fundamental and applied level.
Keywords: Dynamic Programming; Greedy Algorithm; Graph; Optimization.
1. Introduction
The optimization problem in modern business belongs to the most general task of
mathematical optimization problems. In our investigation solving this problem with general
mathematical methodology and powerful algorithms as a way of furthering our interdisciplinary
approach in research and teaching proceedings is considered.
In this work, optimization problems for financial investment and supply management of a
company, as a particular example, are considered. Planning Software to solve complex conservation
planning problems in financial investment is delivered. Investigations include the following stages
of sub-problems:
Statement optimization problems for financial investment of business-company (FIC)
Description how graph theory can be utilized as a representation language of building
information models and implementation of basic concepts in a wide range of models of
business processing.
Construct the corresponding graphs of FIC
Investigation of basic solve strategies of FIC
Investigation of greedy algorithm strategy with respect to problems FIC
Justify of numerical approximation
Implementation of program code for the optimization problem.
2. Notations and Definitive Concepts
This paper deals with the problem of optimal allocation of financial resources of the
company, modeled with the use of directed graph-diagrams.
BRAIN – Broad Research in Artificial Intelligence and Neuroscience
Volume 10, Issue 1 (January - February, 2019), ISSN 2067-3957
102
One of the features of the modern economy is dynamism on each level of management. It
defines the realization of different flows of goods and services, involves the movement and storage
of raw materials during planning.
The dynamic process must be balanced and optimal. The research of this problem makes the
construction of a corresponding mathematical model necessary, because only through computer
simulation we can determine optimal variant of the management of relevant flows of finance or
goods in proper time so that they are reflected in the business plans of the company.
We know many papers on the issues of optimal allocation of financial resources, using
appropriate optimization methods, including (Jeremy, 2012) But little work is devoted to the
construction of optimal management system in the graphs.
The problem of optimal management of investments relates to the problems of dynamic
programming (Sniedovich, 2010). In the methods of dynamic programming, the initial Information
is based on the consideration that in the model the real challenges are: Objective; Constraint
condition; Parameters of management.
Solutions of the problems occur by the method of dividing the investment operations into the
multi-stage recursive procedures. Profit during the entire operation is achieved from a sequence of
profit at each stage separately.
The problem of optimal resources management is from a class of the additional tasks. In this
paper, we address several constrained optimization problems (financial investment, supply
management) by using the multistage graph modeling method (Berge ,1962), because the graph is a
particular way for visualization of the storing and organizing dates of the investments and
corresponding profits.
We have constructed the Software Planning (SP) used to manage all types of resources and
find the algorithm of greedy strategy use tool- optimizer to obtain the best results of solutions.
3. Statement Problem
In this work, we have considered practical problems of optimal management of resources of
a company to find the tour of investing projects to obtain the best available benefit given in the
defined financial domain.
Let us consider the mathematical formulation of the problem, thus we introduce the
following notations:
𝐶 = (𝐶 ) - the matrix of initial values of projects investment in the company, 𝑅 = (𝑅 ) - the
matrix of the value of corresponding benefits (i=1,..,n; j=1,..,m), S- total sum invests of projects,
n- number of the company, m-number of projects, 𝑋 = (𝑋 ) - the matrix of selected projects
where
𝑋 =
1, 𝑖𝑓 𝑝𝑟𝑜𝑗𝑒𝑐𝑡 𝑖𝑠 𝑠𝑒𝑙𝑒𝑐𝑡𝑒𝑑
0 , 𝑖𝑓 𝑝𝑟𝑜𝑗𝑒𝑐𝑡 𝑖𝑠 𝑛𝑡 𝑠𝑒𝑙𝑒𝑐𝑡𝑒𝑑
Problem. It is required to construct – the matrix of optimal plan of investment in the company -
𝑋 = (𝑋 ) satisfy the following conditions:
Constraint conditions:
∑ ∑ (𝐶 ∗ 𝑋 ) ≤ 𝑆 (1)
Criteria of optimization:
∑ ∑ (𝑅 ∗ 𝑋 ) → 𝑚𝑎𝑥 (2)
Let us consider modeling proceedings of this problem.
M. Chumburidze, I. Basheleishvili, A. Khetsuriani - Dynamic Programming and Greedy Algorithm Strategy for Solving
Several Classes of Graph Optimization Problems
103
For the simplest case, we have considered the solution of the problem for the following
particular case when n=3, m=4 and S=5. Data value of initial investment of projects are presented in
table 1.
Table 1. Data value of initial investment
Project Company I Company II Company III
# Invest- C1j Profit-R1j Invest-C2j Profit-R2j Invest-C2j Profit-R2j
1 0 0 0 0 0 0
2 1 5 2 8 1 3
3 2 6 3 9 1 3
4 2 6 4 12 1 3
The multi-stage graph of management investment of projects in the company, corresponding
the dates of the table are constructed and has the following form (look pic.1):
SP program maintenance enables us to define the effective version of management of proper
financial flows by using a visual diagram on each level of investment and find the optimal solution.
The software performs the following procedures by using the corresponding tools:
To construct the table of date, for the particular value (table 1.)
To construct the multistage graph, corresponding the dates of table1. (look figure 1.)
Figure 1. Directed graph of investment
Where Pj (j=0, 1, 2, 3) designates the stage financial process for given projects of the
company.
The vertex (Vjk , where j is the number of the stage) of the graph are used for storing the sum
invests of the given stage (from the beginning to the end):
V2k= V1k+ C2k ; V31=5= V2k+ C3k ; k=0..5;
The nodes 0 and 5 are terminal points: 0 (only variant) defines the initial position of the
system, 5 (only variant) are used for stored constraint condition.
The edges of graphs are labeled by the benefits of the corresponding stage of investing plan
accordingly to table 1.
BRAIN – Broad Research in Artificial Intelligence and Neuroscience
Volume 10, Issue 1 (January - February, 2019), ISSN 2067-3957
104
For example, the label of vertex, which connects V24 of P2 column to connect V31 of P3
column is labeled by the benefit -3mln corresponding the investment-1mln of the third stage.
4. Problem Solution
We will consider the dynamical process of investment. The solution of complex problems is
based on breaking them down into simpler substructures:
In the first stage the financial resources for the first company is invested, there are the six
possible ways of investment between 0 flow-of- investment and 5 flow-of- investment (look
at vertex of the column P1 of graph), in the nodes the column P1(first stage) the date of initial
investment of first stages is stored.
In the second stage, the rest of the financial resource of the company is invested. There are
the six possible ways of investment, in the nodes of column P2 (second stage) the sum
invested together with the first and second stages are stored.
In the third stage, the rest of the financial resources for the company is invested. There is the
only variant of investment, according to the methods of dynamic programming, in the
terminal node of column P3 (third – final stage) the total sum of investment (from the
beginning to the end) is stored and receives a value of financial constraints-5mln.
The solution model according to the method of the dynamic programming is considered
from the terminal node of column P3 before the initial node the column P0 of the graph.
There are six possible ways of conditional optimal profit between P2 and P3 (look graph-
diagram), for example, one of them the way 1 - 5 defined in P2 put in 1 million (mln) investment
and in P3 put in 4mln investment, then 3mln. conditional optimal profit is given. Analogically may
be considered the conditional optimal profit between P1 and P2, there are six possible ways too
(look graph-diagram), for example:
0 →0+15=15;
1→5+12=17;
2→6+11=17;
3→6+8=14;
4→6+3=9;
5→6+0=6.
One of them: the way 1 – 4 defined in P1 put in 1mln investment and in P2 put in 3mln
investment, then 3mln conditional optimal profit are given (9+3=12). For column P0-initial node
(only variant) there are six possible ways of conditional optimal profit between P0 and P1.
After considering all tour investing projects, the best profit -17mln is chosen. There are 3 tours of
optimal plan investment:
TOUR(T1): 0→1→ 4 →5 defined, that in P1 put 1mln., in P2 put 3mln. and in P3 put 1 mln.,
accordingly to (1) and (2) elements of the matrix selected projects get the values:
X21 =1 X32 = X23 = 1;
X11 = X31 = X41 = X12 = X22 = X42 = X13 = X33 = X43 = 0.
COST (T1) =5+9+3=17
TOUR(T2): 0→1→ 5→5 defined, that in P1 put 1mln., in P2 put 4mln. and in P3 put 0 mln.,
accordingly to (1) and (2) elements of the matrix selected projects get the values:
X21 = X42 = 1;
X11 = X31 = X41 = X12 = X22 = X32 = X13 = X23 = X33 = X43 = 0.
COST (T2) =5+12+0=17
TOUR(T3): 0 → 2 → 4 →5 defined, that in P1 put 2mln., in P2 put 2mln. and in P3 put
1mln., accordingly to (1) and (2) elements of the matrix selected projects get the values:
M. Chumburidze, I. Basheleishvili, A. Khetsuriani - Dynamic Programming and Greedy Algorithm Strategy for Solving
Several Classes of Graph Optimization Problems
105
X31 = X22 = X23 = 1;
X11 = X21 = X41 = X12 = X32 = X42 = X13 = X33 = X43 = 0.
COST (T3) = 6+8+3=17
This method is based on considering all the ways to invest all alternative projects for
choosing the best profit and is called “consider all plans for selecting optimal value " but the
obtained result is not achieved in reasonable time. The “dark color “indicates the tour of an
approximate optimal plan of the investment project.
The pseudo code of dynamic method has the form:
Pseudo code - dynamic method ( )
{
List paths;
List Profit;
for each path in GraphPaths (StartVertex, EndVertex)
{
PathProfit =0;
for (i=0; i<path.Verterxs.count-1; i++)
{
PathProfit = PathProfit +
(path[i], path[i+1]).Weight –
(path.Vertexs[i+1].Label- path.Vertexs[i].Label)
}
Profit.add(PathProfit)
paths.add(path)
}
MaxProfit= Profit.item[0];
pathindex=0;
for (j=0;j< Profit.item.count; j++)
{
if(MaxProfit< Profit.item[j])
{
MaxProfit= Profit.item[j];
pathindex=j;
}
}
print(path[pathindex], “›” ,MaxProfit )
}
Greedy algorithms (Bang-Jensen, 2004) look for simple, easy-to-implement solutions to
complex, multi-step problems by deciding which next step will provide the most obvious benefit. A
greedy strategy does not produce an optimal solution in general, but nonetheless, a greedy heuristic
may locally yield to the optimal solutions that approximate a global optimal solution in a reasonable
time.
Greedy answer: 5+12+0=17
Accordingly of (1) and (2) elements of the matrix selected projects get the values:
X21 = X42 = 1;
X11 = X31 = X41 = X12 = X22 = X32 = X13 =X23 = X33 = X43 = 0
BRAIN – Broad Research in Artificial Intelligence and Neuroscience
Volume 10, Issue 1 (January - February, 2019), ISSN 2067-3957
106
The pseudo code for greedy algorithm has the form:
Pseudo code- greedy ()
{
O[m], I[m]
CurentVertex=StartVertex
for (i=1; i<m;i++)
{
for each v in Adj[CurentVertex]
{
if ( IsMax( (CurentVertex, v ).Weight-(v.label-
CurentVertex.label)) in (CurentVertex, Adj [CurentVertex])
)
{
I[i]=v.label-I[i-1];
O[i]=(CurentVertex, v).Wight;
CurentVertex=v;
}
}
}
for (i=1; i<m;i++)
{
print(I[i],” ›”,O[i])
}
}
5. Conclusion
In this work, dynamic programming and greedy algorithm strategy for solving optimization
problems of FIC models are investigated. The particular example of financial investment companies
is considered and a corresponding multistage graph has been constructed. Approximation
algorithms, which solved multistage problems, have been delivered.
It is important to mention that similarly to investment management, this program is able to
address supply management and other logistic problems.
References
Bang-Jensen, J., Gutin, G., & Yeo, A. (2004). When the greedy algorithm fails. Discrete
Optimization, 1(2), 121-127.
Barron, A. R., Cohen, A., Dahmen, W., & DeVore, R. A. (2008). Approximation and learning by
greedy algorithms. The annals of statistics, 36(1), 64-94.
Basheleishvili, I. (2018). The Algorithm of Selection and Functions Distribution of Multifunctional
Personnel-Case when the Number of Functions is Greater than the Number of Personnel.
Journal of Technical Science and Technologies, 6(2).
Bendall, G., & Margot, F. (2006). Greedy-type resistance of combinatorial problems. Discrete
Optimization, 3(4), 288-298.
Berge C.( 1962.)The Theory of Graphs and its Applications, Wiley, N.Y.
Chumburidze, M., & Lekveishvili, D. (2014). Approximate Solution of Some Mixed Boundary
Value Problems of the Generalized Theory of Couple-Stress Thermo-Elasticity. World
Academy of Science, engineering and Technology, 6(28), 161-163.
Korte, B., & Lovász, L. (1981, August). Mathematical structures underlying greedy algorithms. In
International Conference on Fundamentals of Computation Theory (pp. 205-209). Springer,
Berlin, Heidelberg.
Sniedovich, M. (2010). Dynamic programming: foundations and principles. CRC press.
Stein, J. C. (1997). Internal capital markets and the competition for corporate resources. The Journal
of Finance, 52(1), 111-133.
M. Chumburidze, I. Basheleishvili, A. Khetsuriani - Dynamic Programming and Greedy Algorithm Strategy for Solving
Several Classes of Graph Optimization Problems
107
Manana Chumburidze has obtained PhD degree in Mathematics sciences in Ivane Javakhishvili
Tbilisi State University of Georgia in 1999. She is Associate Professor of
Department Computer Sciences at Akaki Tsereteli State University of Georgia. She
is membership of The American Society of Mechanical Engineers (ASME) and
member of the Scientific and Technical Committee of Editorial Review Board on
Mechanics and Computational Sciences in the WASET (World Academy of
Science, Engineering and Technology) organization of USA. His research interests
include: Computer Sciences, Applied Mathematics.
Irakli Basheleishvili (b. March 27, 1991) received his Bachelor degree in Computer Sciences
(2012), Master degree in Computer Science (2014), PhD in Computer Science
(2017). Now he is lecturer in Department of Computer Technology, Faculty of
Exact and Natural Sciences, Akaki Tsereteli State University of Georgia. His
research interests include: Software Engineering, Databases, Information
Technologies in Human Resources Management, Algorithms, Information
Systems, Decision Support Systems, Mathematical Optimization Methods. He has
authored 2 books and more than 15 papers, more than 10 International conferences
participation.
Anano Khetsuriani, Master student of computer sciences. In 2016 he was
awarded the BCs of Business Administration; Mainor education program:
International Relations.