Application and Assessment of Divide-and-Conquer-Based Heuristic Algorithms for Some Integer Optimization Problems
DOI:
https://doi.org/10.2298/YJOR2111015030MKeywords:
Divide-and-conquer method, multidimensional knapsack problem, bin packing problem, traveling salesman problem, Monte Carlo simulations, method’s efficiencyAbstract
In this paper three heuristic algorithms using the Divide-and-Conquer paradigm are developed and assessed for three integer optimizations problems: Multidimensional Knapsack Problem (d-KP), Bin Packing Problem (BPP) and Travelling Salesman Problem (TSP). For each case, the algorithm is introduced, together with the design of numerical experiments, in order to empirically establish its performance from both points of view: its computational time and its numerical accuracy.References
F. A. Morales and J. A. Martínez, “Analysis of Divide-and-Conquer strategies for the 0-1 minimization problem,” Journal of Combinatorial Optimization, vol. 40, no. 1, pp. 234 - 278, 2020.
G. Diubin and A. Korbut, “Greedy algorithms for the minimization knapsack problem: Average behavior,” Journal of Computer and Systems Sciences International, vol. 47, no. 1, pp. 14-24, 2008.
A. Fréville and G. Plateau, “Heuristics and reduction methods for multiple constraints 0- 1 linear programming problems,” European Journal of Operational Research, vol. 24, pp. 206-215, 1986.
R. Loulou and E. Michaelides, “New greedy-like heuristics for the multidimensional 0-1 knapsack problem,” Oper. Res., vol. 27, pp. 1101-1114, 1979.
A. M. Frieze, M. Clarke et al., “Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses,” European Journal of Operational Research, vol. 15, no. 1, pp. 100-109, 1984.
O. Oguz and M. Magazine, “A polynomial time approximation algorithm for the multidimensional 0/1 knapsack problem,” Univ. Waterloo Working Paper, 1980.
B. Gavish and H. Pirkul, “Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality,” Mathematical Programming, vol. 31, pp. 78-105, 1985.
A. Volgenant and J. Zoon, “An improved heuristic for multidimensional 0-1 knapsack problems,” Journal of the Operational Research Society, vol. 41, pp. 963-970, 1990.
P. C. Chu and J. E. Beasley, “A genetic algorithm for the multidimensional knapsack problem,” Journal of Heuristics, vol. 4, pp. 63-86, 1998.
X. Lai, J.-K. Hao, and D. Yue, “Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem,” European Journal of Operational Research, vol. 274, no. 1, pp. 35-48, 2019. [Online]. Available: https://ideas.repec.org/a/eee/ejores/ v274y2019i1p35-48.html
W. F. de la Vega and G. S. Lueker, “Bin packing can be solved within 1 + ε in linear time,” Combinatorica, vol. 1, pp. 349-355, 1981.
N. Karmarkar and R. M. Karp, “An efficient approximation scheme for the one-dimensional bin-packing problem,” in 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), 1982, pp. 312-320.
A. van Vliet, “An improved lower bound for on-line bin packing algorithms,” Information Processing Letters, vol. 43, no. 5, pp. 277-284, 1992. [Online]. Available: https://www.sciencedirect.com/science/article/pii/002001909290223I
A. C.-C. Yao, “New algorithms for bin packing,” J. ACM, vol. 27, no. 2, p. 207-227, Apr. 1980. [Online]. Available: https://doi.org/10.1145/322186.322187
C. C. Lee and D. T. Lee, “A simple on-line bin-packing algorithm,” J. ACM, vol. 32, no. 3, p. 562-572, Jul. 1985. [Online]. Available: https://doi.org/10.1145/3828.3833
E. G. Coffman, M. R. Garey, and D. S. Johnson, Approximation Algorithms for Bin-Packing - An Updated Survey. Vienna: Springer Vienna, 1984, pp. 49-106. [Online]. Available: https://doi.org/10.1007/978-3-7091-4338-4 3
T. Fischer and P. Merz, “Reducing the size of traveling salesman problem instances by fixing edges,” in Evolutionary Computation in Combinatorial Optimization, C. Cotta and J. van Hemert, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 72-83.
C. Walshaw, “A multilevel approach to the Travelling Salesman Problem,” Oper. Res., vol. 50, pp. 862-877, 2002.
C. Walshaw, “Multilevel refinement for combinatorial optimisation problems,” Annals of Operations Research, vol. 131, pp. 325-372, 2004.
K. Ishikawa, I. Suzuki, M. Yamamoto, and M. Furukawa, “Solving for large-scale traveling salesman problem with divide-and-conquer strategy,” SCIS & ISIS, vol. 2010, pp. 1168- 1173, 2010.
B.-R. C. V. C. W. Applegate, David, “On the solution of traveling salesman problems.” Documenta Mathematica, pp. 645-656, 1998. [Online]. Available: http://eudml.org/doc/233207
D. L. Applegate, R. E. Bixby, V. Chv´atal, and W. J. Cook, “Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems.” Math. Program., vol. 97, no. 1-2, pp. 91-153, 2003. [Online]. Available: http: //dblp.uni-trier.de/db/journals/mp/mp97.html#ApplegateBCC03
G. Dantzig, R. Fulkerson, and S. Johnson, “Solution of a large-scale traveling-salesman problem,” Journal of the Operations Research Society of America, vol. 2, no. 4, pp. 393-410, 1954. [Online]. Available: http://www.jstor.org/stable/166695
D. S. Johnson, “Local optimization and the traveling salesman problem,” in Proceedings of the 17th International Colloquium on Automata, Languages and Programming, ser. ICALP ’90. Berlin, Heidelberg: Springer-Verlag, 1990, p. 446-461.
S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Oper. Res., vol. 21, pp. 498-516, 1973.
D. Applegate, W. Cook, and A. Rohe, “Chained Lin-Kernighan for large Traveling Salesman Problems,” INFORMS Journal on Computing, vol. 15, no. 1, pp. 82-92, 2003. [Online]. Available: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.15.1.82.15157
W. Cook and P. Seymour, “Tour merging via branch-decomposition,” INFORMS Journal on Computing, vol. 15, no. 3, pp. 233-248, 2003. [Online]. Available: https://pubsonline.informs.org/doi/abs/10.1287/ijoc.15.3.233.16078
P. Billinsgley, Probability and Measure, ser. Wiley Series in Probability and Mathematical Statistics. New York, NY: John Wiley & Sons, Inc., 1995.
S. K. Thompson, Sampling, ser. Wiley Series in Probability and Statistics. New York: John Wiley & Sons, Inc., 2012.
R. Mansini and M. G. Speranza, “Coral: An exact algorithm for the multidimensional knapsack problem,” INFORMS J. on Computing, vol. 24, no. 3, p. 399-415, Jul. 2012. [Online]. Available: https://doi.org/10.1287/ijoc.1110.0460
S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations. USA: John Wiley & Sons, Inc., 1990.
H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems, ser. Discrete Mathematics and its Applications. Ney York: Springer, Berlin, Heidelberg, 2004.
B. Korte and J. Vygen, Combinatorial Optimization: Theory and Algorithms, 5th ed. Springer Publishing Company, Incorporated, 2012.
G. Dósa, R. Li, X. Han, and Z. Tuza, “Tight absolute bound for first fit decreasing binpacking: Ffd(l)11/9 opt(l)+6/9,” Theoretical Computer Science, vol. 510, pp. 13-61, 2013. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0304397513006774
D. Bertsimas and J. N. Tritsiklis, Introduction to Linear Optimization. Belmont, MA: Athena Scientific and Dynamic Ideas, LLC, 1997.
B. Fritzke and P. Wilke, “Flexmap-a neural network for the traveling salesman problem with linear time and space complexity,” in [Proceedings] 1991 IEEE International Joint Conference on Neural Networks, 1991, pp. 929-934 vol.2.
D. S. Johnson and L. A. McGeoch, Experimental Analysis of Heuristics for the STSP. Boston, MA: Springer US, 2007, pp. 369-443. [Online]. Available: https://doi.org/10.1007/0-306-48213-4 9
F. A. Morales and J. A. Martínez, “Expected performance and worst case scenario analysis of the Divide-and-Conquer method for the 0-1 knapsack problem,” arXiv, 2020. [Online]. Available: https://arxiv.org/abs/2008.04124
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
