A two-criteria linear assignment problem is applied to the distribution of medical university students for hospital internships. The optimization goal is to improve the overall level of service by maximizing total grades for the internship. The main criteria selected are the combined academic performance score and the motivational score of students to occupy specific job positions. The stated problem is reduced to the task of predicting grades for the student internship and is solved on the basis of historical data. It also solves a series of ordinary linear assignment problems with prohibitions on some assignments. A computer experiment was designed, and test calculations were conducted. The results showed the efectiveness of using the chosen technique to solve the original problem.
Here, Π is a set of permutation matrices of order [3, 4, 5, 6], where is the number of applicants for the positions and the positions themselves, ∈ +× is the matrix of individual assignments costs. = ∙ → min; ∈ Π .
{ Π = ∈ × ∶ ⋅ = ⋅ = }
, = {0, 1} , = (1, ..., 1) .
LAP is widely used in many theoretical and practical fields, such as scheduling theory, logistics, graph theory, and computational logic, both as a standalone problem and as a subproblem in more complex problems [1, 7, 8].
As a rule, LAP is formulated as a minimization problem but it is also found in the literature as a maximization problem. In this case, LAP has the form assignments on a scale from 0 to 100 score.
Under the constraints (2), where the matrix
∈ ℝ × is the utility matrix and represents the profit
from the assignments, it is clear that LAP (2), (3) can be reduced to the standard LAP (
→ max .
∈ [0, 100] × . ifnally reduce this two-criteria assignment problem to a single-criteria one using the predicted values of grades for practice as the efectiveness metric of the assignments. To solve the problem, methods of multicriteria optimization, linear integer optimization, and statistics, particularly regression analysis, are used. 1.
The classical linear assignment problem (LAP) [2] is the problem of optimizing a linear function on a set of permutation matrices: ∈ = Π , where is a polyhedron of stochastic matrices, which is an integral [3]. This determines the comparative simplicity of solving LAP using linear programming methods compared to other combinatorial problems. Moreover, LAP is polynomially solvable. namely, there is a Hungarian algorithm for solving it with computational complexity ( 3) [9].
Then the transition from LAP (2),(3) to the classical LAP (
→ = [ ] = [100 − ] ∈ [0, 100] × .
As can be seen, the elements of the matrix express the cost of individual assignments on a scale from 0 to 100 points.
In what follows, when we refer to LAP, we mean the classical problem (
× , = 1, are the cost matrices for each criterion.
Finally, the third generalization concerns the presence of additional constraints in addition to the
main constraints (2). So the problem (
By combining the conditions (7) − (9) with (
From a computational point of view, solving these generalizations is much more challenging than LAP. Problems in the NAP and CLAP classes are known to be NP-hard [2, 10, 11]. As for MLAP, we encounter the typical challenges of solving multi-objective optimization problems here. When using standard approaches, such as the weighting method (the linear convolution method) [15, 16, 17] and the priority method [15, 16, 17], additionally addresses the problem of expert assessment and determination of weights of the objective functions representable by a vector
= ( (
{ ′ = [ ′ ],
′ , = , (, ) ∉ ∞, (, ) ∈ .
(7) (8) (9) (10) (11) (12) (13) =1 = ∑ ( ) ( ).
If the priority method is used, then a sequence of CLAPs is solved with one of the criteria (8) and iterative addition of constraints on non-deterioration of higher priority criteria, which are optimized in previous iterations.
Likewise, some CLAPs are reduced to NAPs and sometimes even to LAPs. Thus, the traditional way of solving constrained optimization problems, the penalty method [18], consists of incorporating all or part of additional constraints into the objective function using penalty terms. . In contrast, linear optimization problems turn into nonlinear ones without constraints, i.e., CLAP becomes NAP. If additional constraints express prohibitions on certain pair-wise assignments, then instead of using the penalty method, one can transfer from CLAP to an equivalent LAP of the following form: Here, is the set of pairs (, ) of prohibited assignments, where is the student number and is the job position number. The reducibility of this CLAP to LAP justifies its polynomial solvability, for example, by the Hungarian method [9].
This paper addresses the practical problem of enhancing the level of medical service, which entails solving problems of regression analysis and a finite sequence of CMLAPs. These CMLAPs are reduced to ordinary LAPs by incorporating prohibitions on certain assignments and applying linear convolution of optimization criteria. As a result, we propose an algorithm for solving the formulated complex problem, solvable in polynomial time, depending on the problem dimension , the number of criteria , and the number of periods for which the forecast of the assignment cost matrix is made.
The following practical task is considered: at the end of the academic year, students of medical universities undergo hospital internships. The objective is to assign students to suitable hospital positions to maximize the medical service they provide. A quantitative indicator of the level of service is the grades given to students in hospitals as scores for their internship. These scores, in turn, accumulate patient and staf evaluations of the student performance.
Historical data demonstrates that the level of success of an internship depends on two main indicators.
The first indicator is academic performance, expressed by the factor (the academic score, grade coeficient), which depends on scores in key academic disciplines 1, … , and the average score in all academic disciplines. A higher value of indicates better learning outcomes, increasing the likelihood of the student possessing suficient knowledge to succeed in solving assigned practical problems.
The second indicator is the student’s desire to work in a specific position or hospital, referred to as the motivational factor and assessed by the numerical indicator (the motivation coeficient). A higher indicates higher motivation, suggesting that the student is more likely to succeed in the position entrusted to them.
As can be seen from the formulation, this is the standard linear assignment problem of assigning students to positions, assuming that grades for the internship are known for all students and all job positions: ∗ = ∙ ∗ = min { = ∙ } ,
∈Π minimizing the total cost of the assignment and, as a consequence, maximizing the total eficiency of the final assignment: (14) = [ ], is a matrix of costs of assigning the applicants to the positions, in particular, is the cost of assigning applicant (further a student ), to the position (further a job ). Respectively, Here,
′ ∗ = ∙ ∗ = max { = ∙ } .
∈Π = [ ], is a matrix of eficiency (utility matrix) of assigning the students to the jobs, particularly represents the cost of assigning a student to a job . (15) (16) (17)
However, the challenge arises because grades for the internship will only be given after the students have been assigned to the positions and have completed it. Therefore, the matrix is unknown. In the mathematical model, instead of real estimates (17), only predicted values of these utilities can be used:
→ ̂ = [̂ ], , where ̂ is the forecast utility matrix of assigning the students to the positions, in particular, ̂ is the forecast utility of assigning the applicant to the position .
Thus, instead of the problem (15) we come to the following problem: { ̂∗ = ̂ ∙ ̂∗ = max ̂ = ̂ ∙ ∈Π } , (18) (19) in which the real values of the estimates are replaced by the predicted ones, and the utility matrix is replaced by ̂. Accordingly, the optimal solution to the problem (19) will be the pair ̂∗, ̂∗⟩ , ⟨ where ̂∗ is the predicted matrix of optimal assignments, ̂∗ is the predicted value of the optimal total utility of the assignments ∗.
Assuming that there is historical data on the appointments of previous students to the same positions, their grades in academic disciplines and summer internships for previous years and motivational scores, this forecasting task can be formulated as follows. The goal of the forecast includes searching for the matrix ̂ with the subsequent solution of the problem (19) and consists of finding a forecast matrix of assignments ̂∗, which is close to the optimal matrix of assignments ∗. This goal can be represented as Another metric for comparison
̂∗ ≈ ∗.
̃∗ = ∙ ̂∗ ≈ ̂∗, which we can calculate at the end of the process of acceptance and implementation of the found assignments, when scores for the internship are given, that is, ̃∗ is a posteriori estimate.
Let us introduce some notations: • ∈ 1, is a student index; • ∈ 1, is a position index; • ∈ 1, + 1 is an index of the time period, including 1, is an index of the historical period, + 1 is an index of the current (forecast) period; • ∈ 1, is an index of the key academic discipline; • ℎ ∈ 1, is a hospital type.
As input data for making forecasts, we have: 1. for the forecast + 1-th period and historical periods 1, ..., : a) by the student: i. the score for key academic disciplines for this practice and the average score of the students: = ( )
,, , = ( ), , where ∈ [0, 100] is the score of the student in the key discipline in the period and up to 100 for the best: ii. student ratings of the positions (the motivational factor), starting from 0 for the worst = [ ],, ; b) by the job: where position in the period ; ∈ [0, 100] is the motivational score of the student assigned to the i. their link to the hospitals; ii. the relative weight of disciplines and the average score of them (can be the same for all periods, the same for the positions, the same for the hospitals). For example, the vector of weights:
= ( 1, ..., , ) ∈ + +1, 1 + ... + + = 1, corresponds to the case when these weights are uniform across positions and periods. In particular, is the relative weight of the key academic discipline in the factor , while is the relative weight of the average score in the factor ; iii. intervals of passing scores, both average and in individual disciplines (can be uniform across hospitals and periods).
Let us introduce a constraint: ≤
≤ , ≤ ≤ , ∀, , , .
, are, respectively, the lowest and highest passing scores in the discipline for the occupation of the position in the period , while , are the lowest and highest pass average score for position
during period can also be uniform across the periods and positions within the same hospital. For . These passing scores example, the lower bound on passing academic scores, uniform across all periods, (20) (21) (22) (23) i. score for the practice and position occupied by them (
, , , ) , = 1, ..., .
(24) assigned to the position 3 and received a grade of 85.
For example, , 1, (
,1 1 ) = (2, 3, 85) means that in period = 1, the student 2 was looks like this where position
c) by hospital: i. hospital rating ii. requirements for passing grades a) by student: 2. for previous periods 1, ..., : ≤ , ≤ , ∀, , , ,
is the minimal passing score in the discipline for occupation of the ,
is the minimal passing average score for the position . ii. There are also statistics on which students were appointed to which positions and what grade they received When constructing our mathematical model, we limit our consideration to the cases (21) and (23). The academic performance coeficient looks like this: , which relative weights depend on the = ∑ =1
+ ∈ [0, 100] , ∀, ∈ 1, + 1.
The two main factors of academic achievement and motivation are combined into a single metric: Now, we can find the forecast matrix of total scores adapting (28) as follows: ̂ +1 = [ ̂ +1 ] ; ̂ +1 =̂ +1 +1 + ̂ +1 +1 ∈ [0, 100] , ∀, . In order to incorporate the constraints (23) into the utility matrix, we perform the transition from ′ ′ → = [ ]
′ ; = {
′ , −∞, otherwise (23) holds for all (, , ) ̂ +1 → ̂′ +1 = [ ̂′ +1 ] ; ̂′ +1 = { ̂ ′ +1
, −∞, otherwise (23) holds for all (, ) period , i.e. in the form of a weighted sum of the indicators where , ≥ 0, + = 1, ∀ .
As a result, we obtain a set of matrices of total scores: = ( ,
) and = +
∈ [0, 100] , ∀, , , = [ ] ; = + ∈ [0, 100] , ∀, .
As stated earlier, the weighted sum coeficients are supposed to be known for historical periods ∈ 1, and unknown for the current period + 1. Therefore, under the assumption the vector (25) (26) (27) (28) (29) (30) (31) (32) the matrices {
} to Similarly, = ( ) =1,
= ⋅ + + , ̂
+1 = ⋅ ( + 1) + . on the period . Therefore, we introduce a simple linear regression [19, 20]: is given, while
+1 is unknown, we formulate the auxiliary forecasting problem of assessing +1 (the forecast value is denoted as ̂ +1) as follows: we assume that stochastically linearly depends squares method [19], we can construct the desired forecast: where ,
are regression parameters and is the error. After estimating its parameters by the least Now we solve a series of ordinary LAPs of type (19) with the eficiency matrices: getting a set of auxiliary optimal solutions ⟨ ∗, ∗⟩ , = 1, .
In the same way, the following LAP is solved for the current period + 1: yielding the solution ∗ = ∙ ∗ = max { = ∈Π ∙
} +1,∗ = ̂ +1 ∙ +1,∗ = max ̂ = ̂ +1
∙ ∈Π { }
, ⟨ +1,∗, +1,∗⟩ , = 1, .
(33) (34) for the internship.
The solution (33) is the main result of optimization as it yields the student assignment based on the forecast score for their internship in the form of the matrix +1,∗, while the corresponding entries of the matrix ̂ +1 provide expected internship score of the students given that the assignment given by +1,∗ is implemented. Note that, in this case, the value of +1,∗ yields the expected total score Remark 1. The above scheme of obtaining the assignment solution (33) relies on the known parameters (29). However, the information can be hidden from the decision-maker. In this situation, another set of data given by assumption can be utilized: the historical scores (24) for the internship. We propose to assess the vector (29) solving a set of additional 2-factor linear regressions with a constraint: = + , + = 1, , ≥, = 1, , contains predicted parameters rather than real. where observation is utilized for every , while the values of column of = 1, . Then the above algorithm becomes applicable with the only diference that now the vector and are participate, 4. Experiment design 1. Enter , , ,
′, where ′ is total number of disciplines; 2. To generate the academic score matrices , , ∀ , for each discipline, we set the average scores to the normal distribution: ( ) and the standard deviation ( ),
= 1, ′. The generation is conducted according
∼ ( ( ) , ( )) , ∀, , . arithmetic averages over the columns of the matrix: The first columns of the matrix form the matrix . Next, the matrix-column is filled with =
′ 1 ′ ∑ .
=1 with a given parameters ( ), (
): 4. We will generate matrices of motivational scores { 3. Using the relative weights (21), one can now find the values of the factor }
according to a normal distribution ∼ ( ( ), ( )), ∀, weights and = 1 − known for historical periods. 5. To convolute the academic and motivational points into the combined score , we use the 6. We will set the low bound for the passing score for diferent positions in key academic disciplines and the average academic score. Thus, we do not set the upper bound. We will start from the previously specified mathematical expectation and standard deviation of these values (see (34)), allowing at most specified deviation from the mathematical expectation depending on the standard deviation.
We use the formula (22), where the lower bounds , , ∀ , are calculated by the formula
= max{0, ( ) − ( )}, = min{100, ( )− ( ), ∀ , }, assuming that the parameters { } are given.
(31)).
7. we assess the parameters of the regression (30) and use them for the forecast valuê +1 (see the outlined experimental design scheme.
A test experiment was conducted for the following parameters = 14, = 4, = 5, ′ = 10 and
This paper addresses the practical task of improving medical care services through the internships of medical university students in hospitals. Based on historical data, the main assumption is that student performance is statistically linearly proportional to their academic performance scores and the attractiveness of the positions to the students. A mathematical model of the problem was constructed using multi-objective optimization methods, linear integer optimization, and regression analysis. A computational experiment was designed, and a test calculation for a small-scale problem was conducted to demonstrate the applicability of the proposed approach in solving the original task. man and Hall/CRC, 2023. [2] R. E. Burkard, E. Çela, Linear assignment problems and extensions, in: D.-Z. Du, P. M. Pardalos (Eds.), Handbook of Combinatorial Optimization: Supplement Volume A, Springer US, Boston, MA, 1999, pp. 75–149. doi:10.1007/978-1-4757-3023-4_2.
Theoretic background of computer solution of combinatorial and geometric configuration problems, in: 2021 IEEE 8th International Conference on Problems of Infocommunications, Science and Technology (PIC S&T), IEEE, Kharkiv, Ukraine, 2021, pp. 62–66. [5] O. Matsyi, O. Pichugina, Permutation-matrix approach to optimal linear assignment design, in: Proceedings of the II International Scientific Symposium “Intelligent Solutions” (IntSol-2021), volume 3018 of CEUR Workshop Proceedings, CEUR, Kyiv - Uzhhorod, Ukraine, 2021, pp. 141– 149. URL: ceur-ws.org/Vol-3018/Paper_13.pdf, ISSN: 1613-0073. [6] O. Pichugina, S. Yakovlev, Quadratic optimization models and convex extensions on permutation matrix set, in: N. Shakhovska, M. O. Medykovskyy (Eds.), Advances in Intelligent Systems and Computing IV, volume 1080 of Advances in Intelligent Systems and Computing, Springer International Publishing, Cham, 2020, pp. 231–246. doi:10.1007/978-3-030-33695-0_17, ISSN 2194-5357. [7] O. Pichugina, O. Matsiy, Y. Skob, Performance comparison of unbounded knapsack problem formulations, in: Proceedings of the 7th International Conference on Computational Linguistics and Intelligent Systems. Volume III: Intelligent Systems Workshop, volume 3403 of CEUR Workshop Proceedings, CEUR, 2023, pp. 263–272. URL: https://ceur-ws.org/Vol-3403/paper21.pdf, issn 1613-0073. [8] O. Pichugina, L. Kirichenko, Y. Skob, O. Matsiy, Constraint community detection: modelling approaches with applications, in: Proceedings of the 3rd International Workshop of ITprofessionals on Artificial Intelligence (ProfIT AI 2023), volume 3641 of CEUR Workshop Proceedings, CEUR, 2023, pp. 204–215. URL: https://ceur-ws.org/Vol-3641/paper18.pdf. [9] H. W. Kuhn, The hungarian method for the assignment problem, in: M. Jünger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, L. A. Wolsey (Eds.), 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, Springer, Berlin, Heidelberg, 2010, pp. 29–47. doi:10.1007/978-3-540-68279-0_2. [10] Y. Berstein, J. Lee, S. Onn, R. Weismantel, Parametric nonlinear discrete optimization over well-described sets and matroid intersections, Mathematical Programming 124 (2010) 233–253. doi:10.1007/s10107-010-0358-6. [11] E. Cela, The Quadratic Assignment Problem: Theory and Algorithms, softcover reprint of hardcover 1st ed., Springer US, 2010. [12] Bufardi, Ahmed, On the eficiency of feasible solutions of a multicriteria assignment problem, The Open Operational Research Journal 2 (2008). URL: https://benthamopen.com/ABSTRACT/ TOORJ-2-25. [13] E. K. Mensah, E. Keshavarz, M. Toloo, 10 - finding eficient solutions of the multicriteria assignment problem, in: M. Toloo, S. Talatahari, I. Rahimi (Eds.), Multi-Objective Combinatorial Optimization Problems and Solution Methods, Academic Press, 2022, pp. 193–211. doi:10.1016/B978-0-12-823799-1.00008-5. [14] A. Odior, O. Charles-Owaba, F. Oyawale, Determining feasible solutions of a multicriteria assignment problem., Journal of Applied Sciences and Environmental Management 14 (2010). doi:10.4314/jasem.v14i1.56481, number: 1. [15] Y. Collette, P. Siarry, Multiobjective Optimization: Principles and Case Studies, 2004th ed.,
Springer, 2011. [16] M. Ehrgott, Multicriteria Optimization, Springer-Verlag Berlin and Heidelberg GmbH & Co. KG, 2010. [17] I. Kaliszewski, J. Miroforidis, D. Podkopaev, Multiple Criteria Decision Making by Multiobjective
Optimization: A Toolbox, softcover reprint of the original 1st ed., Springer, 2018. [18] M. Ayodele, Penalty weights in QUBO formulations: Permutation problems, volume 13222, 2022, pp. 159–174. doi:10.1007/978-3-031-04148-8_11. arXiv:2206.11040 [quant-ph]. [19] P. Bruce, A. Bruce, P. Gedeck, Practical Statistics for Data Scientists: 50+ Essential Concepts
Using R and Python, 2nd ed., O’Reilly Media, Beijing Boston Farnham Sebastopol Tokyo, 2020. [20] J. Mandel, The Statistical Analysis of Experimental Data, revised ed., Dover Publications, New York, 1984.