{"title":"A New Heuristic Approach for the Large-Scale Generalized Assignment Problem","authors":"S. Raja Balachandar, K.Kannan","volume":35,"journal":"International Journal of Mathematical and Computational Sciences","pagesStart":969,"pagesEnd":975,"ISSN":"1307-6892","URL":"https:\/\/publications.waset.org\/pdf\/8097","abstract":"
This paper presents a heuristic approach to solve the Generalized Assignment Problem (GAP) which is NP-hard. It is worth mentioning that many researches used to develop algorithms for identifying the redundant constraints and variables in linear programming model. Some of the algorithms are presented using intercept matrix of the constraints to identify redundant constraints and variables prior to the start of the solution process. Here a new heuristic approach based on the dominance property of the intercept matrix to find optimal or near optimal solution of the GAP is proposed. In this heuristic, redundant variables of the GAP are identified by applying the dominance property of the intercept matrix repeatedly. This heuristic approach is tested for 90 benchmark problems of sizes upto 4000, taken from OR-library and the results are compared with optimum solutions. Computational complexity is proved to be O(mn2) of solving GAP using this approach. The performance of our heuristic is compared with the best state-ofthe- art heuristic algorithms with respect to both the quality of the solutions. The encouraging results especially for relatively large size test problems indicate that this heuristic approach can successfully be used for finding good solutions for highly constrained NP-hard problems.<\/p>\r\n","references":"[1] Amini, M.M., Racer, M, A rigorous comparison of alternative solution\r\nmethods for the generalized assignment problem, Management Science\r\n40, 868-890, 1994.\r\n[2] Anderson, E.D. and K.D. Andersen, Presolving in linear programming.\r\nMath. Prog. Series B.,71:221-245, 1995.\r\n[3] Beasley JE. OR-Library; Distributing Test Problems by Electronic Mail,\r\nJournal of Operational Research Society 41, 1069-1072, 1990.\r\n[4] Brearley, A.L., G.Mitra and H.P Williams, Analysis of mathematical\r\nprogramming problem prior to applying the simplex algorithm . Math.\r\nProg., 8: 54-83, 1975.\r\n[5] Cattrysse, D.G., Wassenhove, L.N.V., A survey of algorithms for the generalized\r\nassignment problem. European Journal of Operational Research\r\n60, 260-272, 1992.\r\n[6] Cattrysse, D., Salomon, M and Van Wassenhove, L.N., A set partitioning\r\nheuristic for the generalized problem. European Journal of Operational\r\nResearch., 72, 167-174, 1994.\r\n[7] Chu, P.C., Beasley, JE., A genetic algorithm for the generalized assignment\r\nproblem. Computers and Operations Research 24, 17-23, 1997.\r\n[8] Diaz, J.A., Fernandez, E., A tabu search heuristic for the generalized\r\nassignment problem, European Journal of Operational Research 132, 22-\r\n38, 2001.\r\n[9] Fisher, M.L., The Lagrangian relaxation method for solving integer\r\nprogramming problems. Management Science 27, 1-18,1981.\r\n[10] Fisher, M. L., Jaikumar,R. and Van Wassenhove, L.N, A multiplier\r\nadjustment method for the generalized assignment problem. Mgmt Sci.,\r\n32, 1095-1103, 1986.\r\n[11] Gottlieb, E.S., Rao, M.R., The generalized assignment problem: Valid\r\ninequalities and facets. Mathematical Programming 46, 31-52, 1990.\r\n[12] Gowdzio, J.,Presolve analysis of linear program prior to applying an\r\ninterior point method .Inform. J.Comput., 9: 73-91, 1997.\r\n[13] Guignard M., Rosenwein M.B. An improved dual based algorithm for\r\nthe generalized assignment problem, Operations Research 37 (4), 658-\r\n663, 1989.\r\n[14] Haddadi, S., Lagrangian decomposition based heuristic for the generalized\r\nassignment problem. INFOR 37, 392-402, 1999.\r\n[15] Haddadi, S., Ouzia, H., An effective Lagrangian heuristic for the\r\ngeneralized assignment problem,. INFOR 39, 351-356, 2001.\r\n[16] Haddadi, S., Ouzia, H., Effective algorithm and heuristic for the generalized\r\nassignment problem. European Journal of Operational Research\r\n153, 184-190, 2004.\r\n[17] Harald Feltl and Gunther R. Raidl., An improved hybrid genetic algorithms\r\nfor the generalized assignment problem, SAC -04, Nicosia, Cyprus,\r\nmarch 14-17, 2004.\r\n[18] Higgins, A.J. A dynamic tabu search for large-scale generalized assignment\r\nproblems, Computers and Operations Research 28 (10), 1039-1048,\r\n2001.\r\n[19] Ioslovich, I., Robust reduction of a class of large scale linear program.\r\nSiam J. Optimization, 12: 262-282, 2002.\r\n[20] Jeet V., Kutanoglu E., Lagrangian relaxation guided problem space\r\nsearch heuristics for generalized assignment problems, European Journal\r\nof Operational Research 182, 1039-1056, 2007.\r\n[21] Jornsten K., Nasberg M., A new lagrangian relaxation approach to\r\nthe generalized assignment problem, European Journal of Operational\r\nResearch 27, 313-323, 1986.\r\n[22] Karwan, M.H., V. Loffi, J. Telgan and S. Zionts, Redundancy in\r\nmathematical Programming: A State of the Art Servey (Berlin: Springer-\r\nVerlag), 1983.\r\n[23] Klastorin T.D. An effective subgradient algorithm for generalized assignment\r\nproblem, Computers and Operations Research 6, 155-164, 1979.\r\n[24] Kuhn, H.W. and R.E . Quant, An Experimental Study of the Simplex\r\nMethod. In: Metropolis, N. et al.(Eds.). Preceedings of Symposia in\r\nApplied Mathematics. Providence, RI: Am. Math. Soc., 15: 107-124,\r\n1962.\r\n[25] Laguna, M., Kelly, J.P., Gonzalez Velarde, J.L., Glover, F. Tabu search\r\nfor the multilevel generalized assignment problem, European Journal of\r\nOperational Research 82, 176-189, 1995.\r\n[26] Lorena L.A.N., Narciso M.G., Relaxation heuristics for a generalized\r\nassignment problem, European Journal of Operational Research 91, 600-\r\n610, 1996.\r\n[27] Martello, S. P. Toth., An algorithm for the generalized assignment\r\nproblem, operational Research -81, ed. J.P.Brans. North-Holland, 589-\r\n603, 1981.\r\n[28] Martello, S., Toth P. Knapsack Problems: Algorithms and Computer\r\nImplementations, Wiley, New York, 1990.\r\n[29] Matthesiss, T.H., An Algorithm for determining irrelevant constraints\r\nand all vertices in systems of linear inequalities. Operat. Res., 21: 247-\r\n260, 1973.\r\n[30] Meszaros. C. and U.H. Suhl, Advanced preprocessing techniques for\r\nlinear and quadratic programming, Spectrum, 25: 575-595, 2003.\r\n[31] Monfared. M.A.S and M . Etemadi., The impact of energy function\r\nstructure on solving generalized assignment problem using Hopfield\r\nneural network, European Journal of Operational Research 168, 645-654,\r\n2006.\r\n[32] Narciso, M.G., Lorena, L.A.N. Lagrangian\/surrogate relaxation for generalized\r\nassignment problems. European Journal of Operational Research\r\n114 (1), 165-177, 1999.\r\n[33] Nauss, R.M., Solving the generalized assignment problem:An optimizing\r\nand heuristic approach. INFORMS Journal of Computing 15 (3),\r\n249-266, 2003.\r\n[34] Nauss, R.M., The generalized assignment problem. In: Karlof, J.K. (Ed.),\r\nInteger Programming: Theory and Practice. CRC Press, Boca Raton, FL,\r\n39-55, 2006.\r\n[35] Osman, I.H., Heuristics for the generalized assignment problem: Simulated\r\nannealing and tabu search approaches. OR Spektrum 17, 211-225,\r\n1995.\r\n[36] Paulraj, S., C. Chellappan and T.R. Natesan, A heuristic approach for\r\nidentification of redundant constraints in linear programming models. Int.\r\nJ. Com. Math., 83(8): 675-683, 2006.\r\n[37] Raja Balachandar. S, Kannan. K, A new polynomial time algorithm for\r\n0-1 multiple knapsack problems based on dominant principles, Applied\r\nMathematics and Computation, 202, 71-77, 2008.\r\n[38] Ross, G.T., Soland, R.M., A branch and bound algorithm for the\r\ngeneralized assignment problem, Mathematical Programming 8, 91-103,\r\n1975.\r\n[39] Savelsbergh, M., A branch-and-price algorithm for the generalized\r\nassignment problem. Operations Research 45 (6), 831-841, 1997.\r\n[40] Srojkovic, N.V. and P.S. Stanimirovic, Two direct methods in linear\r\nprogramming. European J. Oper. Res., 131: 417-439, 2001.\r\n[41] Tai- Hsi Wu , Jinn-Yi Yeh, and Yu -Ru Syau., A tabu search approach\r\nto the generalized assignment problem, Journal of Chinese institute of\r\nIndustrial Engineers, vol. 21, no. 3, pp. 301-311, 2004.\r\nTelgan, J., Identifying redundant constraints and implicit equalities in\r\nsystem of linear constraints. Manage. Sci., 29: 1209-1222, 1983.\r\n[42] Tomlin, J.A. and J.S Wetch, Finding duplicate rows in a linear programming\r\nmodel. Oper. Res. Let., 5: 7-11,1986.\r\n[43] Trick, M.A., A linear relaxation heuristic for the generalized assignment\r\nproblem. Naval Research Logistics 39, 137-152,1992.\r\n[44] Yagiura, M., Ibaraki, T., Glover, F., An ejection chain approach for the\r\ngeneralized assignment problem. INFORMS Journal of Computing 16\r\n(2),133-151, 2004.\r\n[45] Yagiura.M., Ibaraki.T, Glover, F, A path relinking approach with ejection\r\nchains for the generalized assignment problem. European journal of\r\nOperational Research. 169, 548-549, 2006.\r\n[46] Yagiura.M and T. Ibaraki. Generalized Assignment Problem, in: T.F.\r\nGonzalez, ed., Handbook of Approximation Algorithms and Metaheuristics,\r\nChapman and Hall\/CRC in the Computer and Information Science\r\nSeries, Chapter 48 (18 pages), 2007.","publisher":"World Academy of Science, Engineering and Technology","index":"Open Science Index 35, 2009"}