Abstract
A discrete filled function method is developed in this paper to solve discrete global optimization problems over “strictly pathwise connected domains.” Theoretical properties of the proposed discrete filled function are investigated and a solution algorithm is proposed. Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the applicability and efficiency of the proposed method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Beck and M. Teboulle, “Global optimality conditions for quadratic optimization problems with binary constraints,” SIAM Journal on Optimization, vol. 11, no. 1, pp. 179–188, 2000.
W. Conley, Computer Optimization Techniques, Petrocelli Books Inc.: New York, 1980.
M.W. Cooper, “A survey of methods for pure nonlinear programming,” Management Science, vol. 27, no. 3, pp. 353–361, 1981.
M.W. Cooper, “Nonlinear integer programming for various forms of constraints,” Naval Research Logistics Quarterly, vol. 29, no. 4, pp. 585–592, 1983.
L.C.W. Dixon, J. Gomulka, and S.E. Herson, “Reflection on global optimization problems,” in Optimization in Action: Proceedings of the Conference on Optimization in Action held at the University of Bristol in January 1975, L.C.W. Dixon (Ed.), New York, 1976 pp. 398–435.
M.L. Fisher, “The Lagrangian relaxation method for solving integer programming problems,” Management Science, vol. 27, no. 1, pp. 1–18, 1981.
R.-P. Ge, “A filled function method for finding a global minimizer of a function of several variables,” Mathematical Programming, vol. 46, no. 2, pp. 191–204, 1990.
R.-P. Ge and C.-B. Huang, “A continuous approach to nonlinear integer programming,” Applied Mathematics and Computation, vol. 34, no. 1, pp. 39–60, 1989.
R.-P. Ge and Y.-F. Qin, “A class of filled functions for finding global minimizers of a function of several variables,” Journal of Optimization Theory and Applications, vol. 54, no. 2, pp. 241–252, 1987.
A.M. Geoffirion, “Lagrangian relaxation for integer programming,” Mathematical Programming Study, vol. 2, pp. 82–114, 1974.
A.A. Goldstein and J.F. Price, “On descent from local minima,” Mathematics of Computation, vol. 25, no. 115, pp. 569–574, 1971.
O.K. Gupta and A. Ravindran, “Branch and bound experiments in convex nonlinear integer programming,” Management Science, vol. 31, no. 12, pp. 1533–1546, 1985.
Q.-M. Han and J.-Y. Han, “Revised filled function methods for global optimization,” Applied Mathematics and Computation, vol. 119, nos. 2/3, pp. 217–228, 2001.
W. Hock and K. Schittkowski, Test Examples for Nonlinear Programming Codes, Springer-Verlag, New York, 1981.
F. Körner, “A new branching rule for the branch and bound algorithm for solving nonlinear integer programming problems,” BIT, vol. 28, no. 3, pp. 701–708, 1988.
A.V. Levy and A. Montalvo, “The tunneling algorithm for the global minimization of functions,” SIAM Journal on Scientific and Statistical Computing, vol. 6, no. 1, pp. 15–29, 1985.
D. Li and X.-L. Sun, “Success guarantee of dual search in integer programming: pth power Lagrangian Method,” Journal of Global Optimization, vol. 18, pp. 235–254, 2000.
D. Li and D.J. White, “pth power Lagrangian Method for Integer Programming,” Annals of Operations Research, vol. 98, pp. 151–170, 2000.
V.V. Litinetski and B.M. Abramzon, “MARS—A multi-start adaptive random search method for global constrained optimization in engineering applications,” Engineering Optimization, vol. 30, pp. 125–154, 1998.
X. Liu, “Finding global minima with a computable filled function,” Journal of Global Optimization, vol. 19, no. 2, pp. 151–161, 2001.
R. Luus and T.H.I. Jaakola, “Optimization by direct search and systematic reduction of the size of the search region,” AIChE Journal, vol. 19, no. 4, pp. 760–765, 1973.
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, pp. 103–132, 1999.
J.J. Moré, B.S. Garbow, and K.E. Hillstrom, “Testing unconstrained optimization software,” ACM Transactions on Mathematical Software, vol. 7, no. 1, pp. 17–41, 1981.
W.L. Price, “Global optimization by controlled random search,” Journal of Optimization: Theory and Applications, vol. 40, pp. 333–348, 1983.
K. Schittkowski, More Test Examples for Nonlinear Programming Codes, Springer-Verlag, 1987.
X.-L. Sun and D. Li, “Asymptotic strong duality for bounded integer programming: A logarithmic-exponential dual formulation,” Mathematics of Operations Research, vol. 25, pp. 625–644, 2000.
Z. Xu, H.-X. Huang, P.M. Pardalos, and C.-X. Xu, “Filled functions for unconstrained global optimization,” Journal of Global Optimization, vol. 20, no. 1, pp. 49–65, 2001.
X.Q. Yang and C.J. Goh, “A nonlinear Lagrangian function for discrete optimization problems,” in From Local to Global Optimization, A. Migdalas, P. M. Pardalos, and P. Värbrand (Eds.), Kluwer Academic Publishers, Dordrecht, 2001.
L.-S. Zhang, F. Gao, and W.-X. Zhu, “Nonlinear integer programming and global optimization,” Journal of Computational Mathematics, vol. 17, no. 2, pp. 179–190, 1999.
L.-S. Zhang, C.-K. Ng, D. Li, and W.-W. Tian, “A new filled function method for global optimization,” Journal of Global Optimization, vol. 28, no. 1, pp. 17–43, 2004.
Q. Zheng and D.-M. Zhuang, “‘Integral global minimization: Algorithms, implementations and numerical tests,” Journal of Global Optimization, vol. 7, no. 4, pp. 421–454, 1995.
W.-X. Zhu, “An approximate algorithm for nonlinear integer programming,” Applied Mathematics and Computation, vol. 93, nos. 2/3, pp. 183–193, 1998.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ng, CK., Zhang, LS., Li, D. et al. Discrete Filled Function Method for Discrete Global Optimization. Comput Optim Applic 31, 87–115 (2005). https://doi.org/10.1007/s10589-005-0985-7
Received:
Revised:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10589-005-0985-7