=Paper=
{{Paper
|id=Vol-1623/paperapp6
|storemode=property
|title=On Formulation and Software Implementation of Some Financial Management and Barter Transactions Problems
|pdfUrl=https://ceur-ws.org/Vol-1623/paperapp6.pdf
|volume=Vol-1623
|authors=Edward Gimadi,Evgenii Goncharov,Valentin Leonov
|dblpUrl=https://dblp.org/rec/conf/door/GimadiGL16
}}
==On Formulation and Software Implementation of Some Financial Management and Barter Transactions Problems==
https://ceur-ws.org/Vol-1623/paperapp6.pdf
On Formulation and Software Implementation
of Some Financial Management
and Barter Transactions Problems
Edward Kh. Gimadi1,2 , Evgenii N. Goncharov1,2⋆ , and Valentin V. Leonov1,2
1
Sobolev Institute of Mathematics, Novosibirsk, prosp. Akad. Koptyuga, 4, Russia,
2
Novosibirsk State University, Novosibirsk, str. Pirogova, 2, Russia
{gimadi,gon}@math.nsc.ru,
leonov.valentin@gmail.com
http://www.math.nsc.ru/
Abstract. The article presents some mathematical problems, reducible to the
classical search problem of minimum cost circulation in the network. We also
provide information about the software implementation of the problems on com-
puters of the latest generation. Processing time on data with 100,000 customers
and 1,000,000 transactions did not exceed 1.5 minutes.
Keywords: minimum cost network circulation, polynomial algorithm, reduc-
tion, software implementation
1 Introduction
The high level of mutual non-payments on debt obligations was one of the most serious
problems that companies encountered throughout Russia and other CIS countries in
the 90-ies years of the last century. A huge number of companies were involved into
complex schemes of credit-debt relationship. The majority of enterprises could hardly
been considered bankrupt, as long as the amount of debt that they were due matched to
the amount of debt they were attributable from other counterparties. Companies were
unable to pay off their debts until they received respective payments from their debtors.
In practice, a considerable amount of settlements were made through barter transac-
tions and transactions which involved various types of securities and their derivatives.
However, such method of payment provide significantly less flexibility, and lack of
centralized supply and distribution systems as well as undeveloped securities market
created serious difficulties in management of supply and procurement for a standalone
enterprise. Every company knows some their potential suppliers of the feedstock and
equipment as well as some direct purchasers of their end-products. However, such infor-
mation is not necessarily sufficient to organize suitable barter transactions in the face
⋆
The authors are supported by the Russian Foundation for Basic Research (project no. 16-
07-00829, 15-01-00976)
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org
714 E. Kh. Gimadi, E. N. Goncharov, V. V. Leonov
of lack of working capital. One of the possible ways for an enterprise to resolve such sit-
uation is to use complex barter schemes based on a comprehensive analysis of resource
requirements and the corresponding aggregate production capacity of enterprises.
Note that the specific problem remains quite topical at the moment, at least in a
number of former Soviet republics (Ukraine, Belarus, and others).
This article focuses on the use of mathematical models and methods for solving
research and operational problems that arise in the analysis of so-called institutional
traps: barter, non-payments, tax evasion and corruption, leading to inefficient forms of
organization of single companies and the financial system as a whole.
These problems are connected with the problems of mutual debtness of business on
one hand, as well as with performing appropriate barter transactions on the other side.
These problems include:
• the problem of maximization of repayment of debts by their directed-redistribution
(taking into account importance of a piece of debt);
• the problem of the maximization of non-monetary repayment of debts by circuit
offset method;
• the problem of optimal use of credit and financial resources for the implementation
of the largest possible matching. In addition to bounding the debt limit to each counter-
party, the aggregate amount of debt for the company can be set. Direct limit-purpose
lending of individual enterprises is allowed.
• the problem to find appropriate barter set of transactions under which compa-
nies can obtain the required resources for the production process (within enterprise’s
demand) and realise entire output (within enterprise’s capacity).
• the problem of maximization of debt offsets by utilising appropriate credit and
barter transactions (also taking into account transportation costs).
• optimisation of mutual offset and barter transactions, which account for financial
impact of the implementation of each specific operation and its priority (which could
be important for example for tax purposes).
Significant relevance of listed above fiscal infrastructure problems inspired a number
of research papers focused on obtaining adequate mathematical models of the mutual
offset and barter transactions, so as led to development of effective computational
algorithms for problem solving. We would note papers [5]–[7] which consider problem
setting which offsets mutual debts of enterprises, where functional is set as a sum of
squares of debts of enterprises remaining indebted after redistribution. Described choice
of the objective function seems to be artificial because it does not express the merits and
could be explained by the authors bias towards the method of Lagrange multipliers.
The papers [8], [9] deal with a more natural functional equal to the sum of debts
of all businesses. From a mathematical point of view, the abovementioned problem
could be trivially reduced to the problem to find an arbitrary feasible solution of the
transport problem (ie, the cost of transportation is not included). Methods proposed
in [8], [9] to resolve the derived transportation problem are already well known to the
operations research society for a long time. For example, algorithm used in [8] basicly
is a variation of the method of ”North-Western” corner. In [9] redistribution of debt
payments is made in proportion to the aggregate balance sheets of enterprises. At the
On Formulation and Software Implementation of Some Financial Management 715
same time consideration of less trivial problems by staging proposed in [8], [9] methods
do not provide a exact solution.
On the basis of works [1] – [3], which explored reduction of problems listed above
to find circulation of minimum cost, efficient (polynomial time complexity) software
was developed. Abovementioned software allows one to find the exact solution of the
problems listed above as well as to do efficient analysis and if needed manage complex
financial and commodity flows between enterprises at national, regional and enterprise
levels. In these papers authors have proposed mathematical model of debt repayment,
based on the reduction to the minimum cost circulation problem.
2 Mimimum-cost circulations problem (MCCP)
The papers [1] – [3] used a model of the Mimimum-cost circulations problem (MCCP)
in the network.
Let G = (V, U ) — a directed graph with vertex set A and the set of arcs U ⊂ V ×V .
For any function w, defined on the set of arcs, we denote by divw (x) divergence
function w in the vertex x ∈ V , is given by:
∑ ∑
divw (x) = w(u) − w(u) ,
u∈A(x) u∈B(x)
where A(x), B(x) — sets of edges in the graph G, that go from a vertex x out, and
enter into a vertex x, respectively.
The function f , defined on the arcs of the graph G = (V, U ), called the circulation
flow, or circulation, if divf (v) = 0 for every v ∈ V .
The mimimum-cost circulation problem (MCCP) on the graph G = (V, U ) can be
set as follows:
∑
minimize c(u)f (u) (1)
u∈U
subject to:
divf (v) = 0 , v ∈ V , (2)
ǎ(u) ≤ f (u) ≤ â(u), u ∈ U , (3)
where c(u) — the price of a single passage of the flow along the arc u; ǎ(u) and â(u)
— lower and upper bounds on the quantity of flow on the arc u ∈ U .
This MCCP form was formulated back by Ford and Fulkerson [4].
Extensive material on the characteristics of the implementation of effective meth-
ods MCCP solutions and comparative analysis of different algorithms, contained, for
example, in [10] – [12].
716 E. Kh. Gimadi, E. N. Goncharov, V. V. Leonov
3 Mathematical models of financial and barter operations,
reducible to MCCP
3.1 Reallocation companies debts problem
Let N = {1, . . . , n} — a set of enterprises. On the set of pairs of enterprises E =
{(i, j) | i ̸= j, 1 ≤ i, j ≤ n} functions d(e), c(e) and a(e) are given for each e = (i, j), are
equal to debt, debt unit price and the maximum permissible value of the debt company i
owes the company j respectively. It is natural to assume that d(e) ≥ 0, a(e) ≥ 0, e ∈ E.
The redistribution of debts of enterprises problem (RDEP) is formulated as follows:
for given functions d(e), c(e), a(e) find such a redistribution of debt f (e), which
minimizes the functional ∑
c(e)f (e)
e∈E
under the following conditions:
• divergence functions d and f are the same:
divf (x) = divd (x), x ∈ N ;
• fulfilled restrictions on the value of debts:
0 ≤ f (e) ≤ a(e), e ∈ E .
Proposition 1. [1]-[3] The redistribution of debts of enterprises problem is reduced to
the MCCP (1)–(3).
3.2 The problem of appropriate credit to pay off debts of enterprises
Let N = {1, . . . , n} — a set of enterprises, and A ⊂ E = {(i, j) | i ̸= j, 1 ≤ i, j ≤ n}
— a subset of pairs (i, j), on which debt dij of enterprise i to enterprise j are given.
We also know the value of the total loan Q, provided by enterprises to repay debt.
Initially, the company i ∈ N has negative balance at divd (i) > 0 and surplus at
divd (i) < 0.
For each company i ∈ N , in principle, the opportunity to obtain a private loan qi0 of
the total (all enterprises) credit the amount of Q0 and the target credit qi , 0 ≤ qi ≤ Qi
(intended only for the enterprise), and as a result of further settlements some amount
of pi may be on “cash” account of the enterprise i.
Expedient lending problem (ELP) is set to find a system of payments (fij ), lending
(qi0 ) and (qi ), as well as “pure” returns debt pi , which minimizes the total value of the
remaining debt (accounting for loans granted):
∑
n ∑
(qj0 + qj ) + (dij − fij )
j=1 (i,j)∈A
On Formulation and Software Implementation of Some Financial Management 717
subject to:
• amount of the total credit of the consumed resource does not exceed the total
limit of the resource:
∑n
qj0 ≤ Q0 , qj0 ≥ 0, j ∈ N ;
j=1
• for each enterprise i value of the consumed credit does not exceed the specified
limit of this resource:
0 ≤ qi ≤ Qi , i ∈ N :
• and payment of the enterprise i to the enterprise j does not exceed the value of
its debt:
0 ≤ fij ≤ dij , (i, j) ∈ A;
• the total amount of funds coming to the enterprise in the form of loans and
payments from other companies, is equal to the amount of money left on “cash” account
of the enterprise and its payments to creditors:
∑ ∑
qi0 + qi + fji = pi + fij , i ∈ N.
j∈B(i) j∈A(i)
Here are some features of ELP (see [3]).
1) The amount of money received for “cash” accounts, equal to the amount of loans
received by enterprises
∑ ∑
(qi0 + qi ) = pi .
i∈N i∈N
2) For optimal solution ELP the following conclusions are valid
qi0 + qi > 0 ⇒ pi = 0, pi > 0 ⇒ qi0 + qi = 0.
3) For the optimal solution of ELP for every enterprise j with the initial value of the
surplus received loans – following sum qj0 + qj is equal to 0.
4) For the optimal solution of ELP for every enterprise i with initially negative balance
value of the available balance pi is equal to 0.
Proposition 2. [1]-[3] Expedient lending problem is reduced to the MCCP (1)–(3).
Two fictitious vertices i01 , i02 and the arc (i01 , i02 ) between them, as well as fictitious
arcs (i01 , i) are introduced to account for the reduction of total lending (to all vertices
with a negative balance) and (i, i02 ) of all vertices with a positive balance. The capacity
of these arcs to be equal to Q0 .
To account for lending for each vertex i (negative balance) is entered duplicate to
its fictitious company i′ with arc (i′ , i), as well as fictitious arcs (j, i′ ) of each vertex j
with surplus. Capacity of these arcs are equal to the values of Qi .
718 E. Kh. Gimadi, E. N. Goncharov, V. V. Leonov
3.3 Expedient barter problem
Let N = {1, . . . , n} — a set of enterprises, R = {1, . . . , m} — a set of types of goods
(resources), produced and / or consumed by the enterprises from the set N . In the
future, we will not distinguish between “goods” and “resource” as the same product
(service) may act as a resource for one enterprise, and as produced goods for another.
For each enterprise i ∈ N and goods r ∈ R values sir ≥ 0 and pri ≥ 0 are sets, which
are equal to the volume of supply and demand (calculated in terms of value). Without
loss of generality we can assume that sri pri = 0 for all i ∈ N and r ∈ R. The substantial
meaning of this condition lies in the fact that no enterprise can be both a supplier and
a buyer of the same goods.
Under the scheme (graph) of the commodity exchange we shall mean the set of
r
values of fij ≥ 0, i, j ∈ N , r ∈ R. The value of fij
r
equal to the volume (by value) of the
goods r, which is transmitted from the enterprise i to the enterprise j. Furthermore, we
r r
assume that fij fji = 0, i.e there are no counter deliveries of the same goods between a
pair of enterprises.
The problem to find expedient barter (PFEB): for given values of sri and pri to find
r
a barter scheme (fij ), which would maximize the total volume of barter transactions:
∑ ∑
r
fij (4)
(i,j)∈N ×N r∈R
subject to: • the total volume of goods r, now transferred i, must not exceed its
capacity, t. e. for any r ∈ R, i ∈ N
∑
r
fij ≤ pri ; (5)
j∈N
• the total volume of goods r, now received j, should not exceed the requirements
of the latter, i.e. for any r ∈ R, j ∈ N
∑
r
fij ≤ srj ; (6)
i∈N
• the total amount of goods purchased by enterprise, equal to the total volume of
goods sold by this company, i.e. for any i ∈ N
∑∑ ∑∑
r r
fji = fij . (7)
r∈R j∈N r∈R j∈N
The following statement holds
Proposition 3. [1]-[3] PFEB is reduced to the MCCP (1)–(3).
3.4 The problem of debt repayment to the use of barter transactions
Suppose that in addition to the original definition of PFEB, described in the previous
section, for each pair of enterprises (i, j) ∈ N × N the value of dij ≥ 0 is given, which
On Formulation and Software Implementation of Some Financial Management 719
characterizes the debts from enterprise i to enterprise j. Without loss of generality we
can assume that dij · dji = 0 for any i, j ∈ N .
r
Along with the values of fij ≥ 0 (i, j ∈ N , r ∈ R), equal to the volume (by value)
of the goods r, transmitted from the enterprise i to the enterprise j, we introduce the
value of fij ≥ 0, i, j ∈ N . The value of fij is defined as the payment for debt which
the enterprise i received from the enterprise j.
Under the graph (scheme) of commodity exchange, allowable under the repayment
r
of debt problems, we mean a set of values (fij , fij ), satisfying the following conditions:
• the total volume of goods r, transferred i, must not exceed its capacity, ie for all
r ∈ R, i ∈ N ∑
r
fij ≤ pri ; (8)
j∈N
• the total volume of goods r, received j, should not exceed the requirements of
the latter, ie. for any r ∈ R, j ∈ N
∑
r
fij ≤ srj ; (9)
i∈N
• the sum of the volume of goods, purchased by the enterprise, and debt, credited
his creditors, is the sum of the volumes, implemented by the enterprise of goods and
debt, credited his debtors, t.e., for any i ∈ N
∑∑ ∑ ∑∑ ∑
r r
fji + fji = fij + fij ; (10)
r∈R j∈N j∈N r∈R j∈N j∈N
• amount of debt, counted i to enterprise j, should not exceed the value of the
debt enterprise j to enterprise i, ie for any i ∈ N , j ∈ N
fij ≤ dji . (11)
Suppose also non-negative values of α, β ≥ 0 are given, meaning of which will be
explained later.
The problem of maximum debt repayment using barter transactions (PDR) can be
formulated as follows: for given values of α, β, sri , pri dij to find a barter scheme
r
(fij , fij ), which would maximize the weighted sum of the volume of barter transactions
and offsets:
∑∑∑ ∑∑
r
α fij +β fij , (12)
r∈R i∈N j∈N i∈N j∈N
when performing limited tasks purposeful exchange of goods (see Section 4).
Coefficients α and β reflect the degree of importance (priority) of barter and credit
operations respectively. In particular, by putting α = 0, we get the problem to find the
maximum repayment of debts using barter transactions. The case β = 0 corresponds
to the problem of maximizing the total volume of barter transactions. (Note that even
in this case, the PDR is not equivalent to the previously discussed PFEB, since the
presence of additional connections corresponding to the debt relationship, expanding
the set of feasible options for barter).
720 E. Kh. Gimadi, E. N. Goncharov, V. V. Leonov
Proposition 4. [1]-[3] PDR is reduced to the MCCP (1)–(3).
Comment. Reducibility to MCCP problem persists in case of weighted objective
functions (described in the last two paragraphs), where the value of flows of the respec-
tive arcs (relations) are multiplied by predetermined factors assigned to such relations.
For such factors one can use (depending on the definition of the problem), the price
of the units of flow along the connection, interest tax deductions, the priority of the
operation of this connection, etc.
4 Software implementation
Based on the models proposed above, authors developed software, allowing for com-
putational solving of the real problems of mutual offset of debts by enterprises using
the barter transactions. The algorithm was coded in C ++ in Visual Studio system,
all experiments were carried out on a PC with a 1.7 GHz CPU and 2 Gb RAM with
Windows 7 operating system.
To demonstrate capabilities of the algorithm, we conducted a series of numerical
experiments. Test instances were created as follows. We set a number of clients (enter-
prises), and randomly create a list of transactions. The payor and the recipient of the
bank transfer are selected randomly and equiprobably from the list, payment amount
is selected with equal probable distribution out of range (100, 500000). Amount at-
tributed to financing of the project is assigned as 0.01 of the sum of all transactions.
The results of test experiments are presented in the table below.
Table 1.
Problems Offset cashless (%)
found cycles Processing
clients transactions total with credit time (sec)
100 1,000 799 80.5 11.3 0.03
1,000 10,000 7871 79.0 25.4 0.25
1,000 100,000 95472 94.3 10.4 2.67
10,000 100,000 77921 77.8 43.4 2.88
10,000 500,000 467489 91.8 22.7 15.4
10,000 1,000,000 956644 94.3 15.2 39.1
50,000 1,000,000 1608960 80.8 14.0 84.0
100,000 1,000,000 1559519 74.6 21.9 94.4
For each of the generated instances we show in the table the number of cycles found;
the share of transactions that were offset cashless relative to the total amount of all
transactions, including the share of transactions that were offset on the back of use
of credit; processing time. As we can see from the table, lending, if allowed, yielded
tangible results: one credit led to increase in total amount of offset transactions in the
range of 10 to almost 50.
On Formulation and Software Implementation of Some Financial Management 721
The current version of the software allows one to receive solution of the problem,
containing tens of thousands of customers and millions connections (debts) between
them. Such dimension corresponds to the average number of enterprises in a large
region or even in an area. Unfortunately, at the present time the authors do not have
the real data set of similar size to try the algorithm.
Processes of reduction to the MCCP problem that were considered in the models
above, as well as processes of subsequent retrieval of solutions of the original problems
are structural. It means that the user is allowed to enter some information in hard num-
bers. For numerical experiment authors use real raw data provided by the Krasnoyarsk
Chamber of Accounts. Data contained approximately 1,000 clients and approximately
10,000 bank transactions. Processing time was 0.1 seconds.
The software developed by the authors was used in the National Bank of the Repub-
lic Buryatia (Ulan-Ude), JSCB ”Kuzbassprombank” (Kemerovo), Krasnoyarsk Cham-
ber of Accounts and APSB ”Omskpromstroybank”. We believe that wider adoption of
the software is constrained by the complexity of gathering the necessary input data
and the lack of legislation for cashless offset between counterparties in Russia.
It is worth noting that the developed software provides one-stop shop for getting
instant optimum solutions for problems of mutual debts repayment, provided that
there is sufficient information on the requirements of customers — both debtors and
creditors. To build such database is a standalone problem, which could be resolved
by joint efforts of regional administration, banks, tax authority and potentially law
enforcement agencies only.
Positive experience of automated cashless offsets is recorded since April 1994, in the
Republic of Buryatia, where JSC “ Bikombank ” (Buryat Innovation Commercial Bank)
on a regular basis (twice a month) executed matching of debts between various enter-
prises within the region. Altai region has experience of creating a database to address
the problem of non-payment: regional state committee of the Statistics has created the
system of data collection and subsequent computations for cashless repayment of ar-
rears (see “Finance magazine Siberia”, 3/17, 1995). The software package developed in
the Sobolev Institute of Mathematics, was shared in the past with Tveruniversalbank,
the National Bank of the Republic of Buryatia, AKB ”Kuzbassprombank” (Kemerovo)
and the Chamber of Account of the Sakha Republic.
It is valuable that calculations can be carried out virtually in real time, which is
very important in a rapidly changing market sentiment. For example, a conventional
personal computer can solve the maximum cashless offset problem while optimising
use of credit resources (with tens of thousands customers and hundreds of thousands
connections between them) for a time within few minutes. On a number of particular
customary data sets it turned out that each unit of credit resources leads to redemption
of six to eight units of the debt.
Authors believe that another topical problem at the moment is optimization of
barter transactions, whereas different market agents in both groups of sellers (pro-
ducers) and buyers have different prices for the same goods. The mathematical model
implemented for this problem also uses (as a base), minimum cost circulation problem.
722 E. Kh. Gimadi, E. N. Goncharov, V. V. Leonov
5 Conclusion
The article presents some mathematical problems reducible to the classical problem to
find in the circulation flow of minimum cost in a network. Computation output that
was processed on a latest generation computer is provided. Processing time on data
with 100,000 customers and 1,000,000 transactions did not exceed 1.5 minutes.
References
1. Gimadi E.Kh.: Mathematics can help practitioners. An article in the newspaper Business
News (Moscow-news), 7 december 1994. (in russian)
2. Gimadi E.Kh., Glebov N.I., Zalyubovski V.V.: On some problems of repayment of mutual
debts of the enterprises. Diskretnyi analiz i issledovanie operacij, ser. 2, 4(1), 30–39 (1997).
(in russian)
3. Gimadi E.Kh., Glebov N.I., Zalyubovski V.V.: On expedient barter problems. Diskretnyi
analiz i issledovanie operacij, ser. 2, 5(1), 3–11 (1998). (in russian)
4. Ford L.R., and Fulkerson D.R.: Flows in Networks. Princeton University Press, Princeton,
N. J. (1962).
5. Kalitkin N.N.: Optimum mutual debts. Matematicheskoe modelirovanie 7(1), 11–21 (1995).
(in russian)
6. Kalitkin N.N.: Letting the offset of mutual debts of enterprises. Doklady AN 343(1),12–14
(1995). (in russian)
7. Kalitkin N.N., Kuzmina L.V.: On offset of mutual debts of the enterprises. Matematicheskoe
modelirovanie 7(4), 64–72 (1995). (in russian)
8. Kalitkin N.N., Mirhailov A.P.: The ideal solution to the problem of set-off of mutual debts.
Matematicheskoe modelirovanie 7(6), 111–117 (1995). (in russian)
9. Ciciashvili G.Sh.: The solution of the problem of settlement of mutual debts.
Dal’nevostochnyi manematicheskiy sbornik 1, 126–131 (1995). (in russian)
10. Goldberg A.V., Tarjan R.E.: Finding mimimum-cost circulations by cancelling negative
cycles. J. Assoc. Comput. Mach. 36(4), 873-886 (1989).
11. Goldberg A.V., Tarjan R.E.: Finding mimimum-cost circulations by successive approxi-
mation. Math. of Oper. Res. 15(3), 430-466 (1990).
12. Johnson D.S., McGeoch C.C. (eds.): Network flows and matching: first DIMACS imple-
mentation challenge (DIMACS series in discrete mathematics and theoretical computer
science 12, AMS, (1993).