×
Balachandar, S. Raja; Kannan, K.

A heuristic algorithm for resource allocation/reallocation problem. (English) Zbl 1236.90149

J. Appl. Math. 2011, Article ID 218078, 11 p. (2011).
Summary: This paper presents a 1-opt heuristic approach to solve resource allocation/reallocation problem which is known as 0/1 multichoice multidimensional knapsack problem (MMKP). The intercept matrix of the constraints is employed to find optimal or near-optimal solution of the MMKP. This heuristic approach is tested for 33 benchmark problems taken from OR library of sizes upto 7000, and the results have been compared with optimum solutions. Computational complexity is proved to be \(O(klmn^2)\) of solving heuristically MMKP using this approach. The performance of our heuristic is compared with the best state-of-art heuristic algorithms with respect to the quality of the solutions found. 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.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
90C27 Combinatorial optimization

Keywords:

multichoice multidimensional knapsack problem; computational complexity

Software:

OR-Library
PDF BibTeX XML Cite
\textit{S. R. Balachandar} and \textit{K. Kannan}, J. Appl. Math. 2011, Article ID 218078, 11 p. (2011; Zbl 1236.90149)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] R. Parra-Hernández and N. Dimopoulos, “Channel resource allocation/reallocation in cellular communication and linear programming,” in Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, vol. 3, pp. 2983-2989, October 2003.
[2] S. Khan, Quality adaptation in a multi-session adaptive multimedia system: model and architecture, Ph.D. dissertation, University of Victoria, Victoria, Canada, 1998.
[3] M. Moser, D. P. Jokanovic, and N. Shiratori, “An algorithm for the multidimensional multichoice knapsack problem,” IEICE Trans Fundam Electron, vol. 80, no. 3, pp. 582-589, 1997.
[4] S. Khan, K. F. Li, E. G. Manning, and M. D. M. Akbar, “Solving the Knapsack problem for adaptive multimedia systems,” Studia Informatica, vol. 2, pp. 154-174, 2002.
[5] Y. Toyoda, “A simplified algorithm for obtaining approximate solutions to zero-one programming problems,” Management Science, vol. 21, no. 12, pp. 1417-1427, 1974/75. · Zbl 0307.90056
[6] M. M. Akbar, E. G. Manning, G. C. Shoja, and S. Khan, “Heuristic solutions for the multiple-choice multi-dimension knapsack problem,” in the International Conference on Computional Science, V. N. Alexandrov, J. Dongarra, B. A. Juliano, R. S. Renner, C. Jeng, and K. Tan, Eds., Lecture Notes in Computer Science, pp. 659-668, San Francisco, Calif, USA, May 2001. · Zbl 0983.68646
[7] M Hifi, M Micharfy, and A Sbihi, “Heuristic algorithms for the multiple-choice multi-dimensional knapsack problem,” Journal of the Operational Research Society, vol. 55, no. 12, pp. 1323-1332, 2004. · Zbl 1088.90043
[8] M. Hifi, M. Michrafy, and A. Sbihi, “A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem,” Computational Optimization and Applications, vol. 33, no. 2-3, pp. 271-285, 2006. · Zbl 1103.90086
[9] N. Cherfi and M. Hifi, “Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem,” International Journal of Operational Research, vol. 5, no. 1, pp. 89-109, 2009. · Zbl 1169.90484
[10] N. Cherfi and M. Hifi, “A column generation method for the multiple-choice multi-dimensional knapsack problem,” Computational Optimization and Applications, vol. 46, no. 1, pp. 51-73, 2010. · Zbl 1190.90157
[11] A. Drexl, “A simulated annealing approach to the multiconstraint zero-one knapsack problem,” Computing, vol. 40, no. 1, pp. 1-8, 1988. · Zbl 0638.65053
[12] R. Parra-Hernández and N. J. Dimopoulos, “A new heuristic for solving the multichoice multidimensional knapsack problem,” IEEE Transactions on Systems, Man, and Cybernetics Part A, vol. 35, no. 5, pp. 708-717, 2005.
[13] M. A. H. Newton, M. W. H. Sadid, and M. M. Akbar, “A parallel heuristic algorithm for multiple-choice multidimensional knapsack problem,” in the International Conference on Computer and Information Technology, pp. 181-184, Dhaka, Bangladesh, December 2003.
[14] A. Z. M. Shahriar, M. M. Akbar, M. S. Rahman, and M. A. H. Newton, “A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem,” Journal of Supercomputing, vol. 43, no. 3, pp. 257-280, 2008. · Zbl 05537648
[15] A. Sbihi, “A best first search exact algorithm for the multiple-choice multidimensional knapsack problem,” Journal of Combinatorial Optimization, vol. 13, no. 4, pp. 337-351, 2007. · Zbl 1146.90058
[16] S. Raja Balachandar and K. Kannan, “A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles,” Applied Mathematics and Computation, vol. 202, no. 1, pp. 71-77, 2008. · Zbl 1147.65045
[17] A. L. Brearley, G. Mitra, and H. P. Williams, “Analysis of mathematical programming problems prior to applying the simplex algorithm,” Mathematical Programming, vol. 8, pp. 54-83, 1975. · Zbl 0317.90037
[18] J. Gondzio, “Presolve analysis of linear programs prior to applying an interior point method,” INFORMS Journal on Computing, vol. 9, no. 1, pp. 73-91, 1997. · Zbl 0890.90143
[19] I. Ioslovich, “Robust reduction of a class of large-scale linear programs,” SIAM Journal on Optimization, vol. 12, no. 1, pp. 262-282, 2001. · Zbl 0992.90046
[20] M. H. Karwan, V. Lotfi, J. Telgen, and S. Zionts, Redundancy in Mathematical Programming: A State-of-the-Art Survey, vol. 206 of Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Germany, 1983. · Zbl 0524.90058
[21] T. H. Mattheiss, “An algorithm for determining irrelevant constraints and all verticles in systems of linear inequalities,” Operations Research, vol. 21, pp. 247-260, 1973. · Zbl 0265.90024
[22] Cs. Mészáros and U. H. Suhl, “Advanced preprocessing techniques for linear and quadratic programming,” Spectrum, vol. 25, no. 4, pp. 575-595, 2003. · Zbl 1042.90031
[23] N. V. Stojković and P. S. Stanimirović, “Two direct methods in linear programming,” European Journal of Operational Research, vol. 131, no. 2, pp. 417-439, 2001. · Zbl 0991.90087
[24] J. Telgen, “Identifying redundant constraints and implicit equalities in systems of linear constraints,” Management Science, vol. 29, no. 10, pp. 1209-1222, 1983. · Zbl 0527.90066
[25] J. A. Tomlin and J. S. Welch, “Finding duplicate rows in a linear programming model,” Operations Research Letters, vol. 5, no. 1, pp. 7-11, 1986. · Zbl 0621.65058
[26] S. Paulraj, C. Chellappan, and T. R. Natesan, “A heuristic approach for identification of redundant constraints in linear programming models,” International Journal of Computer Mathematics, vol. 83, no. 8-9, pp. 675-683, 2006. · Zbl 1128.90040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.