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

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.

• S. Raja Balachandar
• K.Kannan

• Combinatorial Optimization Problem
• Generalized Assignment Problem
• Intercept Matrix
• Heuristic
• Computational Complexity
• NP-Hard Problems.

[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.