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 computers of the latest generation. Processing time on data with 100,000 customers and 1,000,000 transactions did not exceed 1.5 minutes. 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 transactions and transactions which involved various types of securities and their derivatives. However, such method of payment provide signi cantly less exibility, 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 information 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. 1607-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
of lack of working capital. One of the possible ways for an enterprise to resolve such situation 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 speci c 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 nancial 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 nancial resources for the implementation of the largest possible matching. In addition to bounding the debt limit to each counterparty, the aggregate amount of debt for the company can be set. Direct limit-purpose lending of individual enterprises is allowed.
the problem to nd appropriate barter set of transactions under which companies 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 nancial impact of the implementation of each speci c operation and its priority (which could be important for example for tax purposes).
Signi cant relevance of listed above scal 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 [
On the basis of works [
The papers [
Let G = (V; U ) | a directed graph with vertex set A and the set of arcs U V V .
For any function w, de ned on the set of arcs, we denote by divw(x) divergence function w in the vertex x 2 V , is given by: divw(x) =
∑ u2A(x) w(u)
∑ u2B(x) w(u) ; 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 , de ned on the arcs of the graph G = (V; U ), called the circulation ow, or circulation, if divf (v) = 0 for every v 2 V .
The mimimum-cost circulation problem (MCCP) on the graph G = (V; U ) can be set as follows: subject to: minimize ∑ c(u)f (u) u2U divf (v) = 0 ; v 2 V ; a(u) f (u) a^(u); u 2 U ; (1) (2) (3) where c(u) | the price of a single passage of the ow along the arc u; a(u) and a^(u) | lower and upper bounds on the quantity of ow on the arc u 2 U .
This MCCP form was formulated back by Ford and Fulkerson [
Extensive material on the characteristics of the implementation of effective
methods MCCP solutions and comparative analysis of different algorithms, contained, for
example, in [
3.1
Reallocation companies debts problem Let N = f1; : : : ; ng | a set of enterprises. On the set of pairs of enterprises E = f(i; j) j i ̸= j; 1 i; j ng 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 2 E.
The redistribution of debts of enterprises problem (RDEP) is formulated as follows: for given functions d(e), c(e), a(e) nd such a redistribution of debt f (e), which minimizes the functional under the following conditions: divergence functions d and f are the same: ful lled restrictions on the value of debts: ∑ c(e)f (e) e2E divf (x) = divd(x); x 2 N ; 0 f (e)
a(e); e 2 E :
Proposition 1. [
The problem of appropriate credit to pay off debts of enterprises Let N = f1; : : : ; ng | a set of enterprises, and A E = f(i; j) j i ̸= j; 1 i; j ng | 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 2 N has negative balance at divd(i) > 0 and surplus at divd(i) < 0.
For each company i 2 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 nd 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 ) + j=1
∑ (dij (i;j)2A fij ) subject to:
amount of the total credit of the consumed resource does not exceed the total limit of the resource:
and payment of the enterprise i to the enterprise j does not exceed the value of its debt:
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 +
∑ j2B(i) fji = pi + ∑ fij ; i 2 N: j2A(i)
Here are some features of ELP (see [
∑ pi: i2N i2N 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. [
Two ctitious vertices i01; i02 and the arc (i01; i02) between them, as well as ctitious 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 ctitious company i′ with arc (i′; i), as well as ctitious arcs (j; i′) of each vertex j with surplus. Capacity of these arcs are equal to the values of Qi.
Expedient barter problem Let N = f1; : : : ; ng | a set of enterprises, R = f1; : : : ; mg | 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 2 N and goods r 2 R values sir 0 and pir 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 sirpir = 0 for all i 2 N and r 2 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 values of firj 0, i; j 2 N , r 2 R. The value of firj equal to the volume (by value) of the goods r, which is transmitted from the enterprise i to the enterprise j. Furthermore, we assume that firj fjri = 0, i.e there are no counter deliveries of the same goods between a pair of enterprises.
The problem to nd expedient barter (PFEB): for given values of sir and pir to nd a barter scheme (firj ), which would maximize the total volume of barter transactions: ∑ subject to: the total volume of goods r, now transferred i, must not exceed its capacity, t. e. for any r 2 R, i 2 N
the total volume of goods r, now received j, should not exceed the requirements of the latter, i.e. for any r 2 R, j 2 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 2 N ∑ ∑ fjri = ∑
∑ firj : Suppose that in addition to the original de nition of PFEB, described in the previous section, for each pair of enterprises (i; j) 2 N N the value of dij 0 is given, which (4) (5) (6) (7) characterizes the debts from enterprise i to enterprise j. Without loss of generality we can assume that dij dji = 0 for any i; j 2 N .
Along with the values of firj 0 (i; j 2 N , r 2 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 2 N . The value of fij is de ned 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 of debt problems, we mean a set of values (firj ; fij ), satisfying the following conditions: the total volume of goods r, transferred i, must not exceed its capacity, ie for all r 2 R, i 2 N
the total volume of goods r, received j, should not exceed the requirements of the latter, ie. for any r 2 R, j 2 N ∑ fij
r pir ; sjr ; 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 2 N ∑ ∑ fjri + ∑ fji = ∑ ∑ firj +
∑ fij ;
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 ; ; sir, pir dij to nd a barter scheme (firj ; fij ), which would maximize the weighted sum of the volume of barter transactions and offsets: ∑ ∑
∑ firj + r2R i2N j2N ∑
∑ fij ; i2N j2N (12) when performing limited tasks purposeful exchange of goods (see Section 4).
Coefficients and re ect the degree of importance (priority) of barter and credit
operations respectively. In particular, by putting = 0, we get the problem to nd 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).
Proposition 4. [
Comment. Reducibility to MCCP problem persists in case of weighted objective functions (described in the last two paragraphs), where the value of ows of the respective arcs (relations) are multiplied by predetermined factors assigned to such relations. For such factors one can use (depending on the de nition of the problem), the price of the units of ow along the connection, interest tax deductions, the priority of the operation of this connection, etc. 4
Based on the models proposed above, authors developed software, allowing for computational 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 (enterprises), 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 attributed to nancing 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.
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.
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 numbers. 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 Republic Buryatia (Ulan-Ude), JSCB "Kuzbassprombank" (Kemerovo), Krasnoyarsk Chamber 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 enterprises 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 arrears (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 (producers) 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. The article presents some mathematical problems reducible to the classical problem to nd in the circulation ow 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.