Cross-entropy and rare events for maximal cut and partition problems

ABSTRACT

We show how to solve the maximal cut and partition problems using a randomized algorithm based on the cross-entropy method. For the maximal cut problem, the proposed algorithm employs an auxiliary Bernoulli distribution, which transforms the original deterministic network into an associated stochastic one, called the associated stochastic network (ASN). Each iteration of the randomized algorithm for the ASN involves the following two phases:(1) Generation of random cuts using a multidimensional Ber(p) distribution and calculation of the associated cut lengths (objective functions) and some related quantities, such as rare-event probabilities.(2) Updating the parameter vector p on the basis of the data collected in the first phase.We show that the Ber(p) distribution converges in distribution to a degenerated one, Ber(pd^*), pd^* = (pd,1,...,pd,n) in the sense that someelements of pd^*, will be unities and the rest zeros. The unity elements of pd^* uniquely define a cut which will be taken as the estimate of the maximal cut. A similar approach is used for the partition problem. Supporting numerical results are given as well. Our numerical studies suggest that for the maximal cut and partition problems the proposed algorithm typically has polynomial complexity in the size of the network.

REFERENCES

• 1: Emile Aarts , Jan Korst, Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing, John Wiley & Sons, Inc., New York, NY, 1989
• 2: Emile Aarts , Jan K. Lenstra, Local Search in Combinatorial Optimization, John Wiley & Sons, Inc., New York, NY, 1997
• 3: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 4: Ali, S. M. and Silvey, S. D. 1966. A general class of coefficients of divergence of one distribution from another. J. Roy. Stat. Soc. Ser. B 28, 131--142.
• 5: Sigrún Andradóttir, A method for discrete stochastic optimization, Management Science, v.41 n.12, p.1946-1961, Dec. 1995 [doi>10.1287/mnsc.41.12.1946]
• 6: Andradóttir, S. 1996. A global search method for discrete stochastic optimization. SIAM J. Optim. 6, 513--530.
• 7: Harry Cohn , Mark Fielding, Simulated Annealing: Searching for an Optimal Temperature Schedule, SIAM Journal on Optimization, v.9 n.3, p.779-802, 1999 [doi>10.1137/S1052623497329683]
• 8: Colorni, A., Dorigo, M., Maffioli, F., Maniezzo, V., Righini, G., and Trubian, M. 1996. Heuristics from nature for hard combinatorial problems. Int. Trans. Oper. Res. 3, 1--21.
• 9: Di Caro, G. and Dorigo, M. 1998. AntNet: Distributed stigmergetic control for communications networks. J. Artif. Intel. Res. 9, 317--365.
• 10: Marco Dorigo , Gianni Di Caro, The ant colony optimization meta-heuristic, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 11: Marco Dorigo , Gianni Di Caro , Luca M. Gambardella, Ant algorithms for discrete optimization, Artificial Life, v.5 n.2, p.137-172, April 1999 [doi>10.1162/106454699568728]
• 12: Dorigo, M. and Gambardella, L. M. 1997a. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans. Evolut. Comput.1, 53--66.
• 13: Dorigo, M. and Gambardella, L. M. 1997b. Ant colonies for the traveling salesman problem. BioSystems 43, 73--81.
• 14: Dorigo, M., Maniezzo, V., and Colorni, A. 1996. The ant system: Optimization by a colony of cooperating agents. IEEE Trans. Syst. Man, and Cybern.---Part B, 26, 29--41.
• 15: Fred Glover , Manuel Laguna, Tabu search, Modern heuristic techniques for combinatorial problems, John Wiley & Sons, Inc., New York, NY, 1993
• 16: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 17: Gong, W. B., Ho, Y. C., and Zhai, W. 1992. Stochastic comparison algorithm for discrete optimization with estimation. In Proceedings of the 31st IEEE Conference on Decision and Control, IEEE Computer Society Press, Los Alamitos, Calif., pp. 795--800.
• 18: Walter J. Gutjahr, A Graph-based Ant system and its convergence, Future Generation Computer Systems, v.16 n.9, p.873-888, June 2000
• 19: Gutjahr, W. J. 2000b. A generalized convergence result for the graph-based ant system methaheuristic. Manuscript, University of Vienna.
• 20: Gutjahr, W. J. and Pflug, G. C. 1996. Simulated annealing for noisy cost functions. J. Global Optim. 8, 1--13.
• 21: Hastings, W. K. 1970. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57, 92--109.
• 22: Horst, R., Pardalos, P. M., and Thoai, N. V. 1996. Introduction to Global Optimization. Kluwer Academic Publishers.
• 23: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 24: Mark Jerrum , Alistair Sinclair, Polynomial-time approximation algorithms for the Ising model, SIAM Journal on Computing, v.22 n.5, p.1087-1116, Oct. 1993 [doi>10.1137/0222066]
• 25: Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, 671--680.
• 26: Lieber, D. 1999. Rare-events estimation via cross-entropy and importance sampling. Ph.D. Thesis, William Davidson Faculty of Industrial Engineeringand Management, Technion, Haifa, Israel.
• 27: Lieber, D. and Rubinstein, R. Y. 1997. Rare-events estimation via the cross-entropy method. Manuscript, Faculty of Industrial Engineering and Management, Technion, Haifa, Israel.
• 28: Lieber, D., Rubinstein, R.Y., and Elmakis, D. 1997. Quick estimation of rare-events in stochastic networks. IEEE Trans. Reliab. 46, 254--265.
• 29: Lovasz, L. 1995. Randomized algorithms in combinatorial optimization. DIMACS Ser. Discr. Math. Theoret. Comput. Sci. 25, 153--179.
• 30: Metropolis, M., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. W., and Teller, E. 1953. Equations of state calculations by fast computing machines. J. Chem. Phys. 21, 1087--1092.
• 31: Norkin, W. I., Pflug, G. C., and Ruszczynski, A. 1996. A branch-and-bound method for stochastic global optimization. Working paper, International Institute for Applied System Analysis, WP-96-065, Laxenburg, Austria.
• 32: Osman, I. W. and Laporte, G. 1996. Metaheuristics: A bibliography. Ann. Oper. Res. 63, 513--523.
• 33: R. Gray Parker , Ronald L. Rardin, Discrete optimization, Academic Press Professional, Inc., San Diego, CA, 1988
• 34: Pinter, J. D. 1996. Global Optimization in Action, Kluwer Academic Publishers.
• 35: Rayward-Smith, V. J., Osman, I. H., Reeves, C. R., and Smith, G. D. 1996. Modern Heuristic Search Methods. Wiley, Chichester.
• 36: Romeijn, H. E. and Smith, R. L. 1994. Simulated annealing for constrained global optimization. J. Glob. Optim. 5, 101--126.
• 37: Rubinstein, R. Y. 1999.The cross-entropy method for combinatorial and continuous optimization. Method. Comput. Appl. Prob. 1, 127--190.
• 38: Rubinstein, R. Y. and Melamed, B. 1998. Efficient Simulation and Modeling. Wiley, New York.
• 39: Rubinstein, R. Y. and Shapiro, A. 1993. Discrete Event Systems: Sensitivity Analysis and StochasticOptimization via the Score Function Method. Wiley, New York.
• 40: Ruud Schoonderwoerd , Janet L. Bruten , Owen E. Holland , Leon J. M. Rothkrantz, Ant-based load balancing in telecommunications networks, Adaptive Behavior, v.5 n.2, p.169-207, Fall 1996 [doi>10.1177/105971239700500203]
• 41: Leyuan Shi , Sigurdur Ólafsson, Nested Partitions Method for Global Optimization, Operations Research, v.48 n.3, p.390-407, May 2000 [doi>10.1287/opre.48.3.390.12436]
• 42: Leyuan Shi , Sigurdur Ólafsson , Ning Sun, New parallel randomized algorithms for the traveling salesman problem, Computers and Operations Research, v.26 n.4, p.371-394, April 1999 [doi>10.1016/S0305-0548(98)00068-9]
• 43: Thomas Stützle , Marco Dorigo, ACO algorithms for the quadratic assignment problem, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 44: Israel A. Wagner , Michael Lindenbaum , Alfred M. Bruckstein, Efficiently searching a graph by a smell-oriented vertex process, Annals of Mathematics and Artificial Intelligence, v.24 n.1-4, p.211-223, 1998 [doi>10.1023/A:1018957401093]
• 45: Wagner, I. A., Lindenbaum, M., and Bruckstein, A. M. 1999. Distributed covering by ant-robots using evaporating traces. IEEE Trans. Robot. Automat. 15, 918--933.
• 46: Wagner, I. A., Lindenbaum, M., and Bruckstein, A. M. 2000. ANTS: Agents on networks, trees and subgraphs. Preprint.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design

Keywords:
Combinatorial optimization, cross-entropy, importance sampling, rare event simulation