Serhii Chernova, Serhii Titova, Liudmyla Chernovaa, Liubava Chernovaa, Antonina Trushliakovaa, Natalia Kunanetsb and Igor Bobykb

Abstract

A classical assignment problem takes a significant part in models and methods of combinatory (discrete) optimization. The problem belongs to so-called Boolean optimization problems where the unknowns possess values equal to 0 or 1. Solution of an assignment problem can be obtained by method of potentials as it consists in a partial case of transportation problem - the volumes of demand and supply for each manufacturer and consumer are equal to one. With account taken of a high level of degeneracy in the primary reference plan of an assignment problem mathematic model, solution thereof based on the method of potentials contains many trivial steps hampering the solution process convergence. The Hungarian method is rapidly converging and adapted to problems of this class.

Keywords

• 1 Project implementation
• assignment problem
• generalization
• matrix
• symbol mathematics
• Hungarian method
• theory of graphs

1. Introduction

2. Research paper study and problem statement

A classically set assignment problem belongs to two-index transportation problems [ 1,2 ]. The known tools of solving such problems can be used for finding the optimum distribution of an assignment problem. Specifics of assignment problem promoted the development of special solution methods. The first papers studying assignment problems relate to the first half of the 20th century. The papers of Konig and Egervary treat the assignment problem as a problem on finding optimum matches on a bipartite approximate graph. [ 6,7,8,9 ] Their researches allowed Kohn to develop in the 50ties a special solution method – the Hungarian method. [ 10–20 ] This classical type of assignment problems and the methods of their solution keep being used today. However, we can see problems appearing in the real life where it is necessary to deviate from requirements of the classical assignment problem – one candidate to one vacant office in a team and one vacant office for one candidate. Such a problem is represented in the known combinatory problem on a system of several representatives.[ 17 ]. In this type of problems, one vacant working place already needs assignment of several employees.

3. The purpose and objectives of the research

The purpose of the paper consists in development of a generalized mathematic model of assignment problem and its solution, with further computer-aided implementation in the environment of Maple and Mathematica symbol mathematics for optimizing procedures of selecting candidates to the project team and determining requirements to the project product; comparing the adequacy of solution results using the procedure developed and the subprograms integrated in the program package kernel.

The following tasks were set for achieving this objective: • Construct a general problem within the classical approach of assignment problem and provide a model example of solutions by the Hungarian method. Based on it, compose a generalized problem where the condition is violated – one candidate is assigned to one project vacancy only and each vacancy is only to be given to one candidate.

• Develop an efficient procedure of solving a generalized assignment problem.

• Make theoretical justification of the procedure developed and interpret it from the dynamic optimization concept’s point of v–ieRw. Bellman optimality principle. Provide a model example of solution.

• Based on Maple and Mathematica symbol math packages, develop programs implementing the algorithm developed. Make an alternative computer-aided calculation of the model example and compare the results with man-made calculations.

• Make computer-aided calculations in Maple та Mathematica computer package environment using the package kernel subprogram library. Compare the model solution results with results obtained before. Develop an algorithm of using the proposed model in project planning procedures.

4. Reduction in common linear optimization problems

4.1 Statement and mathematical model of the problem

The assignment problem is one of classical problems in the theory of combinatory optimization in applied mathematics. Prior to provide a general definition of the problem, let us give particular examples bringing to an assignment problem.

One of possible informal statements of an assignment problem can be represented in the following version. A certain system has an n number of vacant working places m candidates pretending to. We know the matrix  c11  c C   21   cm1 (1) giving numerical evaluation cij  0 of the determined level of efficiency in case of assigning i th candidate to j th working place. The assignment is to be carried out to optimize the total efficiency from assignments – the maximum or the minimum depending on particular sense of the problem. The classical problem statement is to take into account that each candidate can be selected to the project team only one time, and, the other way round, each vacancy in a team is to correspond exactly to one candidate. Should m  n (lack of vacancies), we need to balance the system by adding m  n fictitious vacancies in the project team with numerical evaluation of efficiency being zero: cij  0 , i  m  1, m  2, , m  (m  n) , j  1, 2, , n .

If n  m (lack of candidates), we need to add n  m fictitious candidates to the system. Then, without loss of generality, let us consider the assignment problem balancing procedure as competed unless otherwise conditioned.

An object recognition problem can be reduced to an assignment problem. Thus, let us have an n number or objects for which we have an existing approximate description of their properties, but we don’t know which of the objects this description relates to. We have a set of numerical inform cij  0 as a measure of approximate description of each of them. It makes sense to state a problem on minimizing the total set approximation to the objects.

A conceptual assignment problem allows easily interpreting it as a classical transportation problem providing for determining the type of information system to be developed for customer in the process of project implementation. We need to find the optimum type of information system according to customer’s requirements. We have a list of requirements being e.quTahle stocopoenoef works on the system development is equal to one as well. The requirements to the information system created in the process of project implementation can be minimized by the project cost matrix , i  1, 2, , n , j  1, 2, , n .

Conceptual models that can be interpreted as an assignment problem can be represented as sets (stakeholders) and their respective efficiency criteria are given in Table No. 1. cij nn

Let us compose a mathematical model of general assignment problem. In an arbitrary active

U (continuum, cluster) we might have two discrete finite sets A and B . Set A  A1, A2 , An has a cardinality | A | n and set B  B1, B2 , | B | n . We make a bijection (a one-to-one correspondence) A B  has a cardinality

n B by given function C  cij nn : A  B  R . (Fig. 1) We need to carry out this distribution to minimize the value of efficiency criterion.

 0, for non-distribution of Ai to Bj xij  1, for distribution of Ai to Bj Then the target function of problem will look like

n n WI    cij xij  min .

i1 j1 The classical assignment problem system of constraints is recorded as follows:  n  xij  1, j  1, 2, , n,  i1 I :  n  xij  1, i  1, 2, , n,  j1

The matrix of admissible plans for a linear optimization problem (3), (4) Based on the classical approach to assignment problem, let us introduce the Boolean variables (2) (3) (4) (5)  x11  X   x21    xn1 x12 x22 xn2 x1n 

 x2n     xnn 

xij nn is a permutation matrix as it contains one unit in each row and one unit in each column. Let us call this matrix a permutation matrix with depth h  1 . If we have a k number of units in each row and each column – matrix with depth h  k . Such matrixes are also used to be called Boolean (binary) or (0,1)-matrixes.

For a classical assignment problem, matrix X is also a bistochastic one – the sum of values for each row and each column is equal to one.

Therefore, the classical approach to formation of an assignment problem leads to a mathematic model of linear discrete optimization of the type of two-index classical transportation problem [ 1,2 ] that we use for determining the type of information system. For solving this problem, it is reasonable to use the method of potentials, but in view of binary character of the unknowns, solution of the problem provides for special methods to be used. One of the most efficient methods is the so-called Hungarian method. As in the case of the simplex method, it consists in a successive transfer from the current admissible plan X to the improved one, through implementation of a special algorithm. Each step includes checking for optimality. [ 10,11,12,13 ]

The first step of the Hungarian method consists in modification of matrix C  . In each cij nn case, we should select the least value and subtract it from the elements of respective row. This provides presence of at least one zero in each row. Similarly, it has to be done for columns. In the result of these first modification actions – we can guarantee the presence of at least one zero in each row and in each column.

The second step of the Hungarian method consists in analysis of modified C . If there is a possibility to select one zero in each row and in each column, we can state that we have obtained the optimum solution. The assignment problem is deemed resolved. If such selection is not possible, we need further modification of C matrix and moving to the third step accordingly.

The third step of the Hungarian method provides for crossing out all zeros with possibly least number of crossing lines. This action results in three types of C matrix elements. The first type – the elements not crossed out. The second type – the elements crossed out. The third type – crossed out and located at crossing of the straight lines. We select the least value among the elements not crossed out. The value of this elements is to be subtracted from the values of the elements not crossed out and to be added to the third-type elements. After this procedure, the algorithm is repeated from the first step.

The given procedure of the Hungarian method is rapidly converging and allows obtaining the problem solution within a finite number of steps.

4.2 Model example No. 1

Solve a classical assignment problem represented by a distribution matrix  4 3 9 4 9  (6)

Solution:

We have a classical assignment problem looking as follows:

4 4 WI    cij xij  min,

i1 j1  7  C   4   4  5 I :  in1  4  xij  1, j  1, 2,3, 4,  xij  1, i  1, 2,3, 4,  j1

One of the two possible variants of selecting one zero in each row and each column is marked with circles. Thus the problem has been resolved. We have found the optimum distribution in a classical assignment problem ensuring the minimum value of the target function.

The optimum distribution (10) (11) Wmopint  4  2  1  1  9  17 . Note:

The idea of crossing out rows and columns in the Hungarian method is not subject to a random law, but to a determined interpretation based on the theorem on the number of most independent elements of binary matrixes.

Let us call two matrix elements independent if they are not lying on the same line. Rows or columns of a matrix are called its lines. Based on the terminology introduced, we perform the theorem.

The theorem. The maximum number of independent units in an arbitrary binary matrix is equal to the minimum number of lines including all matrix units.[ 17 ]

We provide an example to interpret the theorem. Let us consider the matrix

1 0 1

Unit elements of matrix A are located in the second and in the fourth columns and in the fourth and fifth rows. Crossing out by the least number of lines of all the matrix units (ones) looks as follows In view of this, the maximum number of the matrix independent units is equal to four.

An assignment problem is connected with combinatory configurations as it operates with binary matrixes. Let us consider an example to interpret this interrelationship.

We might have a seven-member set U  1, 2,3, 4,5, 6, 7 . We need to record three-member subsets of set U , subject to two arbitrary but different elements of these subsets are only located in one of them. It is not difficult to make sure that such subsets will be represented by the following configuration 1, 2, 4 , 1,3, 7 , 1,5, 6 , 2,3,5 , 2, 6, 7 , 3, 4, 6 , 4,5, 7 .

The above mentioned combinatory configuration is assigned an incidence matrix  1  M   0 1  5. Generalized assignment problem and its solution algorithm

Let us call the problem shown below a generalized assignment problem:

n n WI    cij xij  min ,

i1 j1  n  xij  k, j  1, 2, , n,  i1 I :  n  xij  k, i  1, 2, , n,  j1 where k may take values k  2,3,

, n and characterizes the relative depth of distribution in an assignment problem.

The approach to solution of a generalized assignment problem should be interpreted from a dynamic optimization problem point of view.[ 12,13,14 ] According to the concept of dynamic (13) (14) (15) optimization, all the chain of problem distribution is to be divided into separate elementary steps. A single-type simplified problem is resolved at each of such steps. The basic method of dynamic optimization consists in the method of recurrent relations. At the same time, construction of such an algorithm is subject to the known principle of R. Bellman, which is based on the fact that whatever is the initial status of the system at arbitrary current step of optimization, the next step is selected from the condition of optimality relative to the previous status. This approach provides in solution chains not the locally optimum but the globally optimum solution for the process in general.

In our case, for solving a generalized assignment problem, we fix the previous optimum status by substitution of limit values (big or small ones) depending on the sense of the problem in matrix C  c . The next problem is resolved by the canonical (the Hungarian) method. Then we have ij nn to substitute again the limit values in the optimum positions of the already modified matrix C  c

ij nn assignment problem generalization. We use the proposed approach to resolve the model problem.

and to resolve the problem. The number of iterations is equal to the depth of

5.1 Model example No. 2

Find the minimum solution of assignment problem (16) (17) (19) with generalization depth k  3 .

Solution: We have the following mathematic model:

4 4 WI    cij xij  min ,

i1 j1  n  xij  3, j  1, 2, 3, 4,  i1 I :  n  xij  3, i  1, 2, 3, 4,  j1 xij  0  1, i, j  1, 2, 3, 4.

 n  xij  1, j  1, 2, 3, 4,  i1 I :  n  xij  1, i  1, 2, 3, 4,  j1

At the second step, we fix the obtained optimum plan of the previous system status by substitution of big values at the places of the optimum solution in matrix C (marked with circles below). For a new matrix C (1) , we perform the optimum solution. In the result, we obtain: ( 21)

At the third step, we make similar substitutions and in the result we obtain the following optimum calculation

Combining the three steps previously completed, we obtain the final calculation as you can see in the following plan

X mopint   1  1 5.2 Computer-aided calculation and comparison with calculation under the algorithm proposed.

Let the assignment problem be represented by a distribution matrix 1 4 9  C  8 7  8 2 2 1 4 2 5 4 9 4 7 3 7 4 8 1 7 2 4 2 6 7 1 8 9 6 5 8 9 5 1 5 4 3 2 4 2 6 9 4

 . 5 6

 3 4 WI  

i1 j1

We perform the first step of matrix C modification .(28) (27)  n  xij  3, j  1, 2,  i1 I :  n  xij  3, i  1, 2,  j1 xij  0  1, i, j  1, 2, , 7, , 7,

(26)

In the beginning, we provide a problem solution by the procedure proposed. Let us divide the problem into three steps. At the first step, we solve the problem under condition

According to requirements of the second step in the Hungarian method, we check the possibility in the modified C(2) matrix to select one zero in each row and in each column.

This possibility does exist. Respective elements are marked with circles, therefore, it makes no sense to perform the third step of the Hungarian method. We have obtained the solution of the first general problem iteration. 0

 0

 0 0 , W(1) ( X (1) )  16 .

 I opt 0

 1

For the beginning of the second problem solution step, the assignment matrix positions corresponding to the optimum solution of the first step should be replaced by the maximum limit values (for instance, the value equal to 9 would be sufficient). Finally, we have the initial matrix of the second calculation step looking as follows (intentionally introduced values are circled) (29) 5

 7

 1

 3 2

 5 3 (31) We have a solution belonging to the second type We make the same transformations at the third calculation step.

7 

1  5 C (4)  5 2  3 0 1 7 1 0 1 0 8 3 5 0 5 0 4 8 0

 0

 1

 0 , W(2) ( X o(p2t) )  22 .

I 0

 0 0

The optimum solution of the third calculation step is represented as:

Combining all the three iterations, we can obtain a solution of the problem stated as the following sum

Respective target function value

WI ( X ompitn )  16  22  27  65 .

For checking the solution adequacy, we compare the obtained man-made calculation with the computer-aided solution using a program developed in Maple symbol math package environment. The program source code is given below: ############################################ `@@@@@@@@@@@@@@@@@@@@@`; A:=Matrix([[ 1,2,4,7,8,1,6 ],[ 4,1,7,2,9,5,9 ], [ 9,4,3,4,6,4,4 ],[ 8,2,7,2,5,3,5 ], [ 7,5,4,6,8,2,6 ],[ 8,4,8,7,9,4,3 ], [ 2,9,1,1,5,2,4 ]]): (32) (33) (34) eq2:=seq(add(x[i,j],i=1..nr)=prhc,j=1..nr): ############################################### `Binary`; with(Optimization): ss1:=LPSolve(zf, {eq1,eq2}, assume = {binary}): Aoptb:=Matrix(nr): for i to nr do for j to nr do Aoptb[i,j]:=rhs(ss1[2,nr*(i-1)+j]) end do: end do: ######################################################### ss1m:=LPSolve(zf, {eq1,eq2}, assume = {binary},maximize): Aoptb1:=Matrix(nr): for i to nr do for j to nr do ##################################### Aoptb1[i,j]:=rhs(ss1m[2,nr*(i-1)+j]) end do: end do: ### X[optmin]=Aoptb; W[min]=ss1[ 1 ]; ############################### `@@@@@@@@@@@@@@@@@@@@@`; The results of calculation with use of this program (35) As we can see, they fully coincide with calculations made under the procedure proposed. The alternative computer-aided calculation was represented by calculation in Mathematica symbol math package environment. An abstract of the program source code is given below: (* Generalized assignment problem. l – number of project team members n – number of jobs (vacant places) k – possible number of vacancies the candidate pretending to.*) (*Initial data*) l = 7; n = 7; k = 3; (*Matrix of expense on candidates selection*) C1 = {{1, 2, 4, 7, 8, 1, 6}, {4, 1, 7, 2, 9, 5, 9}, {9, 4, 3, 4, 6, 4, 4}, {8, 2, 7, 2, 5, 3, 5}, {7, 5, 4, 6, 8, 2, 6}, {8, 4, 8, 7, 9, 4, 3}, {2, 9, 1, 1, 5, 2, 4}} MatrixForm[%] (* Setting two-dimensional variables x[i,j] – assignment matrix generation *)X = Table[x[i, j], {i, l}, {j, n}]; MatrixForm[%]; (* Setting one-dimension variables k – generation of right parts to system \ constraints*) K = Table[k, {l + n}]; (* One-dimension working array - xi[i](Placement of assignment matrix)*)Xi = xi /@ Range[(l*n)]; (* Placement x[i,j] in one-dimension xi[i] *) m = 0; Do[Do[xi[m + 1] = x[i, j]; m = m + 1, {j, 1, n}], {i, 1, l}] (* Beginning of assignment problem description *) (* Target function – assignment expense minimization *) WI = \!\( \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(l\)]\( \*UnderoverscriptBox[\(\[Sum]\), \(j =

1\), \(n\)]\((C1[\([\)\(i, j\)\(]\)] X[\([\)\(i, j\)\(]\)])\)\)\) (* Arrays of sums by rows and columns *) Om1 = Table[\!\( \*UnderoverscriptBox[\(\[Sum]\), \(j = 1\), \(n\)]\(X[\([\)\(i,

j\)\(]\)]\)\), {i, l}]; Om2 = Table[\!\( \*UnderoverscriptBox[\(\[Sum]\), \(i = 1\), \(l\)]\(X[\([\)\(i,

j\)\(]\)]\)\), {j, n}]; (* Optimization problem system of constraints equation *) eq1 = And @@ Thread[Om1 == k]; eq2 = And @@ Thread[Om2 == k]; eq3 = And @@ Thread[Thread[0 <= Xi <= 1]]; (*Library program calculation *) mm2 = Minimize[{WI, eq1 && eq2 && eq3 && Xi \[Element] Integers}, Xi] (* Transition to convenient two-dimension and binary representation \ optimum solution *) X1 = Table[x1[i, j], {i, l}, {j, n}]; m = 0; Do[Do[x1[i, j] = mm2[[2, m + 1, 2]]; m = m + 1, {i, l}], {j, n}] MatrixForm[Table[x1[j, i], {i, l}, {j, n}]] (* Graphic representation of the optimum assignment matrix *) X2 = Table[x1[j, i], {i, l}, {j, n}]; MatrixPlot[X2, ColorRules -> {1 -> Green, 0 -> Yellow}, Mesh -> All, PlotRange -> {2, 30}] (* Zu end *) The model problem calculation results under this program are represented as follows: Matrix C Optimum distribution X mopint 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 0 Graphic interpretation of the optimum distribution X mopint .

As it can be seen from calculations – the results match each other (Figure 1).

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 (37) (38)

6. Research findings

5 6 7 

Realized a formalized approach to composing a classical assignment problem. Provided a model problem solution by the Hungarian method.

Stated a generalized problem in which one project team vacancy can be assigned several candidates. Composed a generalized problem mathematic model.

Developed a generalized problem solution algorithm. Performed theoretical justification of the algorithm. The algorithm interpretation given as a dynamic optimization problem. Provided a model example solution by the method proposed.

For checking and confirmation of calculation results, developed programs based on Maple and Mathematic symbol mathematics packages, both with use of standard subprogram libraries and without them. The calculation was completed with matching results.

7. Conclusions

For further research, it is important to study the cases of different number of candidates to be selected to the team. The developed method of a generalized assignment problem solution proved to be efficient and can be recommended for solution of a wider class of assignment problems.

8. References

References

[1] Y. Zaichenko , Analysis of operations . Vipol, Kyiv, 2000 .

[2] Y. Zaichenko , Analysis of operations: Manual for universities . Vyshcha shkola, Kyiv , 1975 .

[3] H. Kuhn , The Hungarian method for the assignment problems . Naval. Res. Logist. Quart. 2 , 1955 , pp. 83 - 97 .

[4] H. Kuhn , Variants of the Hungarian method for the assignment problems . Naval. Res. Logist. Quart. 3 , 1956 , pp. 253 - 258 .

[5] D. Konig , Theory of finite and infinite graphs . Birkhauser , Boston, 1990 . DOI: 10 .1007/978-1- 4684 -8971-2.

[6] M. Bondarenko , N. Bilous , A. Rutkas , Computer discrete mathematics. Kharkiv , 2004 , 480 p.

[7] K. Rosen , Discrete mathematics and its applications . McGrawHill Science , 2002 . URL: https://www.houstonisd.org/cms/lib2/TX01001591/Centricity/Domain/26781/DiscreteMathemati cs.pdf

[8] I. Kuzmenko , Ihor Sikorskyi National Polytechnic University. Ihor Sikorskyi National Polytechnic University, Kyiv, 2020 .

[9] Y. Nikolskyi , V. Pasichnyk , Y. Shcherbyna , Discrete mathematics. BHV Publishing Group, Kyiv, 2007 .

[10] R. Burkard , M. Dell'Amico , S. MarAteslsliog.nment problems (Revised reprint) . SIAM , 2012 .

[11] O. Bekh , T. Horodnia , A. Shcherbak , Mathematic programming: Manual. Magnolia, Lviv, 2006 .

[12] I. Dziuban , O. Zhyrov , O. Okhrimenko , Operations analysis methods . Politechnika, Kyiv, 2005 .

[13] I. Fedorenko , O. Cherniak , Research operations in the economy . Znannia, Kyiv, 2007 .

[14] A. Krushevskyi , M. Tymchuk , Mathematic programming in economics and management: Training and methodology manual . IMMB, Kyiv, 2001 .

[15] Y. Tolbatov , E. Tolbatov, Mathematic programming: Manual for high school students . Textbooks and manuals, Ternopil , 2008 .

[16] V. Kutkovetskyi , Operations analysis: Manual. Professional, Kyiv , 2004 .

[17] V. Tarakanov , Combinatory problems and (0, 1) - matrixes . Nauka, Moscow, 1985 .

[18] V. Lytvyn , et al., System Development for Video Stream Data Analyzing. Advances in Intelligent Systems and Computing 1020 ( 2019 ) 315 - 331 .

[19] N. Kunanets , A. Kazarian , R. Holoshchuk , V. Pasichnik , A. Rzheuskyi , Information support of the virtual research community activities based on cloud computing , in: International Scientific and Technical Conference on Computer Sciences and Information Technologies , CSIT 2018 , 2018 , pp. 199 - 202 .

[20] A. Shakhov , V. Piterska , O. Sherstiuk , O. Rossomakha , A. Rzheuskyi , Management of the technical system operation based on forecasting its “aging” . CkEsUhRop PWroocreedings 2565 ( 2020 ) 130 - 141 .