2015, 5(2): 151-168. doi: 10.3934/naco.2015.5.151

Speeding up a memetic algorithm for the max-bisection problem

1. 

Center for Discrete Mathematics and Theoretical Computer Science, Fuzhou University, Fuzhou 350108, China, China

2. 

Department of Mathematics, Minjiang University, Fuzhou, 350108, China

Received  September 2014 Revised  May 2015 Published  June 2015

Max-bisection of a weighted graph $G = (V, E)$ is to partition the vertex set $V$ into two subsets that have equal cardinality, such that the sum of the weights of the edges connecting vertices in different subsets is maximized. It is an NP-complete problem. Various heuristics have been proposed for solving the max-bisection problem and some of them get very good quality solutions, but are time consuming. In this paper, we propose several techniques to speeding up Lin and Zhu's memetic algorithm for this problem. It consists of a crossover operator with a greedy strategy, a fast modified Kernighan-Lin local search, and a new population updating function. Experiments are performed on 71 well-known G-set benchmark instances. Results show that the memetic algorithm is much faster than Wu and Hao's memetic algorithm, which can get best solutions up to now, on middle-scale and large-scale instances. Specifically, some current best known solutions of the test instances are improved.
Citation: Wenxing Zhu, Yanpo Liu, Geng Lin. Speeding up a memetic algorithm for the max-bisection problem. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 151-168. doi: 10.3934/naco.2015.5.151
References:
[1]

C. Ashcraft and J. W. H. Liu, Using domain decomposition to find graph bisectors,, BIT Numerical Mathematics, 37 (1997), 506.  doi: 10.1007/BF02510238.  Google Scholar

[2]

P. Austrin, S. Benabbas and K. Georgiou, Better balance by being biased: a 0.8776-approximation for max bisection,, in Proceedings of SODA, (2013), 277.   Google Scholar

[3]

F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design,, Operations Research, 36 (1988), 493.   Google Scholar

[4]

R. Battiti and A. Bertossi, Differential greedy for the 0-1 equicut problem,, in Proceeding of the DIMACS Workshop on Network Design: Connectivity and Facilities Location (eds. D. Z. Du and P. M. Pardalos), (1997).   Google Scholar

[5]

L. Brunetta, M. Conforti and G. Rinaldi, A branch-and-cut algorithm for the equicut problem,, Mathematical Programming, 78 (1997), 243.  doi: 10.1016/S0025-5610(97)00017-8.  Google Scholar

[6]

K. C. Chang and D. H-C. Du, Efficient algorithms for layer assignment problems,, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6 (1987), 67.   Google Scholar

[7]

P. Chardaire, M. Barake and G. P. McKeown, A PROBE-based heuristic for graph partitioning,, IEEE Transactions on Computers, 56 (2007), 1707.  doi: 10.1109/TC.2007.70760.  Google Scholar

[8]

R. K. F. Chung, Spectral Graph Theory,, 92, (1997).   Google Scholar

[9]

C. Dang, L. He and I. K. Hui, A deterministic annealing algorithm for approximating a solution of the max-bisection problem,, Neural Networks, 15 (2002), 441.   Google Scholar

[10]

A. Duarte, F. Fernández, Á. Sánchez and A. Sanz, A hierarchical social metaheuristic for the max-cut problem,, Lecture Notes in computer Science, 3004 (2004), 84.   Google Scholar

[11]

U. Feige, M. Karpinski and M. Langberg, A note on approximating max-bisection on regular graphs,, \emph{Information Processing Letters}, 79 (2001), 181.  doi: 10.1016/S0020-0190(00)00189-7.  Google Scholar

[12]

C. M. Fiduccia and R. M. Mattheyses, A linear time heuristic for improving network partitions,, in Proceedings of the 19th Design Automation Conference, (1982), 175.   Google Scholar

[13]

A. Frieze and M. Jerrum, Improved approximation algorithm for max k-cut and max-bisection,, Algorithmica, 18 (1997), 67.  doi: 10.1007/BF02523688.  Google Scholar

[14]

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for Max-Cut and satisfiability problems using semidefinite programming,, Journal of the ACM, 42 (1995), 1115.  doi: 10.1145/227683.227684.  Google Scholar

[15]

E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems,, Random Structures and Algorithms, 20 (2002), 382.  doi: 10.1002/rsa.10035.  Google Scholar

[16]

J. Hastad, Some optimal inapproachability results,, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, (1997), 1.   Google Scholar

[17]

C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM Journal on Optimization, 10 (2000), 673.  doi: 10.1137/S1052623497328987.  Google Scholar

[18]

B. Hendrickson and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations,, SIAM Journal on Scientific Computing, 16 (1995), 452.  doi: 10.1137/0916028.  Google Scholar

[19]

J. H. Holland, Adaptation in Natural Artificial System,, The University of Michigan Press (Second edition; MIT press), (1992).   Google Scholar

[20]

K. Jansen, M. Karpinski, A. Lingas and E. Seidel, Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs,, SIAM Journal on Computing, 35 (2005), 110.  doi: 10.1137/S009753970139567X.  Google Scholar

[21]

R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R. E. Miller and J. W. Thatcher), (1972), 85.   Google Scholar

[22]

M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs,, Fundamenta Informaticae, 62 (2004), 369.   Google Scholar

[23]

B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs,, The Bell System Technical Journal, 49 (1970), 291.   Google Scholar

[24]

S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs,, SIAM Journal on Computing, 37 (2007), 319.  doi: 10.1137/S0097539705447372.  Google Scholar

[25]

D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming,, Vol. 2, (1997).   Google Scholar

[26]

K. Krishnan and J. Mitchell, A semidefinite programming based polyhedral cut and price approach for the Max-Cut problem,, Computational Optimization and Applications, 33 (2006), 51.  doi: 10.1007/s10589-005-5958-3.  Google Scholar

[27]

R. B. Lin and S. Y. Chen, Conjugate conflict continuation graphs for multilayer constrained via minimization,, Information Sciences, 177 (2007), 2436.  doi: 10.1016/j.ins.2007.01.013.  Google Scholar

[28]

G. Lin and W. Zhu, An efficient memetic algorithm for solving the Max-Bisection problem,, IEEE Transactions on Computers, 63 (2014), 1365.  doi: 10.1109/TC.2013.7.  Google Scholar

[29]

A. F. Ling, C. X. Xu and L. Tang, A modified VNS metaheuristic for max-bisection problems,, Journal of Computational and Applied Mathematics, 220 (2008), 413.  doi: 10.1016/j.cam.2007.08.018.  Google Scholar

[30]

R. Marti, A. Duarte and M. Laguna, Advanced scatter search for the max-cut problem,, INFORMS Journal on Computing, 21 (2009), 26.  doi: 10.1287/ijoc.1080.0275.  Google Scholar

[31]

P. Moscato and C. Cotta, A gentle introduction to memetic algorithms,, in Handbook of Metaheuristics (eds. F. Glover and G. A. Kochenberger), (2003).  doi: 10.1007/0-306-48056-5_5.  Google Scholar

[32]

K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming,, Mathematical Programming, 39 (1987), 117.  doi: 10.1007/BF02592948.  Google Scholar

[33]

F. Neri, C. Cotta and P. Moscato, Handbook of Memetic Algorithms,, Studies in Computational Intelligence, (2011).  doi: 10.1007/978-3-642-23247-3.  Google Scholar

[34]

G. Palubeckis and V. Krivickiene, Application of multistart tabu search to the Max Cut problem,, Information Technology and Control, 2 (2004), 29.   Google Scholar

[35]

P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, (2012), 373.   Google Scholar

[36]

V. P. Shylo and O. V. Shylo, Solving the max-cut problem by the global equilibrium search,, Cybernetics and Systems Analysis, 46 (2010), 744.   Google Scholar

[37]

K. Sörensen and M. Sevaux, MA|PM: memetic algorithms with population management,, Computers and Operations Research, 33 (2006), 1214.   Google Scholar

[38]

C. C. de Souza, R. Keunings, L. A. Wolsey and O. Zone, A new approach to minimizing the front width in finite element calculations,, Computer Methods in Applied Mechanics and Engineering, 111 (1994), 323.  doi: 10.1016/0045-7825(94)90137-6.  Google Scholar

[39]

D. Spielman, Spectral Graph Theory,, Lecture Notes, (2009).   Google Scholar

[40]

E. W. Weisstein, Laplacian Matrix,, MathWorld-A Wolfram Web Resource, (1995).   Google Scholar

[41]

Q. Wu and J. K. Hao, Memetic search for the max-bisection problem,, Computers and Operations Research, 40 (2013), 166.  doi: 10.1016/j.cor.2012.06.001.  Google Scholar

[42]

F. Xu, X. Ma and B. Chen, A new Lagrangian net algorithm for solving max-bisection problems,, Journal of Computational and Applied Mathematics, 235 (2011), 3718.  doi: 10.1016/j.cam.2011.01.015.  Google Scholar

[43]

Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101.  doi: 10.1007/PL00011415.  Google Scholar

show all references

References:
[1]

C. Ashcraft and J. W. H. Liu, Using domain decomposition to find graph bisectors,, BIT Numerical Mathematics, 37 (1997), 506.  doi: 10.1007/BF02510238.  Google Scholar

[2]

P. Austrin, S. Benabbas and K. Georgiou, Better balance by being biased: a 0.8776-approximation for max bisection,, in Proceedings of SODA, (2013), 277.   Google Scholar

[3]

F. Barahona, M. Grötschel, M. Jünger and G. Reinelt, An application of combinatorial optimization to statistical physics and circuit layout design,, Operations Research, 36 (1988), 493.   Google Scholar

[4]

R. Battiti and A. Bertossi, Differential greedy for the 0-1 equicut problem,, in Proceeding of the DIMACS Workshop on Network Design: Connectivity and Facilities Location (eds. D. Z. Du and P. M. Pardalos), (1997).   Google Scholar

[5]

L. Brunetta, M. Conforti and G. Rinaldi, A branch-and-cut algorithm for the equicut problem,, Mathematical Programming, 78 (1997), 243.  doi: 10.1016/S0025-5610(97)00017-8.  Google Scholar

[6]

K. C. Chang and D. H-C. Du, Efficient algorithms for layer assignment problems,, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6 (1987), 67.   Google Scholar

[7]

P. Chardaire, M. Barake and G. P. McKeown, A PROBE-based heuristic for graph partitioning,, IEEE Transactions on Computers, 56 (2007), 1707.  doi: 10.1109/TC.2007.70760.  Google Scholar

[8]

R. K. F. Chung, Spectral Graph Theory,, 92, (1997).   Google Scholar

[9]

C. Dang, L. He and I. K. Hui, A deterministic annealing algorithm for approximating a solution of the max-bisection problem,, Neural Networks, 15 (2002), 441.   Google Scholar

[10]

A. Duarte, F. Fernández, Á. Sánchez and A. Sanz, A hierarchical social metaheuristic for the max-cut problem,, Lecture Notes in computer Science, 3004 (2004), 84.   Google Scholar

[11]

U. Feige, M. Karpinski and M. Langberg, A note on approximating max-bisection on regular graphs,, \emph{Information Processing Letters}, 79 (2001), 181.  doi: 10.1016/S0020-0190(00)00189-7.  Google Scholar

[12]

C. M. Fiduccia and R. M. Mattheyses, A linear time heuristic for improving network partitions,, in Proceedings of the 19th Design Automation Conference, (1982), 175.   Google Scholar

[13]

A. Frieze and M. Jerrum, Improved approximation algorithm for max k-cut and max-bisection,, Algorithmica, 18 (1997), 67.  doi: 10.1007/BF02523688.  Google Scholar

[14]

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for Max-Cut and satisfiability problems using semidefinite programming,, Journal of the ACM, 42 (1995), 1115.  doi: 10.1145/227683.227684.  Google Scholar

[15]

E. Halperin and U. Zwick, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems,, Random Structures and Algorithms, 20 (2002), 382.  doi: 10.1002/rsa.10035.  Google Scholar

[16]

J. Hastad, Some optimal inapproachability results,, in Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, (1997), 1.   Google Scholar

[17]

C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM Journal on Optimization, 10 (2000), 673.  doi: 10.1137/S1052623497328987.  Google Scholar

[18]

B. Hendrickson and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations,, SIAM Journal on Scientific Computing, 16 (1995), 452.  doi: 10.1137/0916028.  Google Scholar

[19]

J. H. Holland, Adaptation in Natural Artificial System,, The University of Michigan Press (Second edition; MIT press), (1992).   Google Scholar

[20]

K. Jansen, M. Karpinski, A. Lingas and E. Seidel, Polynomial time approximation schemes for Max-Bisection on planar and geometric graphs,, SIAM Journal on Computing, 35 (2005), 110.  doi: 10.1137/S009753970139567X.  Google Scholar

[21]

R. M. Karp, Reducibility among combinatorial problems,, in Complexity of Computer Computations (eds. R. E. Miller and J. W. Thatcher), (1972), 85.   Google Scholar

[22]

M. Karpinski, M. Kowaluk and A. Lingas, Approximation algorithms for MAX-BISECTION on low degree regular graphs,, Fundamenta Informaticae, 62 (2004), 369.   Google Scholar

[23]

B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs,, The Bell System Technical Journal, 49 (1970), 291.   Google Scholar

[24]

S. Khot, G. Kindler, E. Mossel and R. O'Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs,, SIAM Journal on Computing, 37 (2007), 319.  doi: 10.1137/S0097539705447372.  Google Scholar

[25]

D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming,, Vol. 2, (1997).   Google Scholar

[26]

K. Krishnan and J. Mitchell, A semidefinite programming based polyhedral cut and price approach for the Max-Cut problem,, Computational Optimization and Applications, 33 (2006), 51.  doi: 10.1007/s10589-005-5958-3.  Google Scholar

[27]

R. B. Lin and S. Y. Chen, Conjugate conflict continuation graphs for multilayer constrained via minimization,, Information Sciences, 177 (2007), 2436.  doi: 10.1016/j.ins.2007.01.013.  Google Scholar

[28]

G. Lin and W. Zhu, An efficient memetic algorithm for solving the Max-Bisection problem,, IEEE Transactions on Computers, 63 (2014), 1365.  doi: 10.1109/TC.2013.7.  Google Scholar

[29]

A. F. Ling, C. X. Xu and L. Tang, A modified VNS metaheuristic for max-bisection problems,, Journal of Computational and Applied Mathematics, 220 (2008), 413.  doi: 10.1016/j.cam.2007.08.018.  Google Scholar

[30]

R. Marti, A. Duarte and M. Laguna, Advanced scatter search for the max-cut problem,, INFORMS Journal on Computing, 21 (2009), 26.  doi: 10.1287/ijoc.1080.0275.  Google Scholar

[31]

P. Moscato and C. Cotta, A gentle introduction to memetic algorithms,, in Handbook of Metaheuristics (eds. F. Glover and G. A. Kochenberger), (2003).  doi: 10.1007/0-306-48056-5_5.  Google Scholar

[32]

K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming,, Mathematical Programming, 39 (1987), 117.  doi: 10.1007/BF02592948.  Google Scholar

[33]

F. Neri, C. Cotta and P. Moscato, Handbook of Memetic Algorithms,, Studies in Computational Intelligence, (2011).  doi: 10.1007/978-3-642-23247-3.  Google Scholar

[34]

G. Palubeckis and V. Krivickiene, Application of multistart tabu search to the Max Cut problem,, Information Technology and Control, 2 (2004), 29.   Google Scholar

[35]

P. Raghavendra and N. Tan, Approximating CSPs with global cardinality constraints using SDP hierarchies,, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, (2012), 373.   Google Scholar

[36]

V. P. Shylo and O. V. Shylo, Solving the max-cut problem by the global equilibrium search,, Cybernetics and Systems Analysis, 46 (2010), 744.   Google Scholar

[37]

K. Sörensen and M. Sevaux, MA|PM: memetic algorithms with population management,, Computers and Operations Research, 33 (2006), 1214.   Google Scholar

[38]

C. C. de Souza, R. Keunings, L. A. Wolsey and O. Zone, A new approach to minimizing the front width in finite element calculations,, Computer Methods in Applied Mechanics and Engineering, 111 (1994), 323.  doi: 10.1016/0045-7825(94)90137-6.  Google Scholar

[39]

D. Spielman, Spectral Graph Theory,, Lecture Notes, (2009).   Google Scholar

[40]

E. W. Weisstein, Laplacian Matrix,, MathWorld-A Wolfram Web Resource, (1995).   Google Scholar

[41]

Q. Wu and J. K. Hao, Memetic search for the max-bisection problem,, Computers and Operations Research, 40 (2013), 166.  doi: 10.1016/j.cor.2012.06.001.  Google Scholar

[42]

F. Xu, X. Ma and B. Chen, A new Lagrangian net algorithm for solving max-bisection problems,, Journal of Computational and Applied Mathematics, 235 (2011), 3718.  doi: 10.1016/j.cam.2011.01.015.  Google Scholar

[43]

Y. Y. Ye, A 0.699-approximation algorithm for Max-Bisection,, Mathematical Programming, 90 (2001), 101.  doi: 10.1007/PL00011415.  Google Scholar

[1]

Qiao Liu. Local rigidity of certain solvable group actions on tori. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 553-567. doi: 10.3934/dcds.2020269

[2]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[3]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[4]

Editorial Office. Retraction: Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin and Zhike Han, Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 957-957. doi: 10.3934/dcdss.2019064

[5]

Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020448

[6]

Roland Schnaubelt, Martin Spitz. Local wellposedness of quasilinear Maxwell equations with absorbing boundary conditions. Evolution Equations & Control Theory, 2021, 10 (1) : 155-198. doi: 10.3934/eect.2020061

[7]

Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048

[8]

Claudio Bonanno, Marco Lenci. Pomeau-Manneville maps are global-local mixing. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1051-1069. doi: 10.3934/dcds.2020309

[9]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[10]

Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382

[11]

Tong Tang, Jianzhu Sun. Local well-posedness for the density-dependent incompressible magneto-micropolar system with vacuum. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020377

[12]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[13]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

[14]

Editorial Office. Retraction: Honggang Yu, An efficient face recognition algorithm using the improved convolutional neural network. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 901-901. doi: 10.3934/dcdss.2019060

[15]

Editorial Office. Retraction: Xiaohong Zhu, Zili Yang and Tabharit Zoubir, Research on the matching algorithm for heterologous image after deformation in the same scene. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1281-1281. doi: 10.3934/dcdss.2019088

[16]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007

[17]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[18]

Editorial Office. Retraction: Xiaohong Zhu, Lihe Zhou, Zili Yang and Joyati Debnath, A new text information extraction algorithm of video image under multimedia environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1265-1265. doi: 10.3934/dcdss.2019087

[19]

Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2021, 17 (2) : 779-803. doi: 10.3934/jimo.2019134

 Impact Factor: 

Metrics

  • PDF downloads (59)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]