×

zbMATH — the first resource for mathematics

A critical review of discrete filled function methods in solving nonlinear discrete optimization problems. (English) Zbl 1200.65048
Summary: Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison.

MSC:
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
minpack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bang-Jensen, J.; Gutin, G.; Yeo, A., When the greedy algorithm fails, Discrete optimization, 1, 121-127, (2004) · Zbl 1087.90059
[2] Cai, J.; Thierauf, G., Evolution strategies for solving discrete optimization problems, Advances in engineering software, 25, 177-183, (1996)
[3] D. Chakrabarty, N.R. Devanur, V.V. Vazirani, New geometry-inspired relaxations and algorithms for the Metric Steiner Tree Problem, in: A. Lodi, A. Panconesi, G. Rinaldi (Eds.), Integer Programming and Combinatorial Optimization: 13th International Conference, IPCO 2008 Bertinoro, 2008 Proceedings, Italy, May 26-28, Springer-Verlag, Berlin, Heidelberg, 2008, pp. 344-358. · Zbl 1143.90376
[4] Chvatal, V., A greedy heuristic for the set-covering problem, Mathematics of operations research, 4, 3, 233-235, (1979) · Zbl 0443.90066
[5] ()
[6] Dobson, G., Worst-case analysis of greedy heuristics for integer programming with nonnegative data, Mathematics of operations research, 7, 4, 515-531, (1982) · Zbl 0498.90061
[7] A. Etzel, Mixed discrete optimization of multiple-valued systems, in: 27th International Symposium on Multiple-Valued Logic Proceedings, Antigonish, Canada, May 28-30, 1997, pp. 259-264.
[8] Federgruen, A.; Groenevelt, H., The greedy procedure for resource allocation problems: necessary and sufficient conditions for optimality, Operations research, 34, 6, 909-918, (1986) · Zbl 0619.90051
[9] Fisher, M.L., The Lagrangian relaxation method for solving integer programming problems, Management science, 50, 12, 1861-1871, (2004)
[10] R. Fukasawa, M. Goycoolea, On the exact separation of mixed integer knapsack cuts, in: M. Fischetti, D.P. Williamson (Eds.), Integer Programming and Combinatorial Optimization: 12th International Conference, IPCO 2007 Ithaca, 2007 Proceedings, New York, June 25-27, Springer-Verlag, Berlin, Heidelberg, 2007, pp. 225-239. · Zbl 1136.90418
[11] Ge, R., A filled function method for finding a global minimizer of a function of several variables, Mathematical programming, 46, 1, 191-204, (1990) · Zbl 0694.90083
[12] Ge, R.; Huang, C., A continuous approach to nonlinear integer programming, Applied mathematics and computation, 34, 1, 39-60, (1989) · Zbl 0682.90067
[13] Geoffrion, A.M., Lagrangian relaxation for integer programming, Mathematical programming study, 2, 82-114, (1974) · Zbl 0395.90056
[14] Glover, F., Tabu search and adaptive memory programming – advances applications, and challenges, (), 1-75 · Zbl 0882.90111
[15] Goldstein, A.A.; Price, J.F., On descent from local minima, Mathematics of computation, 25, 115, 569-574, (1971) · Zbl 0223.65020
[16] Gu, Y.H.; Wu, Z.Y., A new filled function method for nonlinear integer programming problem, Applied mathematics and computation, 173, 2, 938-950, (2006) · Zbl 1091.65055
[17] O. Günlük, J. Linderoth, Perspective relaxation of mixed integer nonlinear programs with indicator variables, in: A. Lodi, A. Panconesi, G. Rinaldi (Eds.), Integer Programming and Combinatorial Optimization: 13th International Conference, IPCO 2008 Bertinoro, 2008 Proceedings, Italy, May 26-28, Springer-Verlag, Berlin, Heidelberg, 2008, pp. 1-16. · Zbl 1143.90364
[18] Gupta, O.K.; Ravindran, A., Branch and bound experiments in convex nonlinear integer programming, Management science, 31, 12, 1533-1546, (1985) · Zbl 0591.90065
[19] Hock, W.; Schittkowski, K., Test examples for nonlinear programming codes, (1980), Springer-Verlag New York · Zbl 0393.90072
[20] Lee, W.J.; Cabot, A.V.; Venkataramanan, M.A., A branch and bound algorithm for solving separable convex integer programming problems, Computers and operations research, 21, 9, 1011-1024, (1994) · Zbl 0815.90116
[21] Madsen, K.; Žilinskas, J., Testing branch-and-bound methods for global optimization, (2000), IMM Department of Mathematical Modelling, Technical University of Denmark
[22] Marsten, R.E.; Morin, T.L., A hybrid approach to discrete mathematical programming, Mathematical programming, 14, 21-40, (1978) · Zbl 0388.90055
[23] Michel, L.; Van Hentenryck, P., A simple tabu search for warehouse location, European journal of operational research, 157, 576-591, (2004) · Zbl 1067.90054
[24] Mohan, C.; Nguyen, H.T., A controlled random search technique incorporating the simulated annealing concept for solving integer and mixed integer global optimization problems, Computational optimization and applications, 14, 103-132, (1999) · Zbl 0970.90053
[25] Moré, J.J.; Garbow, B.S.; Hillstrom, K.E., Testing unconstrained optimization software, ACM transactions on mathematical software, 7, 1, 17-41, (1981) · Zbl 0454.65049
[26] Ng, C.K.; Li, D.; Zhang, L.S., Filled function approaches to nonlinear integer programming: a survey, (), 1-20
[27] Ng, C.K.; Li, D.; Zhang, L.S., Discrete global descent method for discrete global optimization and nonlinear integer programming, Journal of global optimization, 37, 3, 357-379, (2007) · Zbl 1156.90006
[28] Ng, C.K.; Zhang, L.S.; Li, D.; Tian, W.W., Discrete filled function method for discrete global optimization, Computational optimization & applications, 31, 1, 87-115, (2005) · Zbl 1114.90125
[29] Rim, M.; Jain, R., Lower-bound performance estimation for the high-level synthesis scheduling problem, IEEE transactions on computer-aided design of integrated circuits and systems, 13, 4, 51-458, (1994)
[30] Rosen, S.L.; Harmonosky, C.M., An improved simulated annealing simulation optimization method for discrete parameter stochastic systems, Computers and operations research, 32, 343-358, (2005) · Zbl 1073.90026
[31] Schittkowski, K., More test examples for nonlinear programming codes, (1987), Springer-Verlag New York · Zbl 0658.90060
[32] Shang, Y.; Zhang, L., A filled function method for finding a global minimizer on global integer optimization, Journal of computational and applied mathematics, 181, 1, 200-210, (2005) · Zbl 1078.65054
[33] Shang, Y.; Zhang, L., Finding discrete global minima with a filled function for integer programming, European journal of operational research, 189, 1, 31-40, (2008) · Zbl 1152.90541
[34] N. Turkkan, Discrete optimization of structures using a floating-point genetic algorithm, in: Annual Conference of the Canadian Society for Civil Engineering, Moncton, Canada, June 4-7, 2003.
[35] S.F. Woon, Global Algorithms for Nonlinear Discrete Optimization and Discrete-Valued Optimal Control Problems, Ph.D. Thesis, Department of Mathematics and Statistics, Curtin University of Technology, 2009.
[36] Woon, S.F.; Rehbock, V.; Loxton, R.C., Global optimization method for continuous-time sensor scheduling, Special issue of dynamics and systems theory, 10, 2, 175-188, (2010) · Zbl 1225.37120
[37] Wu, S.J.; Chow, P.T., Steady-state genetic algorithms for discrete optimization of trusses, Computers and structures, 56, 6, 979-991, (1995) · Zbl 0900.73943
[38] Z. Wu, B.W. Wah, The theory of discrete Lagrange multipliers for nonlinear discrete optimization, in: J. Jaffar (Ed.), Principles and Practice of Constraint Programming: 5th International Conference, CP 1999, 1999 Proceedings, Alexandria, Virginia, October 11-14, Springer-Verlag, Berlin, Heidelberg, 1999, pp. 28-42. · Zbl 0965.90051
[39] Z. Wu, B.W. Wah, An efficient global-search strategy in discrete Lagrangian methods for solving hard satisfiability problems, in: Proceedings of the 17th National Conference on Artificial Intelligence, Austin, Texas, July 30-August 3, 2000, pp. 310-315.
[40] X. Xu, P.J. Antsaklis, Optimal control of switched autonomous systems, in: Proceedings of the 41st IEEE Conference on Decision and Control, Las Vegas, Nevada, December 10-13, vol. 4, 2002, pp. 4401-4406. · Zbl 1016.20015
[41] Yang, X.Q.; Goh, C.J., A nonlinear Lagrangian function for discrete optimization problems, (), 291-304 · Zbl 1004.90051
[42] Yang, Y.; Liang, Y., A new discrete filled function algorithm for discrete global optimization, Journal of computational and applied mathematics, 202, 2, 280-291, (2007) · Zbl 1115.65068
[43] Yang, Y.; Wu, Z.; Bai, F., A filled function method for constrained nonlinear integer programming, Journal of industrial and management optimization, 4, 2, 353-362, (2008) · Zbl 1161.90445
[44] Yang, Y.; Zhang, L., A gradually descent method for discrete global optimization, Journal of Shanghai university (English edition), 11, 1, 39-44, (2007) · Zbl 1174.90711
[45] A. Zanette, M. Fischetti, E. Balas, Can pure cutting plane algorithms work? in: A. Lodi, A. Panconesi, G. Rinaldi (Eds.), Integer Programming and Combinatorial Optimization: 13th International Conference, IPCO 2008 Bertinoro, Italy, May 26-28, 2008 Proceedings, Springer-Verlag, Berlin, Heidelberg, 2008, pp. 416-434. · Zbl 1143.90398
[46] Zhu, W., An approximate algorithm for nonlinear integer programming, Applied mathematics and computations, 93, 2-3, 183-193, (1998) · Zbl 0938.90052
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.