Permutation-Matrix Approach to Optimal Linear Assignment Design Olha Matsyia and Oksana Pichuginab a Kharkiv National Аutomobile and Highway University, Str.Yaroslava Mudrogo 25, Kharkiv, 61002, Ukraine b National Aerospace University "Kharkiv Aviation Institute", Chkalova Street 17, Kharkiv, 61070, Ukraine Abstract The paper presents a new iterative approach to solving Linear Assignment problems (LAP) and finding a perfect matching in a weighted bipartite graph iteratively. For that, a new permutation-matrix model of optimal linear assignment is proposed, which allows recursively finding solutions on a set of augmenting paths built based on the current matching. The results can be combined with other methods for solving a LAP such as the Hungarian Algorithm and minimal cost method in order to find an optimum faster. Keywords 1 Linear Assignment Problem; optimal assignment; matching; augmenting path; routes; permutation. 1. Introduction Transport Logistics is a broad application domain for Decision Theory and Optimization Theory dealing with routings and scheduling. It is inevitably connected with optimal placement in space and time of discrete objects. Therefore, Combinatorial Optimization is utilized widely in Transport Logistics problems. Among transport logistics problems are numerous models of optimizing closed routes (routing models), which contain some conditions and constraints inherent in the actual process of moving objects on a plane or in space. Therefore, routing problems are crucial in rational, from economic prospective to decision-making and accelerating transport operations and management. Even the most complex routing problems have a lot in common with the classical Vehicle Routing Problem (VRP) formulated by Danzig and Ramser [1, 2] and extended in many sources [3, 4, 5, 6]. This paper is dedicated to a solution of one type of assignment problem (Linear Assignment Problem, LAP), which is, in turn, is closely related to the Salesman Problem (SP) of a formation of a close route of a minimum length in a graph. The SP is a classical NP-complete problem, while a LAP represents a narrow subclass of combinatorial optimization problems solvable for polynomial time. That is why it is highly perspective to find other approaches to a polynomial solution of a LAP and utilize it in effective metaheuristics for the SP. 2. Related work Conventional methods for solving the Linear Assignment Problem, such as the Hungarian algorithm, Kahn-Munkres method, and potential method are based on different combinatorial II International Scientific Symposium «Intelligent Solutions» IntSol-2021, September 28–30, 2021, Kyiv-Uzhhorod, Ukraine EMAIL: olga.matsiy@gmail.com (Olha Matsyi); oksanapichugina1@gmail.com (Oksana Pichugina) ORCID: 0000-0002-1350-9418 (Olha Matsyi); 0000-0002-7099-8967 (Oksana Pichugina) ©️ 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) 141 optimization approaches. They are all polynomial and characterized by different time complexity,   while the best one is O n3 , where n is an order of their cost matrices [7, 8, 9, 10]. In [11], an algorithm for solving one version of the LAP is presented, which complexity has been   reduced to O n2 . It was shown that the algorithm plays a role of procedure functions that can be embedded into the Branch and Bound method for solving LAPs. It resulted in faster than before calculating tighter lower bounds on the cost of closed routes in TSP. This algorithm is designed to find a perfect matching of the minimum total weight in a weighted bipartite graph on 2n vertices. It utilizes an introduced concept of the shortest augmenting path in a graph [11, 12]. One of the common TSP settings is that the distances dij between each pair of cities i and j i, j  {1, 2,  , n} are known, and it is required to find such a sequence of the cities  [1],  [2], ,  [i], ,  [n] minimizing the value n –1  d i  i 1  d n [1] . (1) i 1 This value is equal to the length of the shortest route (bypass), starting in a city  [1] , passing through all cities in turn and ending in  [1] after visiting  [n]. The TSP, in which dij  d ji for each pair i, j of cities is called symmetric (STSP) [13, 14, 15]. TSP and STSP are strongly NP-complete problems. They belong to a class of combinatorial optimization problems and, reflecting a continuously growing set of applications and generalizations, remains a topical research topic [15, 16, 17, 18]. Suppose that, to each edge, it is assigned zero weight in a complete graph on n  1 vertices (thus reflecting that all delivery routes are of the same cost), but there is a fee for using each vehicle unit. This fee is fixed for all vehicles of the same capacity. Here the task is to find the minimum number of cars that will transport n cargo dii i . This problem, known as the container packing problem, is NP-complete in the strong sense. Since VRP includes the TSP and packing problem conditions, there is unlikely to solve the VRP exactly by efficient algorithms [15]. Besides, fulfilling a constraint  i 1 dii  K  S for a given K  2 and a n container capacity S is not a sufficient condition for the existence of a feasible VRP solution. The VPR is representable as a TSP with constraints. Among the conditions is the one that there is a vehicle initially located in the depot. The vehicle must deliver a homogeneous cargo from production points to consumption ones and then return to the depot. The total number of points of production and consumption is n; they form a set N  {1, 2, , n} , while the depo (the base) is assigned an index 0. The cost of transporting cargo from point i to point j ( i, j  {0}  N ), the vehicle capacity is equal to S , the weight qi of the load that must be delivered back from the point of production if qi  0 or delivered to the point of consumption in case of qi  0 . Also, the balance condition  i 1 qi  0 has n to satisfy. It is required to find a permutation  [1],  [2], ,  [i], ,  [ n] on set N such that u 0  q [i ]  S , u  N , (2) i 1 n –1 d0, 1   d i  i 1  d  n,0  min (3) i 1 142 It follows from expressions (1) and (3) that the formulated problem is the classical TSP, in which the set of feasible solutions satisfying condition (2) may be empty. For example, it has no solution  0,  [1],  [2], ,  [i], ,  [n], 0  for S = 1, n = 5, qi  2 / 3 for suppliers i  1, 2, 3 and qi  –1 for consumers i  4, 5 [1]. Step one  d 1 1  min di1 j1 , di1 j2 , di2 j1 , di2 j2 . i j  After solving the TSP with the matrix  dij  , one must return to the original transport network ij and add all the arcs to the resulting bypass. For the VRP, several applied versions are known in the literature. These include, for example, the School Bus Routing Problem (SBRP), which has the following formulation. A school has a fleet of identical vehicles of capacity S, designed to deliver each student i to his residence after classes. The school has order number 0. The travel time tij from point i to point j is known, i, j 0  N , and the cost of the travel dij is known as well. Also, there is a requirement that each vehicle must return to point 0 no late than at time T [1]. In SBRP, it is required to find Boolean variables xij , i, j 0  N , and such a number K of the vehicles satisfying the following constraints: the point 0 is the beginning and end of a route of each vehicle, n n xi0  x0i  k , (4) i 1 i 1 any delivery point i is included in a single route: n n xij  x ji 1; j  N ; (5) i 1 i 1 there are no routes that include only delivery points:  xij  U ; (6) i, jU U N the route  0, i[1], i[2], , i[ j], , i[ r], 0  , i[ j ]  N of the vehicle satisfies a capacity condition:  –1  xi[ j], i[ j 1]  –1 S –1 . (7) j 1 Also, there is a time limit T for the route execution: r –1 t0i[1]   ti[ j ], i[ j 1]  ti[ ]0  T . (8) j 1 The SBRP objective function is: n  dij xij  min. (9) i, j  0 It is easy to see that, in the SBRP dii  1, i  1, n instead of dii  Z  in the VRP, and the number of vehicles is K  n / S  . 143 If, in the SBRP, the cost dij and time tij of moving the vehicle from a point i to a point j are linearly dependent, and dij  0 if tij  0 . (9) can be replaced by an objective function n  tij xij  min (10) i, j  0 utilizing the initial data dij , i, j  {0}  N as auxiliary data for the economic assessment of the constructed solution. The requirement dii  1 for i  1, n makes a search of (9) much easier. The constraint on the vehicle load takes the form of inequality k   n / S  . The latter is a necessary and sufficient condition for a feasible solution to the problem. If we substitute r  n in (7) and (8), the SBRP becomes the TSP on a set of vertices 0  N , N  n of a transport network represented by the full graph. The k-VRP problem is closely related to the VRP. In contrast to the VRP, the k-VRP does not specify the amount dii of cargo delivered to the i-th consumer ( i  1, n ) and the capacity S of each vehicle, but it is required to serve at most k clients. It is necessary to minimize the total cost of routes of all vehicles, the number of which is equal to m  n / k  . Therefore, the k-VRP is solvable for n, k Z  and n  k . For n  k , it is the TSP defined on a set of permutations induced by  0, i 1, i 2, , i  j , , i n, 0 . In particular, for k = 2, it is polynomially solvable, while for k  3 , it belongs to the class of NP-complete problems [15, 16, 19, 20, 21]. A peculiarity common for all the above routing problems is that they are formulated as generalizations or variants of the NP-complete problem TSP, where additional constraints are added. These constraints naturally make narrower the TSP feasible domain. The constraints lead to the problems' potential infeasibility, stimulating constant interest in further studying combinatorial optimization problems related to the TSP. In this paper, a new mathematical model of optimal assignment is described, which develops the results of [11, 12, 22, 23, 24, 25]. The paper goal is to build a permutation-matrix model of optimal assignment, which allows recursively finding solutions on a set of augmenting paths built from the current matching. 3. Main part Let us describe the method for solving the LAP. We will use the following its formulation.For the matrix of costs (weights) C  cij  of order n , where cij  R1 or cij  , where R0 is a set of ij non-negative real numbers, find n C    min  ci, [i ]. (11)  Sn i 1 Here    [1],  [2], ...,  [n] is a permutation of a set {1, 2, ,n} of the columns’ indexes of the matrix C, Sn is the permutation group, and    [1],  [2], ...,  [n] is the optimal permutation (an optimum) corresponding to the objective function value C     i 1ci [i ] . n The LAP is feasible if C     . Respectively, c [i]  , i  1, n . Note that a LAP with a cost matrix containing elements cij   may be unfeasible. In this case, it is necessary to establish that the feasible domain of the problem is empty. Further, we will assume that we deal with a feasible LAP. 144 The permutation    [1],  [2], ...,  [n] , where C     , respectively, c [i ]   i  1, n, is called a feasible solution to the LAP. The core of the Hungarian algorithm for LAPs is that the cost matrix is equivalently transformed first to make a significant number of its elements zero. The one applies a greedy search to find as many as possible independent zeros. After that, directly the algorithm is applied, increasing by exactly one the set of independent zeros. Like the Hungarian algorithm, our approach to finding the permutation  sequentially increases by one on each iteration the number elements k, k  1, n, of the sequence representing a certain part of a feasible solution (a partial solution) of a LAP. Let us list some properties of this sequence and outline the way of its construction. Any part of a feasible solution of a LAP consisting of k elements determines uniquely a submatrix ci j  of the matrix C having the order k , such that  s t  s ,t i1  i2  ...  is  ...  ik , j1  j2  ...  jt  ...  jk . Introduce a sequence  k   k [i1],  k [i2 ], ...,  k [is ], ...,  k [ik ] ,  k [is ]  j1, j2 , ..., jt , ..., jk  , k  1, n  1, such that: a) it is a solution TO the LAP having the submatrix ci j  as its cost matrix;  s t  s ,t b) the cost of the assignment induced by the permutation  k does not exceed the optimal value of a LAP induced by any submatrix of C having the order k . Let us try to develop a conversion procedure of a sequence  k into a sequence  k 1 . If such an efficient procedure exists for k  0, n  1 and the LAP (11) is feasible, then it takes n steps to find    n . Let us find out how the sequences  k , k  1, n may be constructed. Step 1. The initial sequence 1  1[i1] is trivially defined and is identical to the minimal cost greedy method to solve LAPs. We derive the minimum value of the matrix and make the  corresponding initial assignment of the order 1: let clr  min cij |1  i, j  n , respectively,  i1  l , 1  1[i1] , 1[i1]  r. Step 2. In order to find  2   2[i1],  2[i2 ] from 1 , let us determine     cms  min cij | i  l , j  r , clp  min clj | j  r , cvr  min cir | i  l (see Fig. 1). p q r s m cmp cms l clp clr cvr cvs v w cwq Figure 1. Matrix C It is easy to see that if clr  cms  clp  cvr (further Case 2.1), then conditions a) and b) are satisfied for a sequence  2 with i1  l ,  2 [i1]  r , i2  m,  2 [i2 ]  s. 145 It corresponds to a submatrix of the matrix shown in Fig. 1 depicted in Fig. 2. r s l clr m cms Figure 2. The C -submatrix with elements clr and cms Otherwise, these conditions are satisfied by a sequence  2 with elements i1  l ,  2 [i1 ]  p, i2  v,  2 [i2 ]  r (further Case 2.2). The corresponding submatrix is depicted in Fig. 3. p r l clp v cvr Figure 3. The C -submatrix with elements clp , clr and cvr Step 3. Now, we transform the sequence  2 into a sequence  3   3[i1],  3[i2 ],  3[i3 ] .   If we deal with Case 2.1, then next we find cwq  min cij | i  l , m; j  s, r (see Fig. 1) and the value MIN1  clr  cms  cwq . Note that cwq  cms , if  2   2[l ]  p,  2[v]  r  , i.e. we deal with Case 2.2. The transformation from  2 into  3 is the result of solving the following auxiliary problem. For rows l, m and columns r , s of the matrix C induced by the elements first two least elements clr and cms , it is required to find a triple of components with the minimum sum of their values. Any two triple elements must be placed in three different rows, particularly including l, m and three various columns including r , s ones. If such a triple does not contain clr , but includes cms , then the sum of its elements is bounded from below by the value S1  cvr  clp  cms ,   where cvr  min cir | i  l , m , clp  min clj | j  r , s (further, Case 3.1). Let the solution of the auxiliary problem be a triple, which includes clr and does not contain cms . Then a value S2  clr  cmp  cvs ,   where cmp  min cmj | j  s, r , cvs  min cis | i  l , m (further, Case 3.2). Elements of a solution of the auxiliary problem that does not contain clr and cms define a value  S3  min clp  cmr  cws , cmq  cls  cvr  (further, Case 3.3). Here, cws  min cis | i  l , m ,  cmr  min cmj | j  p, s (see Fig. 4),   cls  min cis | i  m, v , cmq  min cmj | j  r , s (see Fig. 5). Let MIN 2  min S1, S2 , S3. 146 It is clear that it corresponds to the sequence  3 we are looking for if MIN 2  MIN1, otherwise  3   3[l ]  r ,  3[m]  s,  3[ w]  q  (further, Case 3.4). p q r s cmq cms m l clr cls v cvr w Figure 4. Elements of an auxiliary problem solution that does not contain clr and cms that defines  S3 given cws  min cis | i  l , m , cmr  min cmj | j  p, s  p q r s cmq cms m l clr cls v cvr w Figure 5. Elements of an auxiliary problem solution that does not contain clr and cms that defines  S3 given cls  min cis | i  m, v , cmq  min cmj | j  r , s  Depending on which one of the Cases 3.1-3.4 corresponds to min MIN 2, MIN 2 , the sequence  3 is set. Step k. A sequence  k   k [i1],  k [i2 ], ...,  k [is ], ...,  k [ik ] with the properties a) and b) generally is transformed into a sequence  k 1   k 1[i1],  k 1[i2 ], ...,  k 1[ir ], ...,  k 1[ik 1] with the same properties as the following. In the matrix C , it is found   cik 1, k [ik 1]  min cij | i  i1, i2 , ..., is , ..., ik , j   k [i1],  k [i2 ], ...,  k [is ], ...,  k [ik ] , 147 then a sequence  1k 1   k ,  k [ik 1 ] (further, Case k.1) is formed and k MIN1   cis , k [is ]  cik 1, k [ik 1 ] s 1 is evaluated. Next, the problem of finding k  1 elements is solved, for which in the matrix C the minimum sum of their values is attained. At the same time, they are located in different rows and columns, including all rows and columns with numbers specified by values c [i ] , k 1 c [i ] , ..., c [i ] , ..., c [i ]. This induces several cases Cases k.2-k.K and the values S2 ,..., S K . k 2 k s k k Then MIN 2  min S2 ,..., S K  is evaluated, and the partial permutation  k21 of the order k , where the value is achieved, is derived. Finally,  k 1 is found by assigning  k 1   1k 1 in case of MIN1  MIN 2 . Otherwise,  k 1   k21. In the same way, the iterative process continues until  n will be found. Process terminates and    n is set. The complexity of our method for solving LAPs described above has complexity O n3 , the best  known so far and coinciding with the improved version of the Hungarian algorithm. This means that these two can be combined in order to get a hybrid method working, n average, better than the methods itself. 4. Conclusion A new permutation-matrix model of optimal assignment is proposed. It allows recursively finding solutions on a set of augmenting paths built with respect to the current matching. The proposed scheme for finding an optimal assignment underlies a method of solving a LAP where a solution to the problem is found exclusively employing matching theory for bipartite graphs. The developed model for finding the optimal destination develops transport logistics’ theory. It is focused on improving the organization of transportation in real-time and in real situations of vehicle traffic. Its implementation allows reducing the time and fuel consumption for carrying out transport works. The method uses the well-known algorithm for finding maximum matchings in bipartite unweighted graphs, built according to a scheme that expands approaches to solving hard optimization problems. 5. References [1] D. P. Bertsekas, Network Optimization: Continuous and Discrete Models, Athena Scientific, Belmont, Mass, 1998. [2] E.M. Bronshtein, T.A. Zaiko, Deterministic optimization problems of transport logistics, Automation and telemechanics, 10 (20100 113-147. [3] G. Cornuejols, F. Harche, Polyhedral study of the capacitated vehicle routing problem, Mathematical Programming, V. 60, 1–3 (1993) 21–52. doi: 10.1007/BF01580599. [4] A. Langevin, D. Riopel (Ed.), Logistics Systems: Design and Optimization, Springer US, 2005. doi: 10.1007/b106452. [5] J.-Y. Potvin, Vehicle Routing, in: C. A. Floudas and P. M. Pardalos (Ed.), Encyclopedia of Optimization, Springer US, 2008, pp. 4019–4022. doi: 10.1007/978-0-387-74759-0_702. 148 [6] A. V. Vural, B. Eksioglu, Vehicle routing problem with simultaneous pickups and deliveries Vehicle Routing Problem with Simultaneous Pickups and Deliveries, in: C. A. Floudas and P. M. Pardalos (Ed.), Encyclopedia of Optimization, Springer US, 2008, pp. 4022–4027. doi: 10.1007/978-0-387-74759-0_703. [7] D.J. Little, K. Murty, D. Sweeney, K. Carell, Algorithm for solving the travelling salesman problem, Economics and Mathematical Methods, V. 1, 1 (1965) 90-107. [8] C. Helmberg, The m-Cost ATSP, in: G. Cornuéjols, R. E. Burkard and G. J. Woeginger (Ed.), Integer Programming and Combinatorial Optimization, Springer, Berlin, Heidelberg, 1999, pp. 242–258. doi: 10.1007/3-540-48777-8_19. [9] E. Mainika, Optimization algorithms on networks and graphs, Mir, Moscow, 1981. [10] R. E. Burkard, E. Çela, Linear Assignment Problems and Extensions, in: D.-Z. Du and P. M. Pardalos (Ed.), Handbook of Combinatorial Optimization, Springer US, 1999, pp. 75–149. doi: 10.1007/978-1-4757-3023-4_2. [11] A.V. Panishev, D.D. Plechisty, V.A. Shevchenko, Local search procedures in combinatorial algorithms for solving the general traveling salesman problem, Artificial Intelligence, 1 (2005) 465–470. [12] O.B. Matsiy, A.V. Morozov, A.V. Panishev, The Recurrent Method to Solve the Assignment Problem. Cybern Syst Anal, 51, 2015, pp. 939–946. doi:10.1007/s10559-015-9786-x. [13] S.M. Rezer, S.E. Lovetsky, I.I. Melamed, Mathematical methods of optimal planning in transport systems, Results of Science and Technology, series ”Organization of Transport Management”, 1990. [14] E. X. Gimadi, A.V. Shahshneider, Approximate estimation algorithms for routing tasks at random inputs with a limited number of clients in each route, Automation and telemechanics, 2 (2012) 126–139. [15] C. H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Mineola, N.Y., 1998. [16] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman & Co Ltd, New York, 1979. [17] L. Lovasz, M. D. Plummer, Matching Theory, Chelsea Pub Co., Providence, R.I, 2009. [18] T.L. Saaty, Optimization in integers and related extremal problems: from a course given at the University of California, Los Angeles, and George Washington University, Washington DC, RWS Publications, 2014. [19] J. Evans, Optimization Algorithms for Networks and Graphs, 2nd ed., CRC Press, 2017. [20] K. Thulasiraman, S. Arumugam, A. Brandstädt, T. Nishizeki, Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, CRC Press, 2016. [21] A. Langevin and D. Riopel (Eds.), Logistics Systems: Design and Optimization, Springer US, 2005. doi: 10.1007/b106452. [22] O. Pichugina and O. Matsyi, Boolean Satisfiability Problem: Discrete and Continuous Reformulations with Applications, in Proceedings of the 2020 IEEE 15th International Conference on Advanced Trends in Radioelectronics, Telecommunications and Computer Engineering (TCSET), 2020, pp. 623–627. doi: 10.1109/TCSET49122.2020.235507. [23] Y.G. Stoyan, S.V. Yakovlev, Theory and Methods of Euclidean Combinatorial Optimization: Current Status and Prospects. Cybern Syst Anal, 56 (2020) 366–379. https://doi.org/10.1007/s10559-020-00253-6. [24] S. Yakovlev, O. Pichugina, On constrained optimization of polynomials on permutation set CEUR Workshop Proceedings, v. 2353, 2019, рр. 570–580. [25] I. Averbakh, W. Yu, Multi-depot traveling salesmen location problems on networks with special structure, Ann Oper Res, V. 286, 1 (2020) 635–648. doi: 10.1007/s10479-018-2812-4. 149