key: cord-0209291-pw0hw7gt authors: Hosseini, Eghbal title: Cost-Flow Summation Algorithm Based on Table Form to Solve Minimum Cost-Flow Problem date: 2020-12-29 journal: nan DOI: nan sha: fef37f7ba9c3d8af245cee46116194cfd4dd57c6 doc_id: 209291 cord_uid: pw0hw7gt The minimum cost-flow problems have been attracted recently in optimization because of their applications in several areas of applied science and real life. Therefore, finding optima solution of these problems would be significant. Although some heuristic approaches have been proposed for solving the problem, but there is no any method to summarize information and converting from a graph form to a table. In this paper, at first all information of the problem are summarized in a table and then an efficient algorithm based on considering costs and flows is proposed. The algorithm is strongly efficient for problems with large size and it has sufficiently suitable results by solving some our generated problems. The minimum costflow problem is one of the most important problem in several areas. The objective of this problem is transmit definite products from sources to destinations with minimum cost and satisfaction of the demand and the supply constraints. Two relaxation of this problem is maximal flow and shortest route problems. In other words the problem is a combination of maximal flow and shortest route. However several heuristic approaches and meta-heuristic algorithms [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] have been proposed for solving optimization problems, but there are just few attempts recently to solve minimum cost flow problems [12] [13] [14] . Therefore having a general algorithm to summarize information of the problem and solve it would be remarkable. Proposing optimal solution needs to start from a feasible solution as an initial basic feasible (IBFS) solution. Therefore initial feasible solution is basic solution which affects to optimal solution for the problem. In other words, finding IBFS would be significant. There are some heuristic methods in references which can find IBFS for the problem [12] [13] [14] . 1 Corresponding author However some heuristic approaches have been proposed in references, but there is no any attempt to prepare general code of algorithms in Matlab. In this paper, the authors will present heuristic table to summarize problem information and also to propose Matlab code to solve large size problems. Therefore many more problems can be solved in the future by these codes. Most of proposed algorithms have been used to solve small or specific problems. In this paper, using Matlab code several problems in large or small sizes have been generated. Also the algorithm is implemented by few simple MATLAB codes which is based on costs and flows, therefore it has an acceptable computational complexity. Let a minimum costflow problem with n nodes, defined costs and capacities of flows. Make a tableau which consists of the costs and capacities of flows corresponding arcs of the network. In this tableau, each row in the red part relates to capacities of flows from each node to others and the each column in the blue part under the diagonal shows costs of each node to the others. The table proposes the optimal solution if flows in RHS for all rows, except the last one, be zero. General schema of the tableau has been shown in table 1: Step 2: If the solution not be optimal, among rows in RHS except the last row (demand node) choose the largest flow. Corresponding node (rth node) will be selected as sender node. Step 3: Choose the rth column of the cost part in the table and calculate summation of them with costs to the last node one by one. Minimum of these summations will be selected as receiver node using following formula: Step 4: Calculate and rewrite RHS (sum of flows which each node can send). Flow is positive for sender and negative for receivers. Step 5: Go back to step 2 and repeat the process until finding the optimal solution. Consider following minimum costflow problem. Step 3: Step 4: Cost 3= 4*3=12 Step 5: Step 5: Cost 5= 2*4=8 Step 5: The optimal solution by the proposed algorithm is 103$. Consider following minimum costflow problem which has been proposed in DIMACS. To Node Flow Cost 1 2 4 2 1 3 2 2 2 3 2 1 2 4 3 3 3 4 5 1 The best solution using DIMACS is 4 unit flow by 14$. Using the proposed algorithm, summation costflow table is: Step 1: Step 2: Cost 1= 2*2=4 Step 3: Cost 2= 2*2=4 Step 4: Cost 3= 1*2=2 Step 5: Consider following minimum costflow problem which is a complete graph. To Node Flow Cost 1 2 15 1 1 3 5 6 1 4 30 7 1 5 40 10 2 3 10 2 2 4 15 3 2 5 15 4 3 4 7 1 3 5 10 4 4 5 20 2 Some solution to send 20 unit from the origin to the last nodes are: 180$, 200$, 125$ 1nd 120$. Using the proposed algorithm, summation costflow table has been shown in the following table also the proposed optimal solution is 120$. Step 1: Table 5 . Also size and main matrix of the problem, A matrix which includes both costs and flows, have been shown in this Table. 4 4 5 2 4 2 1 4 3 3 4 4 2 4 3 0 14 3 2 5 5 5 2 4 3 3 5 2 2 1 5 4 3 4 3 4 0 7 2 15 3 4 3 5 2 1 1 1 3 3 2 4 4 4 5 5 1 0 5 5 1 4 1 3 3 5 3 2 4 4 3 2 1 3 2 1 4 2 0 1 3 4 2 4 2 4 4 3 1 2 3 2 1 5 3 5 2 4 2 0 518 Example9 25 0 7 1 12 3 3 10 4 5 7 7 6 10 3 3 2 5 12 4 12 11 13 13 5 5 2 0 8 5 13 13 9 4 11 4 7 6 9 15 12 15 4 8 1 12 10 13 15 14 7 3 5 0 1 9 4 4 5 2 12 12 9 6 13 9 15 14 6 9 6 10 12 12 2 13 1 1 2 0 1 7 11 12 6 12 14 4 2 4 6 5 14 1 9 3 13 3 8 15 6 5 2 2 1 0 1 4 6 6 4 15 11 15 7 15 1 10 13 4 14 12 13 9 12 5 2 2 1 3 1 0 4 5 9 13 5 7 13 10 15 4 13 11 4 8 6 9 13 2 13 4 1 3 4 2 3 0 13 6 7 9 11 12 12 6 7 15 9 13 5 10 9 15 2 8 3 1 3 4 2 5 5 0 8 2 14 14 7 12 3 10 4 7 13 3 5 8 6 12 15 5 3 2 4 2 5 4 4 0 3 4 11 6 15 15 10 13 7 10 15 9 15 11 8 10 1 1 2 5 5 4 4 2 3 0 14 3 6 15 7 10 14 15 10 2 1 10 9 15 5 1 1 2 3 3 5 3 3 3 4 1 5 1 3 2 2 0 9 11 15 7 2 1 4 1 2 1 1 2 5 3 3 1 5 3 5 4 2 5 4 3 5 0 10 12 11 6 15 5 3 2 3 5 4 2 4 5 3 3 2 1 1 1 3 1 5 4 1 0 8 15 2 4 1 2 3 1 1 4 2 4 3 3 1 1 1 3 2 5 5 5 3 2 2 0 12 14 12 3 4 2 3 4 5 1 4 3 3 5 2 1 4 4 2 5 5 5 1 2 1 0 5 3 4 1 3 5 3 2 2 3 5 1 3 5 1 4 5 2 1 4 5 4 5 1 4 0 13 2 3 1 5 4 4 5 1 5 3 4 4 5 1 3 4 5 5 5 In this paper, a novel idea has been presented which summarizes all information of the minimum costflow problem in a table. Lower computational complexity is because of summarized table and less calculations in the algorithm. Therefore, perhaps this method will be interested by future works in solving much larger problems. Also the algorithm can be suitable tool for solving small problem especially in educational goals. Proposing more efficient algorithms is possible based on the proposed heuristic table in this paper. Novel metaheuristic based on multiverse theory for optimization problems in emerging systems Covid-19 optimizer algorithm, modeling and controlling of coronavirus distribution process Volcano eruption algorithm for solving optimization problems Quality of service aware routing protocol in software-defined internet of vehicles Presentation and Solving Non-Linear Quad-Level Programming Problem Utilizing a Heuristic Approach Based on Taylor Theorem Solving Linear Tri-level Programming Problem Using Heuristic Method Based on Bi-section Algorithm Three new methods to find initial basic feasible solution of transportation problems Big Bang Algorithm: A New Meta-heuristic Approach for Solving Optimization Problems Laying Chicken Algorithm: A New Meta-Heuristic Approach to Solve Continuous Programming Problems A Genetic Approach for Solving Bi-Level Programming Problems Line search and genetic approaches for solving linear tri-level programming problem Multiple objective minimum cost flow problems: A review A strongly polynomial Contraction-Expansion algorithm for network flow problems Minimum-cost flow algorithms: An experimental evaluation