# A Gradient-Based Interior-Point Method to Solve the Many-to-Many Assignment Problems

Authors: Nitish Das; P. Aruna Priya
Journal: Complexity
 (2019)

---

## Abstract

The many-to-many assignment problem (MMAP) is a recent topic of study in the field of combinatorial optimization. In this paper, a gradient-based interior-point method is proposed to solve MMAP. It is a deterministic method which assures an optimal solution. In this approach, the relaxation of the constraints is performed initially using the cardinality constraint detection operation. Then, the logarithmic barrier function (LBF) based gradient descent approach is executed to reach an accurate solution. Experiments have been performed to validate the practical implementation of the proposed algorithm. It also illustrates a significant improvement in convergence speed for the large MMAPs (i.e., if group size,α≥80) over state-of-the-art literature.


---

## Body

## 1. Introduction

Recently, the many-to-many assignment problem (MMAP) has drawn the attention of the researchers in the field of combinatorial optimization. It is the topic of interest because MMAP serves as an authentic model for the activities such as group role assignment, job scheduling, and machine routing, in an organizational structure [1, 2].The performance of an organizational structure depends on its capability of handling a shared task [3]. Role-based collaboration (RBC) plays a vital role in managing a shared task efficiently [3, 4]. In an RBC system, the rating of each constituent agent is performed. Then, a role is assigned to an agent into a particular group based on their rating value [5, 6]. If there exists a one-to-one mapping between a task and an agent, then it is called a linear assignment problem (LAP) or one-to-one assignment problem [7]. Hence, RBC problem is termed as one-to-many assignment problem [6, 7]. Similarly, if a single agent can handle many tasks which are not assigned to any other agent and vice-versa, then a LAP turns into a MMAP by adding the constraint as mentioned earlier [6, 7]. MMAP is also known as the generalized assignment problem.RBC is the widely investigated topic and many exhaustion techniques are proposed to solve it. If an agent is free of tasks in a group, then it can be assigned to any other group to perform a specific task. MMAP takes care of the condition as mentioned earlier. Therefore, MMAP is more appropriate to simulate the real world role assignment problem in an organizational structure as compared with RBC problem [6, 7]. To the best of author’s knowledge, only a few approaches are proposed to solve MMAP in the literature. Hence, this study is confined to create a new framework to solve MMAP.The Kuhn-Munkres (K-M) technique is the most fundamental technique to solve any combinatorial optimization problem. It works well with the rectangular cost matrices where rows are considered as agents and columns are considered as tasks. A back-tracking method is added to the K-M algorithm to solve MMAP [6, 7]. This approach consists of two stages which are as follows: (a) preparation stage; (b) processing stage. In the preparation stage, normalization of the cost matrix is performed for MMAP using the constraints. Then, in the processing stage, reduction of the cost matrix is conducted to allocate agents to tasks efficiently.In literature, Lagrangian bound-based algorithms are explored to solve k-cardinality assignment problem, which is a conjugate dual of the MMAP [8, 9]. In the Lagrangian relaxation approach, the problem is divided into two subproblems which are as follows: “easy” problem and “complicating” problem. The “easy” problem is referred to optimizing the objective function by relaxing the constraints associated with it. The “complicating” problem is stipulated for optimizing the objective function with constraints. In this technique, relaxation of the constraints is performed by embedding a penalty function into the objective function. Hence, the violation of the penalty function is depressed. In the case of the maximization problem, the fixed-multiplier term of objective function sets the upper bound. Further, the semi-Lagrangian technique is developed [8]. It works well when applied to the objective function with the inequality constraints.The convergence speed and accuracy of an algorithm serve as the most prominent parameters while solving MMAP. Hence, a technique with high accuracy and convergence rate is desired.The fundamental heuristic algorithms which operate on the evolutionary principle like the genetic algorithm (GA), particle swarm optimization (PSO), and differential evolution (DE) are explored in the literature to solve a combinatorial optimization problem. GA’s convergence rate decreases while reaching the global optimum, which is a severe drawback [10, 11]. DE and PSO offer high convergence speed but demonstrate a premature convergence, that is a compromise with the accuracy of the obtained solution [12, 13]. On the other hand, the deterministic techniques like interior-point method, and Lagrangian approach have shown promising results for combinatorial problems as they reach the global optimum with high accuracy and convergence rate [14]. The mentioned deterministic approaches are beneficial in addressing a combinatorial as well as a discrete optimization problem [15].The interior-point method is investigated extensively in the literature for solving convex optimization problems (i.e., both linear and nonlinear problems) with inequality constraints [16]. This method follows a linear programming (LP) model which contains a uniquely defined objective function with constraints [17, 18]. The constraints of the objective function are twice continuously differentiable. The interior-point technique performs the relaxation of the constraints of the LP model as a set of boundary conditions surrounding a specific solution region. From the geometric point of view, it moves towards a solution from either the exterior of the solution region or the interior of the solution region [16, 17]. The barrier method, such as the logarithmic barrier function (LBF) approach, is the fundamental type of interior-point technique explored in the literature [16].Therefore, an interior-point method is adopted to solve MMAP. In the proposed technique, the relaxation of the constraints is performed initially using the cardinality constraint detection operation. Then, the LBF-based gradient descent approach is executed to obtain an optimal solution.Experiments are performed to substantiate the feasibility of the proposed algorithm and its comparative performance analysis with the existing literature [7] is made. It requires only a limited number of iterations to perform the complete search. Therefore, the proposed algorithm outperforms for the large MMAPs (i.e., if group size, α≥80) as compared with [7]. The computation time for each of its iteration is larger than [7]. Therefore, it offers a comparatively large convergence period w.r.t. [7] for the small MMAPs. Thus, the practical implication of the proposed algorithm is to solve the machine routing and scheduling problem in Manufacturing-based organizations [1, 2].The rest of the paper is regulated as follows. Section2 consists of problem formulation. The framework for the gradient-based interior-point method is described in Section 3. Section 4 presents the experimental setup for the proposed work and its comparative analysis with the state-of-the-art literature. In the end, conclusions are devised in Section 5.


## 2. Research Problem Formulation

A graphGmatch=(Vmatch,Ematch), where Vmatch represents the nodes and Ematch denotes the edges, is described as a bipartite graph, if it satisfies the criteria such as Vmatch=Xmatch∪Ymatch and Xmatch∩Ymatch=ϖ, where ϖ is a null set, and Ematch⊆Xmatch×Ymatch [7].A bipartite graphGmatch is described as a weighted bipartite graph if its every edge (i.e., Ematch) consists of a weight (i.e., w(i,j)) [7]. The weight of one-to-one matching (i.e., Mmatch) is described in (1).(1)wMmatch=∑Ematch∈MmatchwEmatchA matching (i.e.,Mmatch) is called a perfect matching, if each node of Xmatch is assigned to one of the Ymatch nodes. Therefore, a linear assignment problem (LAP) is defined as determining a perfect matching in Gmatch which is maximally weighted [7]. In this paper, it is considered that there are α agents and β tasks.Let an ability limit vector ofα agents be Λ. Here, an element Λi indicates the number of tasks that can be maximally assigned to an agent i (i.e., 0≤i<α) [7].Let a task range vector ofβ tasks be Γ. Here, an element Γj represents the quantity of task j (i.e., 0≤j<β) which are needed to be assigned [7].Let a potential matrix,ϱ, be an α×β matrix, where ϱij∈[0,1] denotes a potential value of an agent i for the task j. Hence, ϱij=1 represents the highest value, while 0 represents the least value for a particular element.Let an assignment matrix,ω, be defined as α×β matrix, where ωij opts only the binary labels (i.e., 0 or 1). Hence, ωij=1 which denotes agent i is assigned to task j, whereas ωij=0 symbolizes agent i is not assigned to task j.Let an agenti (i.e., 0≤i<α) can execute many but different tasks. Similarly, let a task j (i.e., 0≤i<β) can be assigned to many but different agents. A LAP turns into a many-to-many assignment problem by adding the two constraints, as mentioned earlier. From literature [7], a many-to-many assignment problem is thus defined mathematically by (2).(2)max⁡λ=∑i=0α-1∑j=0β-1ϱij×ωijwith the constraints as given in (3), (4), and (5).(3)ωij∈0,1where0≤j<βand0≤i<α(4)∑j=0β-1ωij≤Λiwhere0≤i<α(5)∑i=0α-1ωij=Γjwhere0≤j<β


## 3. Methodology

Initially, the potential matrixϱ of dimension α×β is created. Hence, each element of ϱ denotes the efficiency of a particular agent (i.e., out of α agents) performing a specific task (i.e., out of β tasks). Then, Λ and Γ are defined according to the problem constraints. In literature [7], it is proven in Theorem 6 (i.e., Decidable theorem) that MMAP becomes unsolvable, when the inequality defined by (6) occurs.(6)∑i=0α-1Λi<∑j=0β-1ΓjThus, it becomes mandatory to perform cardinality constraint detection (CCD) to avoid the condition described in (6). Therefore, CCD is performed using (7).(7)∑i=0α-1Λi≥∑j=0β-1ΓjThe cardinality ofΛ is always greater than or equal to the cardinality of Γ after performing CCD. Hence, matrix ϱ of dimension α×β is expanded into a matrix ϱ_extend of dimension η×η, where η=∑i=0α-1‍Λi using Λ and Γ. The new columns of ϱ_extend are appended with zeroes. It is expressed in (8), where an agent i contains Λi rows in ϱ_extend and the task j contains Γj columns in ϱ_extend.(8)max⁡λ=∑i=0η-1∑j=0η-1ϱ_extendij×ωijwhereη=∑i=0α-1ΛiFrom the literature [9], the concept of conjugate duality is used to transform the objective function for maximization (i.e., (8)) into a minimization problem. A dual-parameter μ is defined by (9) because the elements of ϱ_extend vary from 0 to 1.(9)μij=1-ϱ_extendijBy applying (9) into (8), the objective function reduces to (10).(10)min⁡λdual=∑i=0η-1∑j=0η-1μij×ωij=costωLet a graphGmap defined by Gmap=(Vmap,Emap), characterizes Equation (10). Thus, η denotes the total number of nodes in it. In the graph Gmap, Emap ( i.e., μij) symbolizes the edge weights between the specific nodes (i.e., between an agent i and a task j), and Vmap ( i.e., column vectors of ω) denotes the set of nodes. Therefore, each node ∈Vmap, represents a specific state code as ωij can take only binary labels.In the field of circuit design, the hypercube embedding based techniques, such as HARD [19] and Improved-FSMIM [20], are developed for hardware optimization. These techniques have never been examined to solve a generalized assignment problem such as MMAP. To the best of author’s knowledge, the proposed work makes the first attempt to address the MMAP by employing the hypercube embedding process, which proves its novelty.Let a hypercube be characterized asϕν=(Vϕ,Eϕ), where ν is the dimension, Vϕ is the set of vertices of ϕν, and Eϕ is the set of edges of ϕν [21]. The total number of elements present in Eϕ and Vϕ, are defined by (11) and (12).(11)Eϕ=Vϕ×ν2=2ν-1×ν(12)Vϕ=2νThe hypercube embedding is applied to minimize (10). It is executed from graph Gmap into the hypercube ϕν [21, 22]. It is symbolized as ω:Vmap→Vϕ. It is a 1 to 1 mapping function. Hence, if a node i of graph Gmap is represented by a particular binary state code, then the corresponding vertex of the hypercube (i.e., ki) is denoted by the same code. Therefore, η-binary ν-vectors are defined by (13).(13)ki∈k:k∈0,1νwherei∈Vmapi.e.,columnvectorsofωIn the hypercubeϕν, distij (where i,j∈Vmap) symbolizes the Hamming distance between the vertices ki and kj. The pictorial representation for evaluation of distij is given in [20]. Its mathematical representation is shown in Equation (14), where ϑij is the instantaneous value of kij. ϑij value varies between -1 and 1 (a detailed description is provided in Section 3.1). Therefore, the cost function of this embedding process is given in (15) and (16).(14)distij=∑ξ=1νϑiξ-ϑjξ2where,kij=1ifϑij≥00ifϑij<0(15)costω=∑i=0η-1∑j=0η-1μij×distij(16)costω=∑i=0η-1∑j=0η-1∑ξ=1νμij×ϑiξ-ϑjξ2Thus, minimizing the cost function presented in (16) becomes the ultimate goal for solving the MMAP.The convergence speed and accuracy of an algorithm serve as the most prominent parameters while solving the MMAP. Hence, a technique with high accuracy and convergence rate is chosen to minimize the cost function given in (16).The basic heuristic algorithms which operate on the evolutionary principle like the genetic algorithm (GA), particle swarm optimization (PSO), and differential evolution (DE) are explored in the literature to solve a combinatorial optimization problem. GA’s convergence rate decreases while reaching the global optimum, which is a severe drawback [10, 11]. DE and PSO offer high convergence speed but demonstrate a premature convergence, that is a compromise with the accuracy of the obtained solution [12, 13]. On the other hand, the deterministic techniques like interior-point method and Lagrangian approach have shown promising results for combinatorial problems as they reach the global optimum with high accuracy and convergence rate [14]. The mentioned deterministic approaches are beneficial in addressing a combinatorial as well as a discrete optimization problem [15]. The barrier method, such as the logarithmic barrier function (LBF) approach, is the fundamental type of interior-point technique explored in literature [16]. Hence, the LBF-based gradient descent technique is selected to minimize the cost function given in (16). The steps involved in the proposed gradient-based interior-point approach are presented in Figure 1.Figure 1
Flow chart for the proposed gradient-based interior-point method.


### 3.1. Logarithmic Barrier Function Based Gradient Descent Approach

An interior-point method, such as logarithmic barrier function method (LBF), is widely investigated to solve discrete optimization problems [14, 23]. It is a deterministic technique that guarantees a feasible solution. The cost function for MMAP is formulated using LBF. Then, its minimization is performed using the gradient-projection technique in an iterative manner. In the LBF method, optimization of the objective function is accomplished in the continuous space domain. The obtained analytic solution is then discretized to produce the exact discrete solution [24]. Thus, the objective function for LBF, which is subjected to inequality constraints, is defined by (17).(17)minfϑs.t.,constraintiϑ≥0,i=1,2,…,uLBF to reduce the objective function (as given in (16)) is presented in (18). Its representation at the iteration iter_t is shown in (19). In (18) and (19), the second term acts as a barrier for any move that excludes constraint (i.e., constrainti(ϑ)) [25].(18)minρϑ,χ=fϑ+χ∑i=1uloge⁡constraintiϑ(19)minρϑ,χiter_titer_t=fϑ+χiter_t∑i=1uloge⁡constraintiϑAt the initial stage, LBF choosesχ0>0 and a feasible ϑ0. It selects χiter_t+1=θ·χiter_t, where θ<1. The process continues until χiter_t arrives at a substantially small value.A line search method is essential to reduce (19) w.r.t. ϑ iteratively. The first-order gradient descent approach is pertinent for this purpose [26]. In this method, weight vectors (i.e., the model parameters) are determined to reduce the objective function [27, 28]. Its mathematical representation is given in (20).(20)minρϑ,χs.t.,τϑ=0In the first-order gradient descent method, a particular iteration (i.e.,iter_t) is defined by (21), where ψ represents the step size. A small positive real number is selected as ψ value [26].(21)ϑ←ϑ-ψ∇ρϑ,χFrom (21), small moves (i.e., with a step size ψ) are made in negative direction of the gradient. At the next iteration (i.e., ϑ(iter_t+1)), (22) is employed to determine ϑ value over the constraint surface.(22)ϑ←ϑτϑ=0The convergence norm for the proposed gradient-based interior-point method is given in (23), where σ (ranges from 0 to 1) is the upper bound.(23)ϑiter_t+1-ϑiter_t<σHence, the hypercube embedding problem is interpreted as determiningη-binary ν-vectors that minimizes (16). It is given in (24).(24)ϑi∈ϑ:ϑ∈Rν&ϑ2=1;wherei∈Vmapandϑ2indicatesthenormalizedvalueofϑThus, (16) is deduced using Hamming distance between vertices of the hypercube (i.e., ϕν). It is presented in (25).(25)costω=∑i=0η-1∑j=0η-1μij×ϑi-ϑj2where,ϑi=ϑi1,ϑi2,…,ϑiνTϑi-ϑj2=∑ξ=1νϑiξ-ϑjξ2In this optimization problem, any two vertices of the hypercube (i.e.,ϕν) should not be defined by the same binary state code (i.e., ϑi-ϑj≠0). This condition serves as a constraint for this optimization process. It is given in (26).(26)constraintϑ=ϑi-ϑj2>0Equations (25) and (26) are applied into (18) to reduce the cost function. The reduced cost function is given in (27).(27)minρϑ,χ=∑i=0η-1∑j=0η-1μij×ϑi-ϑj2+χ∑i=0η-1∑j=0η-1loge⁡ϑi-ϑj2Therefore, the entityτ(ϑ) (from (22)) is defined by (28).(28)τϑ=ϑ12-1,ϑ22-1,…,ϑη2-1Ts.t.ϑ=ϑ1,ϑ2,…,ϑηTϑi=ϑi1,ϑi2,…,ϑiνT;whereeachϑi1≤i≤ηFrom (21), the computation of the derivative term (i.e., ∇ρ(ϑ,χ)) is essential to approach towards the gradient descent direction. The required derivative term is deduced by substituting (29), (30), (31), and (32) into (27). Hence, ∇ρ(ϑ,χ) is defined by (33).(29)∂∂ϑiϑi-ϑj2=2ϑi-ϑj(30)∂∂ϑjϑi-ϑj2=2ϑj-ϑi(31)∂∂ϑiloge⁡ϑi-ϑj2=2ϑi-ϑjϑi-ϑj2(32)∂∂ϑjloge⁡ϑi-ϑj2=2ϑj-ϑiϑi-ϑj2(33)∇ρϑ,χ=2∑j=1ημ1j×ϑ1-ϑj+χ∑j=1ηϑ1-ϑjϑ1-ϑj2∑j=1ημ2j×ϑ2-ϑj+χ∑j=1ηϑ2-ϑjϑ2-ϑj2⋯⋯⋯∑j=1ημηj×ϑη-ϑj+χ∑j=1ηϑη-ϑjϑη-ϑj2By applying (28) into (22), ϑ in its normalized form is given in (34).(34)ϑτϑ=0=ϑ1ϑ1ϑ2ϑ2⋯⋯ϑηϑηAt the end of the gradient descent iterative process (i.e., when (23) is satisfied), discretization of the analytic solution is performed. Hence, a set of optimal state codes (i.e., ω∗) is determined by discretizing ϑ^ij (i.e., value of ϑ at the iteration σ) by (35).(35)k^ij=1ifϑ^ij≥00ifϑ^ij<0The pseudocode for the proposed gradient-based interior-point method is conferred in Algorithm1.Algorithm 1:A Gradient based interior point method.
Input: Λ i ,  Γ j and potential matrix (i.e., ϱ) Output: ω ∗ (i.e., the final solution) begin Initialization: ω   ← O n e   h o t   e n c o d e d   c o d e s ;   χ ← i n i t i a l _ χ; Cardinality constraint detection is performed using Equation (7); Expansion of the potential matrix (i.e.,ϱ) is executed using Equation (8); Conversion of the objective function into a minimization problem (i.e., Equation (10)) is conducted using Equation (9); Hypercube embedding is performed & objective function is defined by Equation (16); while (χ>final_χ)do/∗Start the LBF-based gradient projection method∗/ repeat for i t e r _ t ← 1   t o   σ ϑiter_t←ϑ(iter_t-1)-ψ{∇ρ(ϑ,χ)}; /∗ by Equation (21) and Equation (33)∗/ end return ϑ ^ i j (i.e., ϑ value when iter_t=σ); evaluate k ^ i j = 1 ,   i f   ϑ ^ i j ≥ 0 ;   0 ,   i f   ϑ ^ i j < 0 / ∗ by Equation (35) ∗ / Computecost for the new value of ω by Equation (16); case: c o s t ( ω i t e r _ t - 1 ) ≥ c o s t ( ω i t e r _ t ) then update,ω∗←ωiter_t; case: c o s t ( ω i t e r _ t - 1 ) < c o s t ( ω i t e r _ t ) then update,ω∗←ωiter_t-1; end case untilthe gradient based interior point method converges χ←θ⋅χ; end return ω ∗; end


## 3.1. Logarithmic Barrier Function Based Gradient Descent Approach

An interior-point method, such as logarithmic barrier function method (LBF), is widely investigated to solve discrete optimization problems [14, 23]. It is a deterministic technique that guarantees a feasible solution. The cost function for MMAP is formulated using LBF. Then, its minimization is performed using the gradient-projection technique in an iterative manner. In the LBF method, optimization of the objective function is accomplished in the continuous space domain. The obtained analytic solution is then discretized to produce the exact discrete solution [24]. Thus, the objective function for LBF, which is subjected to inequality constraints, is defined by (17).(17)minfϑs.t.,constraintiϑ≥0,i=1,2,…,uLBF to reduce the objective function (as given in (16)) is presented in (18). Its representation at the iteration iter_t is shown in (19). In (18) and (19), the second term acts as a barrier for any move that excludes constraint (i.e., constrainti(ϑ)) [25].(18)minρϑ,χ=fϑ+χ∑i=1uloge⁡constraintiϑ(19)minρϑ,χiter_titer_t=fϑ+χiter_t∑i=1uloge⁡constraintiϑAt the initial stage, LBF choosesχ0>0 and a feasible ϑ0. It selects χiter_t+1=θ·χiter_t, where θ<1. The process continues until χiter_t arrives at a substantially small value.A line search method is essential to reduce (19) w.r.t. ϑ iteratively. The first-order gradient descent approach is pertinent for this purpose [26]. In this method, weight vectors (i.e., the model parameters) are determined to reduce the objective function [27, 28]. Its mathematical representation is given in (20).(20)minρϑ,χs.t.,τϑ=0In the first-order gradient descent method, a particular iteration (i.e.,iter_t) is defined by (21), where ψ represents the step size. A small positive real number is selected as ψ value [26].(21)ϑ←ϑ-ψ∇ρϑ,χFrom (21), small moves (i.e., with a step size ψ) are made in negative direction of the gradient. At the next iteration (i.e., ϑ(iter_t+1)), (22) is employed to determine ϑ value over the constraint surface.(22)ϑ←ϑτϑ=0The convergence norm for the proposed gradient-based interior-point method is given in (23), where σ (ranges from 0 to 1) is the upper bound.(23)ϑiter_t+1-ϑiter_t<σHence, the hypercube embedding problem is interpreted as determiningη-binary ν-vectors that minimizes (16). It is given in (24).(24)ϑi∈ϑ:ϑ∈Rν&ϑ2=1;wherei∈Vmapandϑ2indicatesthenormalizedvalueofϑThus, (16) is deduced using Hamming distance between vertices of the hypercube (i.e., ϕν). It is presented in (25).(25)costω=∑i=0η-1∑j=0η-1μij×ϑi-ϑj2where,ϑi=ϑi1,ϑi2,…,ϑiνTϑi-ϑj2=∑ξ=1νϑiξ-ϑjξ2In this optimization problem, any two vertices of the hypercube (i.e.,ϕν) should not be defined by the same binary state code (i.e., ϑi-ϑj≠0). This condition serves as a constraint for this optimization process. It is given in (26).(26)constraintϑ=ϑi-ϑj2>0Equations (25) and (26) are applied into (18) to reduce the cost function. The reduced cost function is given in (27).(27)minρϑ,χ=∑i=0η-1∑j=0η-1μij×ϑi-ϑj2+χ∑i=0η-1∑j=0η-1loge⁡ϑi-ϑj2Therefore, the entityτ(ϑ) (from (22)) is defined by (28).(28)τϑ=ϑ12-1,ϑ22-1,…,ϑη2-1Ts.t.ϑ=ϑ1,ϑ2,…,ϑηTϑi=ϑi1,ϑi2,…,ϑiνT;whereeachϑi1≤i≤ηFrom (21), the computation of the derivative term (i.e., ∇ρ(ϑ,χ)) is essential to approach towards the gradient descent direction. The required derivative term is deduced by substituting (29), (30), (31), and (32) into (27). Hence, ∇ρ(ϑ,χ) is defined by (33).(29)∂∂ϑiϑi-ϑj2=2ϑi-ϑj(30)∂∂ϑjϑi-ϑj2=2ϑj-ϑi(31)∂∂ϑiloge⁡ϑi-ϑj2=2ϑi-ϑjϑi-ϑj2(32)∂∂ϑjloge⁡ϑi-ϑj2=2ϑj-ϑiϑi-ϑj2(33)∇ρϑ,χ=2∑j=1ημ1j×ϑ1-ϑj+χ∑j=1ηϑ1-ϑjϑ1-ϑj2∑j=1ημ2j×ϑ2-ϑj+χ∑j=1ηϑ2-ϑjϑ2-ϑj2⋯⋯⋯∑j=1ημηj×ϑη-ϑj+χ∑j=1ηϑη-ϑjϑη-ϑj2By applying (28) into (22), ϑ in its normalized form is given in (34).(34)ϑτϑ=0=ϑ1ϑ1ϑ2ϑ2⋯⋯ϑηϑηAt the end of the gradient descent iterative process (i.e., when (23) is satisfied), discretization of the analytic solution is performed. Hence, a set of optimal state codes (i.e., ω∗) is determined by discretizing ϑ^ij (i.e., value of ϑ at the iteration σ) by (35).(35)k^ij=1ifϑ^ij≥00ifϑ^ij<0The pseudocode for the proposed gradient-based interior-point method is conferred in Algorithm1.Algorithm 1:A Gradient based interior point method.
Input: Λ i ,  Γ j and potential matrix (i.e., ϱ) Output: ω ∗ (i.e., the final solution) begin Initialization: ω   ← O n e   h o t   e n c o d e d   c o d e s ;   χ ← i n i t i a l _ χ; Cardinality constraint detection is performed using Equation (7); Expansion of the potential matrix (i.e.,ϱ) is executed using Equation (8); Conversion of the objective function into a minimization problem (i.e., Equation (10)) is conducted using Equation (9); Hypercube embedding is performed & objective function is defined by Equation (16); while (χ>final_χ)do/∗Start the LBF-based gradient projection method∗/ repeat for i t e r _ t ← 1   t o   σ ϑiter_t←ϑ(iter_t-1)-ψ{∇ρ(ϑ,χ)}; /∗ by Equation (21) and Equation (33)∗/ end return ϑ ^ i j (i.e., ϑ value when iter_t=σ); evaluate k ^ i j = 1 ,   i f   ϑ ^ i j ≥ 0 ;   0 ,   i f   ϑ ^ i j < 0 / ∗ by Equation (35) ∗ / Computecost for the new value of ω by Equation (16); case: c o s t ( ω i t e r _ t - 1 ) ≥ c o s t ( ω i t e r _ t ) then update,ω∗←ωiter_t; case: c o s t ( ω i t e r _ t - 1 ) < c o s t ( ω i t e r _ t ) then update,ω∗←ωiter_t-1; end case untilthe gradient based interior point method converges χ←θ⋅χ; end return ω ∗; end


## 4. Numerical Results and Discussions

The fundamental goal of this numerical study is to substantiate the feasibility of the proposed algorithm and to demonstrate the comparison with the state-of-the-art literature [7]. All optimizations are performed using Eclipse Kepler JDK 1.7 package [7]. The workstation configuration to perform computations is as follows: Intel(R) Core i7 (6th Gen), 16 GB RAM and 3.5 GHz CPU.The proposed approach is a deterministic approach. Therefore, its convergence period for optimal assignment is constant. Experiments are performed between two random groups (whereϱij∈[0,1]) to validate its feasibility. For Λi range, such as [1,3], [1,4], and [1,6], the Γj range is set to [1,2α/β], where mid_value←2, to present the comparison with [7].Similarly, forΛi range [1,5], the Γj range is set to [1,3α/β], where mid_value←3, to present the comparison with [7]. Simulations are performed to evaluate the cost for optimal assignment and convergence time for different combinations of α,β, and Λi range. The cost for a particular assignment matrix is evaluated using (16). The convergence plot for different combinations of α,β, and Λi range is presented in Figure 2. A parameter, successrate, is also defined which provides the average of successful assignments within 100 iterations. It is presented in Table 1. The successrate ranges from 95.78 to 100%. It indicates that the proposed algorithm takes only a limited number of iterations to converge.Table 1
The convergence times andsuccess rate for different combinations of α,β, and Λi range.
α β Λ i success rate Converg. α β Λ i success rate Converg. range % time (ms) range % time (ms) 5 5 [ 1,3 ] 100 0.087 5 5 [ 1,5 ] 99.91 0.18 5 10 [ 1,3 ] 100 0.114 5 10 [ 1,5 ] 98.87 0.194 5 20 [ 1,3 ] 99.39 0.101 5 20 [ 1,5 ] 98.65 0.242 5 50 [ 1,3 ] 100 0.119 5 50 [ 1,5 ] 97.34 0.237 10 5 [ 1,3 ] 99.27 0.147 10 5 [ 1,5 ] 98.21 0.252 10 10 [ 1,3 ] 99.23 0.141 10 10 [ 1,5 ] 98.2 0.27 10 20 [ 1,3 ] 99.12 0.156 10 20 [ 1,5 ] 98.06 0.301 10 50 [ 1,3 ] 100 0.177 10 50 [ 1,5 ] 98.03 0.371 15 5 [ 1,3 ] 99.04 0.151 15 5 [ 1,5 ] 97.97 0.354 15 10 [ 1,3 ] 98.97 0.193 15 10 [ 1,5 ] 97.89 0.386 15 20 [ 1,3 ] 98.94 0.197 15 20 [ 1,5 ] 98.48 0.382 15 50 [ 1,3 ] 98.47 0.28 15 50 [ 1,5 ] 97.54 0.347  5 5 [ 1,4 ] 98.34 0.096 5 5 [ 1,6 ] 97.41 0.203 5 10 [ 1,4 ] 98.32 0.11 5 10 [ 1,6 ] 97.38 0.239 5 20 [ 1,4 ] 98.18 0.106 5 20 [ 1,6 ] 96.88 0.217 5 50 [ 1,4 ] 98.69 0.117 5 50 [ 1,6 ] 96.67 0.319 10 5 [ 1,4 ] 97.95 0.123 10 5 [ 1,6 ] 98.81 0.267 10 10 [ 1,4 ] 97.83 0.147 10 10 [ 1,6 ] 96.6 0.336 10 20 [ 1,4 ] 97.56 0.18 10 20 [ 1,6 ] 97.62 0.293 10 50 [ 1,4 ] 98.44 0.156 10 50 [ 1,6 ] 96.5 0.337 15 5 [ 1,4 ] 97.29 0.185 15 5 [ 1,6 ] 96.3 0.384 15 10 [ 1,4 ] 99.25 0.163 15 10 [ 1,6 ] 95.78 0.406 15 20 [ 1,4 ] 97.1 0.159 15 20 [ 1,6 ] 96.23 0.445 15 50 [ 1,4 ] 96.17 0.29 15 50 [ 1,6 ] 96.16 0.452Figure 2
Convergence plot for different combinations ofα,β, and Λi range.
(a) (b) (c) (d)Another set of analysis is conducted to determine the overall performance (forα ranging from 20 to 300) of the proposed algorithm. Experiments are performed between 100 random groups (where ϱij∈[0,1]). Simulations are run to evaluate the cost for optimal assignment and convergence time for three combinations (i.e., (α,β←α), (α,β←α/2), and (α,β←α/3)) with various Λi range. The cost for a particular assignment matrix is evaluated using (16). The convergence analysis of the proposed algorithm for Λi∈[1,3] and [1,5] are shown in Figure 3. For Λi range, such as [1,3], [1,4], [1,6], and [1,7], the Γj range is set to [1,2α/β],wheremid-value←2. Similarly, for Λi range, [1,5], the Γj range is set to [1,3α/β],where, mid-value←3, to present the comparison with [7]. The performance measures using the convergence time for various Λi range is presented in Tables 2 and 3. An analysis of computation time required for the optimal assignment is presented in Figure 4. Therefore, the performance of the proposed algorithm in comparison with [7] when Λi∈[1,3] and [1,5] are shown in Figure 5.Table 2
Performance measures in terms of convergence time for variousΛi range.
α β Convergence time (ms) for various Λ i range [ 1,3 ] [ 1,4 ] [ 1,5 ] [ 1,6 ] [ 1,7 ] 20 α 1.5 1.53 3.05 3.35 5.01 α / 2 3.91 2.5 3.91 6.67 6.7 α / 3 2.56 4.19 6.74 8 9.46  40 α 2.49 2.39 11.96 22.27 25.47 α / 2 15.09 15.43 30.2 25.42 28.67 α / 3 6.24 8.73 51.99 38.21 67.68  60 α 3.47 11.54 29.37 43.08 215.78 α / 2 45.08 58.75 93.77 35.53 222.17 α / 3 10.4 13.1 103.97 109.42 226.11  80 α 5.66 25.8 63.88 148.13 260.1 α / 2 64.6 87.19 126.34 138.86 327.09 α / 3 22.41 26.41 211.65 214.94 378.63  100 α 10.93 54.1 124.86 336.19 517.8 α / 2 104.36 158.86 286.24 417.04 594.34 α / 3 28.03 39.7 314.03 319.75 600.45  120 α 21.94 74.21 175.46 437.63 747.46 α / 2 175.39 271.75 404.09 653.25 1017.74 α / 3 37.65 66.33 567.18 528.19 1190.04  140 α 46.59 133.76 298.22 732.7 1412.76 α / 2 226.04 349.16 571.05 840.7 1337.31 α / 3 50.37 103.49 805.83 826.76 2330.55Table 3
Performance measures in terms of convergence time for variousΛi range.
α β Convergence time (ms) for various Λ i range [ 1,3 ] [ 1,4 ] [ 1,5 ] [ 1,6 ] [ 1,7 ] 160 α 70.81 172.6 392.73 943.3 1928.53 α / 2 371.03 554.58 934.28 1329.13 2070.21 α / 3 206.33 521.98 1834.04 4182.59 11774.68  180 α 95.94 271.51 614.03 1387.2 3025.63 α / 2 385.72 583.6 1103.61 1394.25 2179.26 α / 3 361.22 1002.62 2829.37 7899.4 22248.78  200 α 120.55 302.94 685.8 1510.65 3368.68 α / 2 575.91 894.46 1486.22 2143.75 3339.83 α / 3 387.91 1048.01 3094.74 8403.4 23672.39  220 α 125.25 298.88 675.04 1497.18 3350.68 α / 2 703.4 1093.11 1860.01 2628.96 4081.13 α / 3 585.1 1633.06 4717.64 13059.29 36823.85  240 α 158.35 352.81 799.02 1768.21 3916.86 α / 2 903.46 1399.31 2250.16 3355.76 5206.06 α / 3 726.87 2020.59 6428.67 16192.45 45616.99  260 α 182.88 419.81 941.7 2135.22 4694.84 α / 2 1058.77 1631.79 2595.69 3919.32 6101.87 α / 3 788.25 2218.62 6989.23 17728.56 49945.42  280 α 202.38 591.12 1329.22 2889.11 6598.76 α / 2 1234.98 1907.92 3179.06 4567.74 7133.22 α / 3 1105.22 3115.55 9123.93 25077.61 70553.6  300 α 272.68 646.28 1434.9 3148.24 7216.9 α / 2 1452.65 2239.31 3608.83 5386.14 8353.25 α / 3 1324.04 3753.62 11225.06 30067.39 84718.73Figure 3
Convergence analysis of the proposed algorithm forΛi∈[1,3]&[1,5].
(a) (b) (c) (d) (e) (f)Figure 4
Performance evaluation of the proposed algorithm in terms of convergence time for variousΛi range.
(a)
Forβ=α (b)
Forβ=α/2 (c)
Forβ=α/3Figure 5
The performance of the proposed algorithm in comparison with the state-of-the-art literature whenΛi∈[1,3]&[1,5].
(a)
Forβ=α when Λi∈[1,3] (b)
Forβ=α/2 when Λi∈[1,3] (c)
Forβ=α/3 when Λi∈[1,3] (d)
Forβ=α when Λi∈[1,5] (e)
Forβ=α/2 when Λi∈[1,5] (f)
Forβ=α/3 when Λi∈[1,5]The proposed technique optimally defines the most feasible solution region. Hence, only a limited number of iterations are required to perform the complete search. Therefore, the proposed algorithm outperforms for the large MMAPs (i.e., if group size,α≥80) as compared with [7].The comparative analysis presented in Figure5 indicates that each iteration of the proposed technique requires a substantial computation time as compared with [7]. Therefore, it offers a comparatively large convergence period w.r.t. [7] for the small MMAPs. It is a limitation of the proposed approach.The problem of machine routing and scheduling is the primary issue in manufacturing-based industries. The mentioned problems become severe in the multisite manufacturing organizations when the number of operators working on a shared task is large [1, 2]. Therefore, the practical implication of the proposed algorithm is to solve the machine routing and scheduling problem in Manufacturing-based organizations. The proposed technique can also be investigated to create reconfigurable FSM-based architecture efficiently [29].


## 5. Conclusion

The framework for a gradient-based interior-point method to solve the many-to-many assignment problem (MMAP) is proposed in this study. It is a deterministic approach which assures an optimal solution. At the initial stage of this approach, the relaxation of the constraints is performed using the cardinality constraint detection operation. Then, the logarithmic barrier function (LBF) based gradient descent approach is executed to obtain an optimal solution for MMAP. The proposed technique requires only a limited number of iterations to perform the complete search. Therefore, the proposed algorithm outperforms for the large MMAPs (i.e., if group size,α≥80) as compared with the existing literature. The practical implication of the proposed algorithm is to solve the machine routing and scheduling problem in manufacturing-based organizations [1, 2]. The proposed technique can also be investigated to create reconfigurable FSM-based architecture efficiently [29].In organizational structures, the role assignment problem is more often strictly limited to LAPs, RBCs, or MMAPs. Hence, a unified algorithm is required that can handle the issues mentioned earlier. The proposed technique will be examined further for creating a unified method to efficiently solve LAPs, RBCs, or MMAPs by adding an adaptive operator (see [30]) in it.



---

*Source: 8405036-2019-07-29.xml*