Efficiency of Robust Heuristic Gradient Based Enumerative and Tunneling Algorithms for Constrained Integer Programming Problems

Authors: Vijaya K. Srivastava, Davide Spinello

Abstract:

This paper presents performance of two robust gradient-based heuristic optimization procedures based on 3ⁿ enumeration and tunneling approach to seek global optimum of constrained integer problems. Both these procedures consist of two distinct phases for locating the global optimum of integer problems with a linear or non-linear objective function subject to linear or non-linear constraints. In both procedures, in the first phase, a local minimum of the function is found using the gradient approach coupled with hemstitching moves when a constraint is violated in order to return the search to the feasible region. In the second phase, in one optimization procedure, the second sub-procedure examines 3ⁿ integer combinations on the boundary and within hypercube volume encompassing the result neighboring the result from the first phase and in the second optimization procedure a tunneling function is constructed at the local minimum of the first phase so as to find another point on the other side of the barrier where the function value is approximately the same. In the next cycle, the search for the global optimum commences in both optimization procedures again using this new-found point as the starting vector. The search continues and repeated for various step sizes along the function gradient as well as that along the vector normal to the violated constraints until no improvement in optimum value is found. The results from both these proposed optimization methods are presented and compared with one provided by popular MS Excel solver that is provided within MS Office suite and other published results.

Keywords: Constrained integer problems, enumerative search algorithm, Heuristic algorithm, tunneling algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1130313

References:

[1] H. P. Williams, (2009). Logic and integer programming. International Series in Operations Research & Management Science. 130. ISBN 978-0-387-92280-5.
[2] D. J. Wilde and C. S. Beightler, Foundations of Optimization, Prentice-Hall, Inc., Englewood Cliffs, New Jersey (1967).
[3] Leon S. Lasdon, Richard L. Fox, Margery W. Ratner, Nonlinear Optimization Using the Generalized Reduced Gradient Method, Office of Naval Research: Technical Memorandum No. 325, October 1973, distributed by National Technical Information Service, U. S. Department of Commerce.
[4] V. K. Srivastava and A. Fahim, A Two-Phase Optimization Procedure for Integer Programming Problems, An International Journal Computers & Mathematics with Applications, 42, (2001) 1585-1595.
[5] Vijaya K. Srivastava and Davide Spinello. A Two-Phase Combined Gradient-Tunneling Based Algorithm for Constrained Integer Programming Problems, Journal of Information & Optimization Sciences, Vol. 36 (2015), No.4, pp. 339-365: DOI:10.1080/02522667.2014.932092.
[6] A. P. French, A. C. Robinson & J. M. Wilson, Using a Hybrid Genetic-Algorithm/Branch and Bound Approach to Solve Feasibility and Optimization Integer Programming Problems, Journal of Heuristics (2001) 7: 551. doi:10.1023/A:1011921025322.
[7] J. Kennedy, R. Eberhart: Particle swarm optimization (C)// Proceedings of IEEE International Conference on Neural Networks. Perth, WA: IEEE Press, 1995: 1942−1948.
[8] Y. Tan, G. Tan, G. & S. Deng, Hybrid particle swarm optimization with chaotic search for solving integer and mixed integer programming problems J. Cent. South Univ. (2014) 21: 2731. doi:10.1007/s11771-014-2235-6.
[9] A. V. Levy and A. Montalvo, The tunneling algorithm for the global minimization of functions, SIAM J, sci.stat. comput, Vol 6, No 1, 15-29 (January 1985).
[10] A. H. Land and A. Doig, An automatic method of solving discrete programming problems, Econometrica 28, 497-520, (1960).
[11] R. E. Gomory, An all-integer programming algorithm, In Industrial Scheduling, (Edited by J. F. Muth and G. L. Thompson), Chapter 13, Prentice Hall, Englewood Cliffs, N. J. (1963).
[12] S. M. Roberts and H. L. Lyvers, The gradient method in process control, Industrial and Engineering Chemistry 53 (1), 877-882 (November 1961).
[13] W. R. Klingman and D. M. Himmelblau, Nonlinear programming with the aid of a multiple-gradient summation technique, Journal of the Association of Computing Machinery 11, (4),400-415, (October 1964).
[14] G. R. Walsh, Methods of Optimization, John Wiley and Sons, 1975
[15] V.R. Prasad and W. Kuo, Reliability optimization of coherent systems, IEEE Transactions on Reliability, Vol 49, No 3, 323-330 (September 2000).
[16] M. Chern and J. Jon, Reliability optimization problems with multiple constraints, IEEE Transactions on Reliability, R-35 (4), 431-436 (October1986).
[17] G. L. Nemhauser and L. A. Wolsey, Integer programming and combinatorial optimization, p443, John Wiley & Sons, (1988).
[18] F.J. Gould. Nonlinear tolerance programming. In F.A. Lootsma, editor, Numerical Methods for Nonlinear Optimization, pages 349-366 Academic Press, 1988.
[19] H.-N. Huynh, H. J. Connell, and S. Kumar. Random search method for integer programming, Article; article/report, 1987. Online: http://trove.nla.gov.au/work/13720937.
[20] Integer Optimization and the Network Models: http://home.ubalt.edu/ntsbarsh/opre640a/partIII.htm.
[21] C. A. Floudas and P. M. Pardalos. A Collection of Test Problems for Constrained Global Optimization Algorithm, chapter 2. Lecture Notes in Computer Science Springer, 1990.
[22] Q. Zheng, D. Zhuang, Integral global optimization: Algorithms, implementations and numerical tests, Journal of Global Optimization 7 (4) (1995) 421–454.
[23] W. Zhu, H. Fan, A discrete dynamic convexized method for nonlinear integer programming, Journal of Computational and Applied Mathematics 223 (2009) 356–373.
[24] C. Mohan, 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 14 (1999) 103–132.