A New Heuristic Approach for the Large-Scale Generalized Assignment Problem

Authors: S. Raja Balachandar, K.Kannan

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.

Keywords: Combinatorial Optimization Problem, Generalized Assignment Problem, Intercept Matrix, Heuristic, Computational Complexity, NP-Hard Problems.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070255

References:

[1] Amini, M.M., Racer, M, A rigorous comparison of alternative solution methods for the generalized assignment problem, Management Science 40, 868-890, 1994.
[2] Anderson, E.D. and K.D. Andersen, Presolving in linear programming. Math. Prog. Series B.,71:221-245, 1995.
[3] Beasley JE. OR-Library; Distributing Test Problems by Electronic Mail, Journal of Operational Research Society 41, 1069-1072, 1990.
[4] Brearley, A.L., G.Mitra and H.P Williams, Analysis of mathematical programming problem prior to applying the simplex algorithm . Math. Prog., 8: 54-83, 1975.
[5] Cattrysse, D.G., Wassenhove, L.N.V., A survey of algorithms for the generalized assignment problem. European Journal of Operational Research 60, 260-272, 1992.
[6] Cattrysse, D., Salomon, M and Van Wassenhove, L.N., A set partitioning heuristic for the generalized problem. European Journal of Operational Research., 72, 167-174, 1994.
[7] Chu, P.C., Beasley, JE., A genetic algorithm for the generalized assignment problem. Computers and Operations Research 24, 17-23, 1997.
[8] Diaz, J.A., Fernandez, E., A tabu search heuristic for the generalized assignment problem, European Journal of Operational Research 132, 22- 38, 2001.
[9] Fisher, M.L., The Lagrangian relaxation method for solving integer programming problems. Management Science 27, 1-18,1981.
[10] Fisher, M. L., Jaikumar,R. and Van Wassenhove, L.N, A multiplier adjustment method for the generalized assignment problem. Mgmt Sci., 32, 1095-1103, 1986.
[11] Gottlieb, E.S., Rao, M.R., The generalized assignment problem: Valid inequalities and facets. Mathematical Programming 46, 31-52, 1990.
[12] Gowdzio, J.,Presolve analysis of linear program prior to applying an interior point method .Inform. J.Comput., 9: 73-91, 1997.
[13] Guignard M., Rosenwein M.B. An improved dual based algorithm for the generalized assignment problem, Operations Research 37 (4), 658- 663, 1989.
[14] Haddadi, S., Lagrangian decomposition based heuristic for the generalized assignment problem. INFOR 37, 392-402, 1999.
[15] Haddadi, S., Ouzia, H., An effective Lagrangian heuristic for the generalized assignment problem,. INFOR 39, 351-356, 2001.
[16] Haddadi, S., Ouzia, H., Effective algorithm and heuristic for the generalized assignment problem. European Journal of Operational Research 153, 184-190, 2004.
[17] Harald Feltl and Gunther R. Raidl., An improved hybrid genetic algorithms for the generalized assignment problem, SAC -04, Nicosia, Cyprus, march 14-17, 2004.
[18] Higgins, A.J. A dynamic tabu search for large-scale generalized assignment problems, Computers and Operations Research 28 (10), 1039-1048, 2001.
[19] Ioslovich, I., Robust reduction of a class of large scale linear program. Siam J. Optimization, 12: 262-282, 2002.
[20] Jeet V., Kutanoglu E., Lagrangian relaxation guided problem space search heuristics for generalized assignment problems, European Journal of Operational Research 182, 1039-1056, 2007.
[21] Jornsten K., Nasberg M., A new lagrangian relaxation approach to the generalized assignment problem, European Journal of Operational Research 27, 313-323, 1986.
[22] Karwan, M.H., V. Loffi, J. Telgan and S. Zionts, Redundancy in mathematical Programming: A State of the Art Servey (Berlin: Springer- Verlag), 1983.
[23] Klastorin T.D. An effective subgradient algorithm for generalized assignment problem, Computers and Operations Research 6, 155-164, 1979.
[24] Kuhn, H.W. and R.E . Quant, An Experimental Study of the Simplex Method. In: Metropolis, N. et al.(Eds.). Preceedings of Symposia in Applied Mathematics. Providence, RI: Am. Math. Soc., 15: 107-124, 1962.
[25] Laguna, M., Kelly, J.P., Gonzalez Velarde, J.L., Glover, F. Tabu search for the multilevel generalized assignment problem, European Journal of Operational Research 82, 176-189, 1995.
[26] Lorena L.A.N., Narciso M.G., Relaxation heuristics for a generalized assignment problem, European Journal of Operational Research 91, 600- 610, 1996.
[27] Martello, S. P. Toth., An algorithm for the generalized assignment problem, operational Research -81, ed. J.P.Brans. North-Holland, 589- 603, 1981.
[28] Martello, S., Toth P. Knapsack Problems: Algorithms and Computer Implementations, Wiley, New York, 1990.
[29] Matthesiss, T.H., An Algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities. Operat. Res., 21: 247- 260, 1973.
[30] Meszaros. C. and U.H. Suhl, Advanced preprocessing techniques for linear and quadratic programming, Spectrum, 25: 575-595, 2003.
[31] Monfared. M.A.S and M . Etemadi., The impact of energy function structure on solving generalized assignment problem using Hopfield neural network, European Journal of Operational Research 168, 645-654, 2006.
[32] Narciso, M.G., Lorena, L.A.N. Lagrangian/surrogate relaxation for generalized assignment problems. European Journal of Operational Research 114 (1), 165-177, 1999.
[33] Nauss, R.M., Solving the generalized assignment problem:An optimizing and heuristic approach. INFORMS Journal of Computing 15 (3), 249-266, 2003.
[34] Nauss, R.M., The generalized assignment problem. In: Karlof, J.K. (Ed.), Integer Programming: Theory and Practice. CRC Press, Boca Raton, FL, 39-55, 2006.
[35] Osman, I.H., Heuristics for the generalized assignment problem: Simulated annealing and tabu search approaches. OR Spektrum 17, 211-225, 1995.
[36] Paulraj, S., C. Chellappan and T.R. Natesan, A heuristic approach for identification of redundant constraints in linear programming models. Int. J. Com. Math., 83(8): 675-683, 2006.
[37] Raja Balachandar. S, Kannan. K, A new polynomial time algorithm for 0-1 multiple knapsack problems based on dominant principles, Applied Mathematics and Computation, 202, 71-77, 2008.
[38] Ross, G.T., Soland, R.M., A branch and bound algorithm for the generalized assignment problem, Mathematical Programming 8, 91-103, 1975.
[39] Savelsbergh, M., A branch-and-price algorithm for the generalized assignment problem. Operations Research 45 (6), 831-841, 1997.
[40] Srojkovic, N.V. and P.S. Stanimirovic, Two direct methods in linear programming. European J. Oper. Res., 131: 417-439, 2001.
[41] Tai- Hsi Wu , Jinn-Yi Yeh, and Yu -Ru Syau., A tabu search approach to the generalized assignment problem, Journal of Chinese institute of Industrial Engineers, vol. 21, no. 3, pp. 301-311, 2004. Telgan, J., Identifying redundant constraints and implicit equalities in system of linear constraints. Manage. Sci., 29: 1209-1222, 1983.
[42] Tomlin, J.A. and J.S Wetch, Finding duplicate rows in a linear programming model. Oper. Res. Let., 5: 7-11,1986.
[43] Trick, M.A., A linear relaxation heuristic for the generalized assignment problem. Naval Research Logistics 39, 137-152,1992.
[44] Yagiura, M., Ibaraki, T., Glover, F., An ejection chain approach for the generalized assignment problem. INFORMS Journal of Computing 16 (2),133-151, 2004.
[45] Yagiura.M., Ibaraki.T, Glover, F, A path relinking approach with ejection chains for the generalized assignment problem. European journal of Operational Research. 169, 548-549, 2006.
[46] Yagiura.M and T. Ibaraki. Generalized Assignment Problem, in: T.F. Gonzalez, ed., Handbook of Approximation Algorithms and Metaheuristics, Chapman and Hall/CRC in the Computer and Information Science Series, Chapter 48 (18 pages), 2007.