# A Network Flow Algorithm for Solving Generalized Assignment Problem

Authors: Yongwen Hu; Qunpo Liu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

The generalized assignment problem (GAP) is an open problem in which an integerk is given and one wants to assign k′ agents to kk′≤k jobs such that the sum of the corresponding cost is minimal. Unlike the traditional K-cardinality assignment problem, a job can be assigned to many, but different, agents and an agent may undertake several, but different, jobs in our problem. A network model with a special structure of GAP is given and an algorithm for GAP is proposed. Meanwhile, some important properties of the GAP are given. Numerical experiments are implemented, and the results indicate that the proposed algorithm can globally and efficiently optimize the GAP with a large range cost.


---

## Body

## 1. Introduction

Assignment problem (AP) is one of the fundamental combinatorial optimization problems with various applications in real life. The classical AP is proved to be anNP-hard problem, and it deals with a situation of assigning n jobs to n agents such that each job must be processed by exactly one agent and vice versa. And the popular systematic method for solving classical AP is Kuhn’s Hungarian method [1, 2] which can be extended for general network flow problems in a polynomial time. However, it is quite difficult to ensure that the number of jobs is exactly equal to the number of agents in real-life situation. Furthermore, jobs and agents are set to be unique in the classical AP, which leads to any row (column) in cij,∀i∈M,j∈N (M is an index set of agents and N is an index set of jobs) being different from every other row (column). In fact, although all agents are unique, some jobs can be identical and vice versa in practical applications. Kennington and Wang [3] give some typical problems, such as manpower planning, scheduling, and planning, in which more than one agent is assigned to the same job group. Also, a shortest augmenting path algorithm is presented for solving them.Dell’Amico and Martello [4] considered a generalization of AP (called K-cardinality linear assignment problem) where one wants to assign k (out of m) agents to k (out of n) jobs k≤minm,n so that the sum of the corresponding cost is minimal. Some potential applications of K-cardinality linear assignment problem can be found in [5, 6]. Further, the K-cardinality assignment problem has various applications, for example, in assigning agents to machines when there are multiple alternatives and only a subset of agents and machines has to be assigned. In this paper, we consider a more generalized assignment problem (GAP) in which a cost matrix Am×n and positive integer k0<k≤minm,n are given and one wants to assign k′ agents to kk′≤k jobs so that the sum of the corresponding cost is minimal.Dell’Amico and Martello developed some algorithms for solvingK-cardinality linear assignment problem by min-cost flow or shortest augmenting path techniques described in [4]. Also, heuristic processing techniques were given in [7]. Later, Volgenant [8] developed an algorithm for it by solving a sequence of classical AP. Recently, based on semi-Lagrangian relaxation, Belik and Jo..rnsten [9] proposed an algorithm for the K-cardinality AP with large scale. Clearly, the GAP considered in this paper is the K-cardinality assignment problem when k′=k. The GAP is an NP-hard [10] problem. Later, Chu and Beasley [11] prove that GAP is NP-complete.Several algorithms have been proposed for GAP in the past few years. Most of the small sizes of the test instances have been solved by some exact methods such as branch and bound, branch and price, and cutting plane [12–16]. However, the exact methods are mostly unable to find an optimal solution within a reasonable computational time. Metaheuristic and heuristics have been proposed for solving GAP in order to reduce the computational time of the exact method, such as the combination of a heuristics and exact method [17], tabu search [18], simulated annealing [19], genetic algorithm [11, 20], differential evolution algorithm [21, 22], and bees algorithm [23].Clearly, the GAP considered in this paper can be transformed into a classical AP when some dummy jobs or agents are introduced. And the Hungarian method and its variants [24–26] are presented for optimizing GAP recently. However, the transformation will result in a larger-scale problem and worse space complexity. Currently, several exact algorithms are presented for solving GAP with minimum cost, such as variable-fixing algorithm [27], branch and bound algorithm [12], and KM algorithm [28], but these algorithms can only solve GAP with some specific assumption.This study focuses on GAP where the number of agents is not equal to the number of jobs. Specifically, one job can be assigned to many, but different, agents, and one agent may undertake many, but different, tasks. It is well known that AP is thought of as a special min-cost flow problem, which suggests that classical AP or GAP can be solved by some methods with network flow theory. Recently, an efficient algorithm was proposed for solving min-cost flow problem [29]. This paper attempts to give a variation of the algorithm presented in [29] for GAP based on the advantage of the special structure of the transformed network model.This paper is organized as follows. Section2 gives a mathematical formulation and network flow model for the GAP; in Section 3, we describe an algorithm for solving GAP. Also, the convergence of the proposed algorithm and some important features of GAP are given in this section; Section 4 presents numerical experiments to evaluate the performance of the proposed algorithm. Concluding remarks and some further research are provided in Section 5.


## 2. Mathematical Formulation and Network Flow Model

Given anm×n matrix C=cij and an integer k0<k≤minm,n, the GAP can be formulated as follows:(1)GAPminz=∑i=1m∑j=1ncijxijs.t.∑j=1nxij=yi,i=1,2,…,m,∑i=1mxij=zj,j=1,2,…,n,∑i=1myi=k,∑j=1nzj=k,xij=0or1,i=1,2,…,m;j=1,2,…,n,where k,yi,zj∈I;cij≥0;i∈M=1,2,…,m;j∈N=1,2,…,n; xij=1 if agent i is assigned to job j. First, we consider the case that an agent can be assigned to more than one job, but a job is assigned to exactly one agent, that is,zj=1,∀j∈N in (1). We leave the situation that a group job can be processed by more than one agent later.It is well known that classical AP is a bipartite matching problem which can be transformed into a maximum flow problem in a simple network. To transform the GAP defined on an undirected graphG=M∪N,A, we create a directed version of G by designating each arc in A as pointing nodes in M to nodes in N. Then, we introduce a source node s and a sink node t, with s,i,∀i∈M, and j,t,∀j∈N. We refer to the transformed network as G′=N′,A′,C,U with a cost set C and a capacity set U associated with each arc i,j∈A′. Let cs,i=0,cj,t=0,0≤us,i≤yi,0≤uj,t≤1,0≤ui,j≤1,∀i∈M,j∈N.Figure1 illustrates the transformation. Mathematically, the transformed model is given by(2)MCFminz=∑i=1m∑j=1ncijxijs.t.∑i=1mxsi=k,i∈M,∑j=1nxjt=−k,j∈N,∑jxij−∑ixij=0,∀i,j∈M∪N,0≤xij≤1,∀i,j∈M∪N∪s∪t.Figure 1
Unit capacity network flow model.It is easy to deal with the case that some identical jobs can be grouped into a set. More specifically, if1′ is a group set which consists of z1′ jobs, then the capacity of 1′,t is to be set to z1′ instead of 1.According to the transformation mentioned above and theIntegrality Theorem [30], it is easy to get the following theorem.Theorem 1.
The GAP is equivalent to the MCF.Theorem1 indicates that we can find an integral flow of value k in the transformed network in order to get an optimal solution of GAP. Although several algorithms are presented for optimizing minimum-cost flow problem, both cost and capacity are to be considered for iteratively defining residual network. Hu et al. [29] introduced an approach that can solve min-cost flow. Unlike the traditional algorithms, the proposed algorithm in [29] can find an augmenting path in the original network by updating node potentials. We will describe an algorithm for optimizing GAP based on the network model defined above in the next section.


## 3. Proposed Algorithm for Solving GAP

Hu et al. [29] gave a detail algorithm for solving minimum-cost flow problem by introducing some optimality conditions. Since the transformed network flow model, shown in Figure 1, is a simple network, a modified version of the algorithm in [29] is introduced for GAP for self-contained in this section.Let us consider a dual problem of problem (2)(3)DPmaxw=kps−kpt+∑i,j∈A′uijpij,s.t.pi−pj+pij≤cij,∀i,j∈A′,piis free,∀i∈M∪N∪s∪t,pij≤0,∀i,j∈A′,where pi and pij are the dual variables of MCF. And we refer to pi and pij as the potential of node i and arc i,j∈A′, respectively.Letxij and p=pi,pij be the feasible solutions of MCF and DP, respectively. If xij and p=pi,pij are optimal solutions, according to strong duality, we have(4)xij=0,ifpi−pj+pij<cij,∀i∈N′,xij=uij,ifpi−pj>cij,∀i∈N′,i,j∈A′.Sincepi is free ∀i∈N′, let pij=min0,cij+pj−pi, then pij≤0 will be held. Therefore, a feasible solution p=pi,pij of DP can be found. Thus, conditions (4) are equal to the conditions as follows:(5)xij=0,ifpi−pj<cij,∀i∈N′,xij=uij,ifpi−pj>cij,∀i∈N′,i,j∈A′.Clearly, an optimal solutionx=xij will satisfy conditions (5). And we have the following theorem.Theorem 2.
Letxij be a feasible solution of MCF, then xij is an optimal solution if and only if the following conditions are satisfied:(6)pi−pj<cij⟹xij=0,pi−pj>cij⟹xij=uij.We refer the arc satisfyingpi−pj=cij,∀i,j∈A′ to an admissible arc. Similarly, a network is an admissible network in which each arc is an admissible arc. Clearly, xij=0,∀i,j∈A′ is an optimal solution with an integral flow of value 0. The proposed algorithm starts sending 0 unit of flow from s to t. Furthermore, by holding condition (6) at each iteration, the proposed algorithm can find at least an augmenting path from the source node s to the sink node t after updating node potential in finite iteration. Therefore, flow can be augmented when the current amount flow is not maximal.Letμ+andμ− be a forward arc set and a backward arc set on an augmenting set μ. Now we describe an algorithm for solving GAP corresponding the network G′=N′,A′,C,U, where N′=M∪N, and we refer an admissible network to R.Clearly, for an optimal solutionxij∗,∀i∈M,j∈N, agent ii∈M will be assigned to job jj∈N if xij∗=1. We give the following definition in advance in order to get some important properties on GAP.Definition 1.
LetViandVj be the node sets of any two augmenting paths (referred to μi,μj) from source node s to sink node t, then μi,μj are independent augmenting paths if Vi\s\t∩Vj\s\t=∅.Theorem 3.
Suppose the current amount of flow obtained by Algorithm1 is k′k′<k, GAP has Cqk−k′ optimal solutions if we can find qq≥k−k′ independent augmenting paths in the following iteration.Theorem3 can be proved easily according to the detail algorithm and definition of independent augmenting path mentioned above, and here, we do not discuss the proof of Theorem 3.Algorithm 1: Algorithm for GAP.
Initial settings:pi=0,∀i∈N′,xij=0,∀i,j∈A′,S=s∪M,s¯=N′\S. Label source node 0,1. Let k be a given integer number such that 0<k≤minm,n.while∑i=1mxsi<k,i∈MdoRemove all labels of nodei,∀i∈M∪N∪t.whilet∉Sdopi=pi+θ,∀i∈S, where θ=mink∈S∩M,q∈S¯∩Nckq−pk+pq.ifpi−pj=cij,∀i∈S,j∈S¯theni,j∈R.end ififi,j∈R,xij=0,∀i∈S,j∈S¯thenNodej is labeled with i,1, S=S∪j,S¯=S¯\j.end ififj,i∈R,xji=1,∀i∈S,j∈S¯thenNodej is labeled with −i,1, S=S∪j,S¯=S¯\j.end ifend whilexij=xij+1,i,j∈μ+,xij−1,i,j∈μ−,xij.end whileTheorem 4.
Letci′,j′=mincij,∀i∈M,j∈N be in a row set Ro and in a column set Co, then at least an agent i′∈Ro is to be assigned to a job in N. Similarly, at least a job j′∈Co is to be processed by an agent in M.Proof.
Sinceθ=mink∈S∩M,q∈S¯∩Nckq−pk+pq, at least an admissible will be introduced after updating node potentials in the following iteration. Thus, pi′−pj′=ci′,j′, and ci′,j′=mincij,∀i∈M,j∈N, which implies that nodes s,i′,j′ can be labeled. In addition, as cj′t=0, then sink node t is to be labeled. Therefore, we can find an augmenting path from s to t, and there exists at least a node j′∈N such that xj′t=1. Furthermore, the equation xj′t=1 is always satisfied in the following iterations according to the details in Algorithm 1. Thus, job j′ is to be processed by an agent in M for optimal match. Similarly, for an optimal solution, there exists an agent i′∈M to be assigned to a job in N.From Theorem4, we have the following corollary.Corollary 1.
Letxij∗,i∈M,j∈N be an optimal solution for the GAP with k−1 cardinality, then the agents and jobs corresponding to xij∗=1 will be assigned in GAP with k cardinality.Theorem 5.
Algorithm1 will terminate in finite iterations.Proof.
Clearly, sink nodet cannot be labeled if xjt=1,∀j∈N. Otherwise, as csi=cjt=0,∀i∈M,j∈N, t will be labeled while j is labeled, which implies that we can find an augmenting path from s to t and one more unit flow can be sent from s to t at first iteration. In addition, node i can be labeled if j is labeled and xij=1. Therefore, we can find an augmenting path after updating node potential in l iterations at l-th iteration, and at least one more unit flow can be sent from s to t. For GAP with k cardinality, the total number of iterations is 1+2+⋯+k=k2+k/2, which gives Theorem 5.As it is described in Algorithm1, flow can be augmented after updating nodes’ potential in a finite iteration. Therefore, the complexity of the proposed algorithm is Ok2n+m2.Next, we will give some numerical experiments to evaluate the efficiency of Algorithm1.


## 4. Numerical Experiments

In this section, the performance of the proposed algorithm is demonstrated by numerical experiments and we compare its performance with a PP-Lapjv algorithm [31] and bees algorithm for GAP. The bees algorithm is proposed by Ozbakir et al. [23] for the complex integer optimization problem. The PP-Lapjv algorithm is an improved version of Lapjv algorithm [32, 33]. The GAP is transformed into a balanced AP when we use the PP-Lapjv algorithm for solving GAP. For the sake of simplicity, the PP-Lapjv algorithm is called A1. The bees algorithm and our algorithm presented in the paper are called A2andA3, respectively. The presented algorithm is coded in MATLABR R2016b on a laptop computer with an Intel®Corei5TMi5-7300HQ CPU @2.50 GHz RAM 8 GB and the operating system is Windows 10 64 bit. As shown in Figure 1, the unit capacity network flow model of the GAP has a special structure that there is only forward i,j,∀i∈M,j∈N. Thus, it is easy to generate a random network which is connected.A series of numerical experiments is implemented on test problems differing in input data values ofcij, and the cij is drawn randomly from a uniform distribution on the intervals 0,102,0,105. This kind of generation is often encountered to evaluate algorithms for solving AP [34]. The GAP with different scales (m,n varying from 20,20 to 200,400) is considered. And each class consists of instances with k valued 0.2v,0.4v,0.6v,0.8v,0.9v,v, where v=minm,n. The column titled k provides the coefficient of v. Also, for each class of problem, we consider the case that an agent can be assigned to k jobs when k is given. In addition, the proposed algorithm is evaluated on various degrees of density 20% and 80%. For a given density d%, the instance is generated as follows. We first randomly generate a value r∈0,1, and for each arc i,j,∀i∈M,j∈N, the arc i,j is kept in the instance with a randomly generated cost cij; otherwise, the next arc is considered. Higher density means that each multiskill agent i∈M can be assigned to more various jobs in M. Further, the parameter setting is the same as the parameters in [23].We report the CPU time ofA1, A2, and A3 for solving GAP in Table 1. In each block, each entry in the 6 lines gives the average CPU time computed over 10 instances, neglecting the input, the output, and generation of the network flow model. And the last line gives the average over all k values considered. Also, Figures 2 and 3 depict the average CPU time on the various k values for the density 80% and 20%, respectively.Table 1
Computational behavior of randomly generated GAP with various values ofm,n,k,c, and a density valued 0.8 (times in seconds).
m,nkd%=80%d%=20%c∈0,102c∈0,105c∈0,102c∈0,105A1A2A3A1A2A3A1A2A3A1A2A320,200.25.6200.0460.0405.9400.0470.0144.9710.0400.0125.8370.0430.0060.45.6830.0480.0196.1680.0480.0215.0080.0420.0175.9060.0450.0160.65.9260.0520.0526.1860.0530.0355.2550.0450.0216.1830.0500.0180.85.9110.0590.0416.0030.0670.0305.2160.0530.0225.9850.0620.0190.96.0980.0600.0506.0640.0720.0405.3430.0530.0296.0900.0660.0241.06.1220.0610.0426.1090.0770.0405.3790.0540.0436.0400.0710.027Average5.8930.0540.0416.0780.0610.0285.1950.0480.0246.1420.0560.01820,400.25.8550.1080.0406.1870.1110.0255.1680.0950.0116.0070.1080.0150.45.9060.1090.0305.9710.1260.0145.1730.0970.0185.9550.1150.0160.66.1010.1120.0706.1280.1280.0325.3820.0990.0235.9100.1190.0200.86.2010.1270.0535.9860.1360.0215.4490.1130.0265.9220.1390.0250.96.4400.1350.0636.0300.1390.0455.7050.1230.0305.9170.1450.0251.06.3610.1390.0475.9470.1430.0415.6440.1230.0316.0000.1510.027Average6.1440.1220.0516.0420.1310.0305.4230.1080.0235.9520.1300.02150,500.25.9510.5510.1787.2460.6670.0835.2470.5670.0506.9770.8500.0450.46.0710.5540.2637.3220.6810.1235.3940.5860.0977.2740.8670.0640.66.1140.5650.3317.3850.6920.1525.4180.5900.1257.2300.8850.1190.86.9350.5820.3587.4110.6960.1946.0980.6030.1277.4110.8860.1200.97.3110.5840.3587.2720.7010.2066.4170.6180.2107.2320.9520.1281.08.0680.6070.3847.3980.7320.2147.0740.6510.2427.1870.9840.111Average6.7420.5740.3127.3390.6950.1625.9410.6030.1427.2220.8990.09850,1000.26.7370.8460.3448.6241.1050.0645.8960.7460.0808.3051.0820.0420.46.9560.8520.5448.7141.1120.1426.1550.7510.1278.5291.1140.0890.66.8720.9200.6868.8931.1240.1946.0260.8170.1698.6691.2070.1130.88.4460.9590.7238.9891.1370.2077.4270.8460.1918.7731.2390.1380.99.2521.0510.8039.0571.1460.2148.1530.9250.2348.6671.3040.2031.011.5761.1120.8849.0511.3680.22710.1360.9770.2398.9611.3480.213Average8.3070.9570.5618.8881.1650.1757.3140.8840.1738.6511.2160.133100,1000.26.7602.2640.7828.9403.0380.1685.9441.9880.3228.6042.8430.1830.46.8492.3682.69710.9833.3980.4796.0512.1070.51710.5663.0550.2570.66.9942.4133.32211.5343.4400.5836.1502.1480.64211.0533.1360.3820.88.6732.8913.54511.6924.2300.6307.6212.6020.66311.3753.9290.4650.99.2863.1073.71411.9434.6610.8548.1812.7960.86611.7444.0180.5871.011.6763.2683.72711.9265.0330.88210.2552.9831.09211.5884.2370.616Average8.3732.7192.96511.1703.9670.5597.3672.4220.66710.8223.5360.415100,2000.29.55515.1035.25611.82618.7240.3438.41111.7000.76911.59716.0870.2120.49.08415.2178.98112.13220.5370.7157.95712.1501.22511.78116.9400.4240.69.35716.46711.17312.23823.2670.9778.23113.5301.47011.88119.3050.5990.812.58618.52511.64215.40625.9011.00311.05015.7251.49515.02322.8010.5500.912.84519.63711.96315.71427.5881.09911.28317.0521.75815.30225.5780.7441.017.23620.20812.19520.01031.0291.15515.11518.1871.77519.21227.2810.932Average11.77717.51110.20214.55424.5080.88210.3414.7241.14514.19321.2120.577200,2000.29.67022.61234.09212.30128.2501.8268.49818.3163.67312.08724.9070.8470.49.78223.10759.84312.21329.2173.1588.57119.1736.14211.85926.8421.7070.69.82524.75070.22512.69334.4234.2088.67621.2857.60812.31830.2252.4460.813.74227.69573.29116.27537.1315.20812.04523.3647.74815.78432.4782.4340.914.15828.73374.68616.69242.1575.65812.42024.9529.03916.28633.1674.5691.018.84331.20376.18821.24545.2087.30616.53027.00710.67820.64335.2474.576Average12.67026.35064.72315.23736.0644.56111.12322.3507.48114.83030.4782.763200,4000.29.529108.531127.21112.686145.8073.9938.37593.96112.33812.139133.4251.6280.410.327113.421218.29112.719154.8267.5529.05594.69220.58312.450134.2193.1250.610.135120.280266.02312.518164.9049.9138.941102.24124.84712.293143.6274.3890.815.123133.514275.43118.226172.92711.49513.271105.82125.05017.707151.2924.3060.916.541139.770285.42218.824180.61911.87014.486122.32727.78418.184156.4435.8521.023.668151.022286.51126.359194.23111.99020.766129.86328.13925.409160.1266.457Average14.221127.356243.14816.889168.8869.94612.482108.15123.12416.364146.5224.248Figure 2
Average CPU time of algorithmsA1, A2, and A3 for different sizes of problem with density 80%.Figure 3
Average CPU time of algorithmsA1, A2, and A3 for different sizes of problem with density 20%.A3 has a high probability to find an augmenting path from s to t after updating nodes’ potential in two iterations, which can be easily verified by the network model and Algorithm 1 of GAP. Furthermore, as it is shown in Algorithm 1, A3 holds the information of node potential at each iteration. Therefore, for a larger range cij∈0,105, the curves of the proposed algorithm are at the bottom of Figures 2 and 3. However, it will take more iterations for finding an augmenting path from s to t with a larger number of arcs i,j∈A′,i∈M,j∈N and a smaller range cij∈1,102,i,j∈A′ for A3. Thus, there are exceptions for the efficiency of A3 when the size of GAP is increased (e.g.,m,n is greater than (100, 100) for a smaller cij). It is understandable that A3 will find an augmenting path in much more iteration in a network with a smaller cij, especially for a larger size of problem. In addition, larger size of GAP results in a greater number of local optimal solutions. Thus, it will take much more CPU time for A2, which is shown in Figures 2 and 3.The CPU time of algorithmA1 consists of time for running Lapjv.m file and constructing the k-th transferred cost matrix which is mainly related to the size of the problem. Therefore, variation of CPU time of A1 is much smaller than that of A3 for the same size of problem (the size of the problem is defined by maxm,n).


## 5. Conclusion and Further Work

This paper develops an algorithm for solving GAP in which an integerk is given and one wants to assign k′k′≤k agents to k jobs such that the sum of the corresponding cost is minimal. The problem is transformed into a network model with a special structure. And the network model of GAP can easily process the GAP in which one agent can be assigned to more than one job or a job group can be processed by more than one agent. Some important properties of GAP are derived and numerical experiments show that our proposed algorithm has some good performance for solving GAP with a larger range cost cij and a smaller number of arcs i,j,∀i∈M,j∈N.In this study, the scale of GAP is not very large, and we plan to develop some techniques for processing large-scale sparse cost matrix in order to optimize the GAP in a short time. Furthermore, it is fundamental to develop an algorithm for solving the bottleneck GAP or fuzzy GAP.



---

*Source: 5803092-2021-01-12.xml*