The Algorithm of Selecting Candidates for IT Projects Based on the Simplex Method

Abstract

In the most cases, solution of linear optimization problems is searched for by the simplex method. However, this classic algorithm of solving linear optimization problems may create additional iterations in the procedure of immediate calculation. If we break the standard simplex method algorithm in some of its components, we can accelerate the simplex calculation convergence - reduce the number of simplex tables. For acceleration of the simplex method convergence, it is proposed to deviate from the canonical algorithm. It is required to choose not the neighbor apex as the next problem plan, but the verified apex selected according to evaluation of the biggest and the smallest target function values. The application aspect of the approach proposed is in usage of the obtained research result for providing the possibility to simplify the numeric algorithm based on reducing the number of iterations. This creates conditions for further development and improvement of similar approaches in linear optimization problems. Solution of the model example, that was found by following the classic algorithm and by breaking it, confirms the hypothesis put forward.

Keywords

• Linear Optimization
• Polyhedron
• Target Function
• Simplex Method
• Basis Vectors
• Primary Plan
• Reference Plan
• Polyhedron Apex

-

The intensive development of IT technologies is generated by the high-qualification staff potential available in Ukraine. According to the data of IT Ukraine Association, the IT industry in Ukraine shows an annual growth of 20%. By results of 2018, the IT industry takes the second place with the volume of services exported. The significance of IT services within the structure of export is growing as well. IT companies strengthen their positions owing to simultaneous implementation of a significant number of projects (up to 300) on the order from customers leading in various branches: automotive, healthcare, TV communication and finance. Employees who realize the projects are the main value for IT companies. Formation of the project team is one of the first-priority objectives in the modern project management. It is the smooth teamwork that represents an important factor of successful project implementation. At the same time, the team formation process is one of the most complicated aspects of project management. A project team is mostly created just for the project implementation period and may consist of specialists in different professions. The team formation procedure is rather difficult and requires using innovative methods with account taken of the fact that the created team has to work like a well-adjusted system[ 1, 3-7 ]. 2

Research Paper Study and Problem Statement

In multiple cases, mathematic models of active systems management are interpreted in the form of linear optimization problems [ 2,8,11,14 ]. Solution of linear optimization problems is based on algorithm of the classic or a common simplex method. It consists in intellectual iteration over polyhedron apexes I (allowable area of optimization problem). The plan or an apex of polyhedron I is specified by a system n of basis vectors a1, a2 , , an . The number of possible apexes of polyhedron equals to the number of combinations Сnm (n – problem measurability, and m = rang(I ) ). Real linear optimization problems that interpret models of candidates selection are characterized by big values of m. In view of this, we have to develop an algorithm ensuring ordered iteration over angular points of the polyhedron. Such a method was developed [ 1, 2 ] and is called simplex method. It allows obtaining the optimum optimization problem solution from the known primary reference plan X 0 , within a finite number of steps. Each iteration step of a simplex method corresponds to competences of the new candidate that improves the target function value. The algorithmic process continues until finding the optimum value of target function or the absence of optimization problem solution.

The number of simplex method iterations is determined by the primary reference plan X0 and the number of angular points I . As there are several “ways” of transition from X0 to the optimum Xopt , we encounter a problem of finding the shortest (in terms of the number of apexes) “way” of iteration. Now there are not any publications with such assessments and their correlation to the classic simplex method algorithm.

The Objective and the Tasks of Research

The research objective provides for development of the algorithm for selecting candidates to an IT project implementation team with use of the classic simplex method for reduction of the number of iterations. For achievement of the objective stated, the following tasks were specified: • Develop the algorithm for selection of IT project implementation personnel with use of simplex method; • Provide model example calculation confirming reduction of the number of iterations as compared with the classic calculation [ 9,10,12 ]. 4

General Statement of a Linear Optimization Problem.

Reference Plan Drafting by Following the Classic Algorithm and by Breaking it

Project activities in the IT sector require formation of an implementing team. The team is a small group (from 3 to 12 persons) having a brightly expressed target orientation and intensive interaction between the team members while fulfilling a joint task. Efficient and fruitful activities of the team in general depend on the competences of each of the team members.

For determining a performer of certain processes, we need to carry out the analysis of (and actually to iterate over) the competences of each of the candidates. The synergetic effect of a joint teamwork is qualitatively higher than the effect of single persons’ activities, i.e. a joint work of specialists can in total give you much more than the results of their individual work.

For large- and medium-scale projects, teams may count tens, hundreds and thousands of participants responsible for particular activities.

The team is the main element of project structure as this is the team who ensures implementation of the project idea. The team leader knows the abilities and skills of the members and uses them for work on the project in accordance with the need. For assurance of efficient high-synergy work of the team, it is necessary first to plan its composition to determine the desired professional characteristics of its members. Most frequently, project managers fail to do it intentionally or replenish the team, as new tasks appear that cannot be solved by efforts of its existing members. In some cases, the project manager composes the team but does not deem it necessary to introduce its members to each other; as a result, the complete composition of the team is only known to the project manager. Such a behaviour shows that there is at least a failure to understand the significance of joint efforts for achievement of the maximum synergy. The main integrating factor of team creation and team activities is the strategic objective of the project implementation [ 15-19 ]. According to this objective, the project manager defines the required number of specialists – team members, their qualification, carries out selection and hiring of employees.

The classic method of team members selection was based on involving professional experts. Advisors were involved for selection of candidates by means of interview. Later, this function was fulfilled through creation of a standard of competences.

For improving the efficiency of this process, it was proposed to use an algorithm based on usage of a simplex method.

Without loss of generality, we may assume to have a standard form of a linear optimization problem record

n WI =  c j x j → max, j=1 n I :  ai j x j  bi , i = 1, j=1 x j  0, j = 1, where b  0, i = 1, 2, i

Adding a balance

xi  0, i = n + 1, n + 2, allow obtaining the canonical recording form of an optimization problem nonnegative variable to each inequality , n + m and recording the problem in a vector form

WI = (c, x) → max, I : (a j , x) = b,

x  0, + x a m m + xm+1am+1 + + xnan = b, or in expanded form:

x1a1 + x2a2 + where a1 =  a11, a21, an+1 = en+1 =  1, 0, x =  x1, x2, , am1 T ,a2 =  a12 , a22 ,

T , 0  , an+2 = en+2 =  0, 1, , xn  T , X  Rn , c =  c1, c2, , cn  ,

T , am2  , , an =  a1n , a2n , , 0 T , , an+m = en+m =  0, 0,

T , amn  , , 1 T , b =  b1, b2 , , bm T .

Vectors an+1,an+2 ,

,an+m are unit vectors. These vectors are linearly independent vectors and constitute the basis. The right sides vector resolution of the optimization problem set of constraints has the following form: b = b1en+1 + b2en+2 + + bmen+m .

As all bi  0 , we obtain the allowable primary reference plan X . The following 0 basis resolution corresponds to the primary plan:

X0 = b1en+1 + b2en+2 + + bmen+m = [0, 0, , 0, b1, b2 , , bm ] .

n

The main idea of using the simplex method-based algorithm is sequential iteration over the competences of a new candidate to become member of an IT project team. One vector is excluded from and another included to the basis by the Gauss-Jordan method.[ 13 ] Subject to compliance with these criteria, we have to build a chain. The beginning of the chain is located at the starting apex X0 of polyhedron I and corresponds to the first simplex table of calculation. Moving to the next candidate X by 1 following the classic algorithm corresponds to transition to the neighbor apex. Actually, each table is a numeric description of apexes I . The process is to be continued till finding the optimum apex Xopt or confirming its absence.

At the arbitrary step of calculation by following the common simplex method algorithm, we have the possibility to move not to the neighbor apex, but to the arbitrary apex located around the optimum apex. Such an apex can be selected based on multiple evaluation methods, e.g. the half-interval method. For this selection, the alternative chain of simplex calculation may have a much smaller number of iterations.

Let us consider a model example of a two-dimensional linear optimization problem solution to confirm this case, first by following the standard procedure and then by breaking the rule of basis vectors combination selection.

Model example

The total competence of candidate Wi consists of several separate competences, with factors determined by the experts x3 , x4 , x5 , x6 . As a result, we obtain a canonical form of a linear optimization problem:

W = 2x1 + 3x2 → max,

I 3x1 − 4x2 + x3 = 6,   x1 + 2x2 + x4 = 12, I :  −x1 + x2 + x5 = 3,  x2 + x6 = 4,

Let us draw the reference simplex table (Tab. 1).

{b j /a ij } 6 3 4 Index row D j has two negative evaluations meaning that plan X0 =  0, 0, 6, 12, 3, 4   is not optimum and can be improved. The pivot col

I umn can be found by the rule of selecting the smallest negative value of evaluations.

X i oFTprhotBeimamisaaaaaaaaaaaaDDDaaaaDniust3431652443626543jjjdjhmeexathrnWWWWoidrIIIIwCd(((002300000300(0000XXXcXat1020Da))))n===b=jbl9010eh4ea(111i1BT136431436sm643829X2aapb2nr.o=e3vg)ea−−−−−:a−−0030130011d320121511t1211i.,vTe4he,ev1−−a0110102000100pa−−4311239l34i2uv,aot3tio,cno0000000011000100a.l000010,u3Pml0anni,Xs001000000001100a000100Wа425I=(,Xa−−−−1s201001430103a1221001000,)o5=n4l,1y41t−h000051101001109.3ai100000,s6 c3o,1l{9ub0243631/j3m,436/a nij0} coXXXniXX102stai0ninost negataiv33e eval0uation D11985 = −5−01. We s0e0lect th1e1 pivot 0r0ow by3t4he con1d0ition19o/3f the smallest siaaaDaaam124624j plexWrIa(230030Xti2o) =fo1r4 pa143b136oii5sitivaei5−1000c131o m0,pio=n0010001e3n,ts4of0000=t000hmeipnivo00011001t39co,lu13m−−10−−121n12.= W3→e−511h3100аa4v.e 3 12 X X2 1 In theD njew WbaI(sXis1), =in9stead of а−54 we in0volve а05 . Aft0er respe3ctive ca0lculation, we have theBfaosaaaaDius3421jrth sWimIC(0032Xpl2e)x= 1t4ab1B341l9e (TabTa.000102a14b)l.e 4. aS0010032implexa10000ta3ble vera01000t4ex X3 a−−3100125 a−1115036 {1b 9j3//a3ij } XX i2 aaaaaaaaDD53325416jj WWII ((00030020XX 30)) == 020 1143634420 −−0010301012 −−1210100043 0000000110 −0100012013 1000000001 1−−−0010100213 34641 XX 30 FroTmhaaet34hiendfoeuxr00trhowtabDle1jX63(8Th3aa=bs.a44−)n3,1:e4g,at1i0v,e00 0e,va3l,u0a10tio,n. Pl10an WXI (3X−41=23)=42,0 4.000, 10, 02, 3, 0X 1 is a 2 3 −1 1 0 0 not oap6timum 0and can 1be impr1oved. O0ur pivo0t column0 will b−e1 а6 , a1s only 1this column contaDi njs neWgIa(tXiv1)e= e9valuation−5D6 = −0 1. We0select t0he pivo3t row b0y the condition of the s ma3allest si0mplex r1a9tio for 0positive0 compo1nents of0 the piv3ot colu m1n. W19e/3have aaaD421j WI (032X 2) = 14 341 0010 0100 0000 1000 −−1012 −1153 3 X 2 0 0 3 2 WI (X 3) = 20 1 4 a 3 a 4 a 2 a 6 D j All eav3aluatio0ns are n1o8nnega−t1ive D 0j  0 . T1his me0ans tha4t we ha0ve found the optimumaaas246olution030. 136 −131 Xopt =010 6, 3 000, WI (Xop001t ) = 21. −−112 001 21 X 1

ThDejreforWeI,(Xth1)e= c9alculation−5within 0the clas0sis sim0plex ca3lculus c0ontains the following cah3ain of s0equentia19l iterati0on over0apexes1I : X0 0→ X1 →3 X2 → X13 → 1X9/o3pt .

Leat4us con0firm that3 breakin0g the c0anonica0l simple1x meth1od algo−r3ithm c3an essentially reda u2ce the3length o4f the c0alculatio1n chain0 – the 0number0 of sim1plex tables. WX 2e are not sae1lecting2the sma1llest ev1aluatio0n like i0n the c0ommon−1 simple1x method, but the biggeDsjt oneW. I R(Xe2s)p=e1c4tive calcu0lation i0s given 0in (Tab0. 6). −2 5 X 1 XXo0pt

X opt X opt The length of calculation chain has been almost twice reduced as X0 → X4 → Xopt .

The problem considered is two-dimensional. Therefore, we can perform a graphical solution providing us with geometric interpretation of the problem calculation chains.

We set up an equation of limit lines At the coordinate origin point, we draw the gradient vector grad(W ) =  2, 3  . I Perpendicularly to it, we draw the level line. Moving the line in parallel to itself in the gradient direction, we set the maximum point Xopt - the apex of the level lines outreach (Fig. 1). The coordinates of the extreme apex are found as coordinates of the crossing point of respective limit lines: The geometric interpretation of the classic simplex calculation consists in the fact that the first simplex table (Tab. 1) corresponds to apex X0 . The calculation up to the second table (Tab. 2) corresponds to transition to the neighbor apex X1 , in the direction of the biggest target function growth. The third, the fourth and the fifth simplex tables (Tab. 3, Tab. 4, Tab. 5) correspond to transition X1 → X2 → X3 → Xopt (Fig. 2). Therefore, for solving the problem by following the classic algorithm, we need to set up five simplex tables. For reducing the number of iterations, we break this algorithm and select not the smallest but the biggest negative evaluation D = −2 in the initial 1 simplex table. The further calculation is given in Table No. 6. As we can see, the number of simplex tables has been reduced from five to three. 5

Research Results Summary

The example considered shows reduction in the number of numeric calculations of an optimization problem based on the method of breaking the standard algorithm. It visually demonstrates reasonability of using optimization problems for determining variations of deviating from canonical algorithms of linear optimization problems solution. From the practical point of view, the proposed approach allows simplifying the calculation complexity of problems on selecting candidates to an IT project implementation team with account taken of their competences.

Based on comparative solutions of a model problem, it has been proved that the number of iterations can be essentially reduced: the classic calculation has five, and in case of breaking the algorithm there are three iterations only.

The research result obtained allows arriving at the conclusion that in a common case, there is a need to search for reasonability of breaking the standard simplex calculation algorithm.

The application value of the proposed approach consists in using the obtained scientific result for assurance of creating an efficient team for IT projects implementation.

Conclusions

It has been determined that using the proposed algorithm in project management is reasonable if applied with breaking the classic method and contributes to acceleration of convergence in the process of obtaining the optimization solution. It has been proved on the example of solving a typical model problem that the proposed approach allows us to essentially reduce the number of iterations. A significant reduction in the computational actions in solving linear optimization problems allows to increase the dimension of the tasks. Such practical expediency stimulates the study of the possibility of constructing more efficient algorithms. The application aspect of the approach proposed is in usage of the obtained research result for providing the possibility to simplify the numeric algorithm based on reducing the number of iterations. This creates conditions for further development and improvement of similar approaches in linear optimization problems. Conference on Computer Sciences and Information Technologies, vol. 2, pp. 127-131 (2018). 17. Pasichnyk V., Shestakevych, T.: The application of multivariate data analysis technology to support inclusive education. In: proceedings of 10th International Conference on Computer Sciences and Information Technologies the International Conference on Computer Sciences and Information Technologies, 88-90 (2015). 18. Holoshchuk, R., Pasichnyk, V., Kunanets, N., Veretennikova, N.: Information modeling of dual education in the field of IT. Advances in Intelligent Systems and Computing, 1080, 637-646 (2020). 19. Odrekhivskyy, M., Pasichnyk, V., Rzheuskyi A., Andrunyk, V., Nazaruk, M., Kunanets, O., Tabachyshyn, D.: Problems of the intelligent virtual learning environment development. CEUR Workshop Proceedings 2386, 359–369 (2019).

References

1. Dantsig , J.: Linear programming and extensions . Progress . Moscow. 600 p. ( 1966 ).

2. Kantorovich , L. , Gorstko A. : Optimum Solutions in Economics . Nauka. Moscow. 227 p. ( 1972 ).

3. Unger , N. , Dempe , S. : Lineare optimierung. Springer. Wiesbaden ( 2010 ).

4. Hetmantsev , V.: Linear algebra and linear programming . Lybid. Kyiv . 250 p. ( 2001 ).

5. Bahaienko , I. , Hryhorkiv , V. , Boichuk , M. , Riumshyn , M. : Mathematic programming . Logos. Kyiv . 266 p. ( 1996 ).

6. Teschl , G. , Teschl, Susanne: Mathematik für informatiker. Band 1: Diskrete mathematik und lineare algebra . Springer. Berlin. ( 2008 ). DOI: 10 .1007/978-3- 540 -77432-7.

7. Buhir , M. : Linear algebra, linear models . Akademia. Kyiv ( 1998 ).

8. Gavurin , M. , Malozemov , V. : Extreme problems with linear constraints . LGU . Leningrad ( 1984 ).

9. Ashmanov , S. : Linear programming . Chief Ed. Board of Phys. & Math. Lit. Moscow ( 1981 ).

10. Sigal , I. , Ivanova , A. : Introduction to applied discrete programming: Models and calculation algorithms . Physmathlit . Moscow ( 2003 ).

11. Romaniuk , T. , Tereshchenko , T. , Prysenko , H. , Horodkova , I. : Mathematic programming . kyiv state university of economics. Kyiv ( 1996 ).

12. Stepaniuk , V.: Methods of mathematic programming . Vyshcha Shkola. Kyiv . ( 1984 ).

13. Titov S. , Chernova , L. : Higher and applied mathematics: training manual: in 2 Parts, P. 1 . Fakt , Kharkiv. 336 p. ( 2017 ).

14. Chernov , S. , Titov , S. , Chernova , Ld., Gogunskii , V. , Chernova , Lb., Kolesnikova , K. : Algorithm for the simplification of solution to discrete optimization problems . East European Journal of Enterprise Technologies 3 /4 ( 93 ), 34 - 43 ( 2018 ).

15. Rzheuskyi , A. , Kunanets , N. , Kut , V. : Methodology of research the library information services: the case of USA university libraries . Advances in Intelligent Systems and Computing II 689 , 450 - 460 . ( 2018 ).

16. Kaminskyi , R. , Kunanets , N. , Rzheuskyi , A. , Khudyi , A. : Methods of statistical research for information managers . In: proceedings of 13th International Scientific and Technical