A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs. (English) Zbl 1467.90050
Summary: The knapsack problem arises in a variety of real world applications, including flexible manufacturing systems, railway stations, hydrological studies and others. In this paper, we propose a descent method-based heuristic for tackling a special knapsack problem: the binary quadratic knapsack with conflict graphs. The proposed method combines (i) an intensification search with a descent method for enhancing the accuracy of the solutions and (ii) a diversification strategy which is used for enlarging the search space. The method uses degrading and re-optimization strategies in order to reach a series of diversified solutions. The performance of the proposed method is evaluated on benchmark instances taken from the literature, where its achieved results are compared to those reached by both GLPK solver and the best method available in the literature. The method seems very competitive, where it is able to achieve 37 new lower bounds.
MSC:
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Billionnet, A.; Soutif, E., An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 157, 565-575 (2004) · Zbl 1067.90126 · doi:10.1016/S0377-2217(03)00244-3 |
| [2] | Dantzig, GB, Discrete-variable extremum problem, Operations Research, 5, 2, 266-288 (1957) · Zbl 1414.90353 · doi:10.1287/opre.5.2.266 |
| [3] | GLPK. (2017). GNU linear programming kit. https://www.gnu.org/software/glpk/; https://github.com/PetterS/glpk. |
| [4] | Hifi, M., An iterative rounding search-based algorithm for the disjunctively constrained knapsack problem, Engineering Optimization, 46, 8, 1109-1122 (2014) · doi:10.1080/0305215X.2013.819096 |
| [5] | Hifi, M.; Michrafy, M., A reactive local search-based algorithm for the disjunctively constrained knapsack problem, Journal of the Operational Research Society, 57, 718-726 (2006) · Zbl 1151.90587 · doi:10.1057/palgrave.jors.2602046 |
| [6] | Hifi, M.; Michrafy, M., Reduction strategies and exact algorithms for the disjunctively knapsack problem, Computers and Operations Research, 34, 9, 2657-2673 (2007) · Zbl 1141.90512 · doi:10.1016/j.cor.2005.10.004 |
| [7] | Hifi, M.; Sadfi, S.; Sbihi, A., An efficient algorithm for the knapsack sharing problem, Computational Optimization and Applications, 23, 27-45 (2002) · Zbl 1064.90040 · doi:10.1023/A:1019920507008 |
| [8] | Hifi, M.; Saleh, S.; Wu, L., A hybrid guided neighborhood search for the disjunctively constrained knapsack problem, Cogent Engineering (2015) · doi:10.1080/23311916.2015.1068969 |
| [9] | Hif, M.; Wu, L., Lagrangian heuristic-based neighborhood search for the multiple-choice multi-dimensional knapsack problem, Engineering Optimization, 47, 12, 1619-1636 (2015) · doi:10.1080/0305215X.2014.982631 |
| [10] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Berlin: Springer, Berlin · Zbl 1103.90003 · doi:10.1007/978-3-540-24777-7 |
| [11] | Martello, S.; Pisinger, D.; Toth, P., Dynamic programming and strong bounds for the 0?1 knapsack problem, Management Science, 45, 414-424 (1999) · Zbl 1231.90338 · doi:10.1287/mnsc.45.3.414 |
| [12] | Merkle, M.; Hellman, M., Hiding information and signatures in trapdoor knapsacks, IEEE Transactions on Information Theory, 24, 5, 525-530 (1978) · Zbl 1487.94132 · doi:10.1109/TIT.1978.1055927 |
| [13] | Perboli, G.; Gobbato, L.; Perfetti, F., Packing problems in transportation and supply chain: New problems and trends, Procedia - Social and Behavioral Sciences, 111, 672-681 (2014) · doi:10.1016/j.sbspro.2014.01.101 |
| [14] | Pferschy, U.; Schauer, J., The knapsack problem with conflict graphs, Journal of Graph Algorithms and Applications, 13, 233-249 (2009) · Zbl 1194.68175 · doi:10.7155/jgaa.00186 |
| [15] | Shi, X.; Wu, L.; Meng, X., A new optimization model for the sustainable development: Quadratic knapsack problem with conflict graphs, Sustainability, 9, 2, 1-10 (2017) · doi:10.3390/su9020236 |
| [16] | Yamada, T.; Kataoka, S.; Watanabe, K., Heuristic and exact algorithms for the disjunctively constrained knapsack problem, Information Processing Society of Japan Journal, 43, 9, 2864-2870 (2002) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
