=Paper=
{{Paper
|id=Vol-3018/Paper_13.pdf
|storemode=property
|title=Permutation-Matrix Approach to Optimal Assignment Design
|pdfUrl=https://ceur-ws.org/Vol-3018/Paper_13.pdf
|volume=Vol-3018
|authors=Olha Matsiy,Oksana Pichugina
|dblpUrl=https://dblp.org/rec/conf/intsol/MatsiyP21
}}
==Permutation-Matrix Approach to Optimal Assignment Design==
https://ceur-ws.org/Vol-3018/Paper_13.pdf
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, jU
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 k21 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 k21.
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