zbMATH — the first resource for mathematics

An auxiliary function method for global minimization in integer programming. (English) Zbl 1235.90095
Summary: An auxiliary function method is proposed for finding the global minimizer of integer programming problem. Firstly, we propose a method to transform the original problem into an integer programming with box constraint, which does not change the properties of the original problem. For the transformed problem, we propose an auxiliary function to escape from the current local minimizer and to get a better one. Then, based on the proposed auxiliary function, a new algorithm to find the global minimizer of integer programming is proposed. At last, numerical results are given to demonstrate the effectiveness and efficiency of the proposed method.

90C10 Integer programming
Full Text: DOI
[1] J. Bang-Jensen, G. Gutin, and A. Yeo, “When the greedy algorithm fails,” Discrete Optimization, vol. 1, no. 2, pp. 121-127, 2004. · Zbl 1087.90059 · doi:10.1016/j.disopt.2004.03.007
[2] V. Chv√°tal, “A greedy heuristic for the set-covering problem,” Mathematics of Operations Research, vol. 4, no. 3, pp. 233-235, 1979. · Zbl 0443.90066 · doi:10.1287/moor.4.3.233
[3] G. Dobson, “Worst-case analysis of greedy heuristics for integer programming with nonnegative data,” Mathematics of Operations Research, vol. 7, no. 4, pp. 515-531, 1982. · Zbl 0498.90061 · doi:10.1287/moor.7.4.515
[4] A. Federgruen and H. Groenevelt, “The greedy procedure for resource allocation problems: necessary and sufficient conditions for optimality,” Operations Research, vol. 34, no. 6, p. 909-918 (1987), 1986. · Zbl 0619.90051 · doi:10.1287/opre.34.6.909
[5] C. Mohan and H. T. Nguyen, “A controlled random search technique incorporating the simulated annealing concept for solving integer and mixed integer global optimization problems,” Computational Optimization and Applications, vol. 14, no. 1, pp. 103-132, 1999. · Zbl 0970.90053 · doi:10.1023/A:1008761113491
[6] S. L. Rosen and C. M. Harmonosky, “An improved simulated annealing simulation optimization method for discrete parameter stochastic systems,” Computers & Operations Research, vol. 32, no. 2, pp. 343-358, 2005. · Zbl 1073.90026 · doi:10.1016/S0305-0548(03)00240-5
[7] J. Cai and G. Thierauf, “Evolution strategies for solving discrete optimization problems,” Advances in Engineering Software, vol. 25, no. 2-3, pp. 177-183, 1996. · Zbl 05470425 · doi:10.1016/0965-9978(95)00104-2
[8] N. Turkkan, “Discrete optimization of structures using a floating-point genetic algorithm,” in Proceedings of the Annual Conference of the Canadian Society for Civil Engineering, Moncton, Canada, 2003. · Zbl 05470425 · doi:10.1016/0965-9978(95)00104-2
[9] S. J. Wu and P. T. Chow, “Steady-state genetic algorithms for discrete optimization of trusses,” Computers and Structures, vol. 56, no. 6, pp. 979-991, 1995. · Zbl 0900.73943 · doi:10.1016/0045-7949(94)00551-D
[10] F. Glover, “Tabu search and adaptive memory programming C advances applications, and challenges,” in Interfaces in Computer Science and Operations Research: Advances in Metaheuristics, Optimization, and Stochastic Modeling Technologies, R. S. Barr, R. V. Helgason, and J. L. Kennington, Eds., pp. 1-75, Kluwer Academic Publishers, 1996. · Zbl 0882.90111
[11] L. Michel and P. Van Hentenryck, “A simple tabu search for warehouse location,” European Journal of Operational Research, vol. 157, no. 3, pp. 576-591, 2004. · Zbl 1067.90054 · doi:10.1016/S0377-2217(03)00247-9
[12] S. F. Woon and V. Rehbock, “A critical review of discrete filled function methods in solving nonlinear discrete optimization problems,” Applied Mathematics and Computation, vol. 217, no. 1, pp. 25-41, 2010. · Zbl 1200.65048 · doi:10.1016/j.amc.2010.05.009
[13] Y. Shang and L. Zhang, “A filled function method for finding a global minimizer on global integer optimization,” Journal of Computational and Applied Mathematics, vol. 181, no. 1, pp. 200-210, 2005. · Zbl 1078.65054 · doi:10.1016/j.cam.2004.11.030
[14] C. K. Ng, D. Li, and L. S. Zhang, “Discrete global descent method for discrete global optimization and nonlinear integer programming,” Journal of Global Optimization, vol. 37, no. 3, pp. 357-379, 2007. · Zbl 1156.90006 · doi:10.1007/s10898-006-9053-9
[15] Y. l. Shang and L. Zhang, “Finding discrete global minima with a filled function for integer programming,” European Journal of Operational Research, vol. 189, no. 1, pp. 31-40, 2008. · Zbl 1152.90541 · doi:10.1016/j.ejor.2007.05.028
[16] Y. Yongjian and L. Yumei, “A new discrete filled function algorithm for discrete global optimization,” Journal of Computational and Applied Mathematics, vol. 202, no. 2, pp. 280-291, 2007. · Zbl 1115.65068 · doi:10.1016/j.cam.2006.02.032
[17] Y. Yang, Z. Wu, and F. Bai, “A filled function method for constrained nonlinear integer programming,” Journal of Industrial and Management Optimization, vol. 4, no. 2, pp. 353-362, 2008. · Zbl 1161.90445 · doi:10.3934/jimo.2008.4.271 · aimsciences.org
[18] Y. H. Gu and Z. Y. Wu, “A new filled function method for nonlinear integer programming problem,” Applied Mathematics and Computation, vol. 173, no. 2, pp. 938-950, 2006. · Zbl 1091.65055 · doi:10.1016/j.amc.2005.04.025
[19] C. K. Ng, L. S. Zhang, D. Li, and W. W. Tian, “Discrete filled function method for discrete global optimization,” Computational Optimization and Applications, vol. 31, no. 1, pp. 87-115, 2005. · Zbl 1114.90125 · doi:10.1007/s10589-005-0985-7
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.