Maximum Independent Sets and Supervised Learning

doi:10.1007/s40305-022-00395-8

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (4): 957-972.doi: 10.1007/s40305-022-00395-8

Maximum Independent Sets and Supervised Learning

Roberto Montemanni¹, Derek H. Smith², Xiao-Chen Chou¹

1. Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, Via Amendola 2, 42122, Reggio Emilia, Italy;
2. School of Computing and Mathematics, University of South Wales, Pontypridd, CF37 1DL, Wales, UK

Received:2020-07-02 Revised:2021-11-22 Online:2023-12-30 Published:2023-12-26
Contact: Roberto Montemanni, Derek H. Smith, Xiao-Chen Chou E-mail:roberto.montemanni@unimore.it;derek.smith@southwales.ac.uk;xiaochen.chou@unimore.it
Supported by:
Xiao-Chen Chou was supported by the Schweizerischer Nationalfonds zur F?rderung der Wissenschaftlichen Forschung (CH) (No. 200020-182360)

Abstract

Abstract: The paper discusses an enhancement to a recently presented supervised learning algorithm to solve the Maximum Independent Set problem. In particular, it is shown that the algorithm can be improved by simplifying the task learnt by the neural network adopted, with measurable effects on the quality of the solutions provided on unseen instances. Empirical results are presented to validate the idea..

Key words: Maximum Clique problem, Maximum Independent Set problem, Machine learning, Graph theory

CLC Number:

Roberto Montemanni, Derek H. Smith, Xiao-Chen Chou. Maximum Independent Sets and Supervised Learning[J]. Journal of the Operations Research Society of China, 2023, 11(4): 957-972.

TrendMD

References

[1] Wu, Q., Hao, J.-K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693-709 (2015)
[2] Leese, R., Hurley, S.: Methods and Algorithms for Radio Channel Assignment. Oxford University Press, Oxford (2002)
[3] Montemanni, R., Smith, D.H., Allen, S.M.: Lower bounds for fixed spectrum frequency assignment. Ann. Oper. Res. 107, 237-250 (2001)
[4] Smith, D.H., Montemanni, R.: A new table of permutation codes. Des. Codes Crypt. 63(2), 241-253 (2012)
[5] Smith, D.H., Montemanni, R.: Permutation codes with specified packing radius. Des. Codes Crypt. 69(1), 95-106 (2013)
[6] Li, Z., Chen, Q., Koltun, V.: Combinatorial optimization with graph convolutional networks and guided tree search. In: Proceedings of the 32nd Conference on Neural Information Processing Systems, pp. 537-546 (2018)
[7] Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6), 375-382 (1990)
[8] Montemanni, R., Barta, J., Smith, D.H.: Graph colouring and branch and bound approaches for permutation code algorithms. In: Rocha, A., et al. (eds.) New Advances in Information Systems and Technologies. Advances in Intelligent Systems and Computing, vol. 444, pp. 223-232. Springer, Cham (2016)
[9] Östergård, P.R.J.: A fast algorithm for the maximum clique problem. Discrete Appl. Math. 120, 197-207 (2002)
[10] Jin, Y., Hao, J.-K.: General swap-based multiple neighborhood tabu search for the maximum independent set problem. Eng. Appl. Artif. Intel. 37, 20-33 (2015)
[11] Smith, D.H., Perkins, S., Montemanni, R.: Solving the maximum clique problem with a hybrid algorithm. Int. J. Metaheuristics 7(2), 152-175 (2019)
[12] Smith, D.H., Montemanni, R., Perkins, S.: The use of an exact algorithm within a tabu search Maximum Clique algorithm. Algorithms 13(10), 253 (2020)
[13] He, H., Daumé H. III, Eisner, J.: Learning to search in branch and bound algorithms. In: Proceedings of the 27th Conference on Advances in Neural Information Processing Systems, pp. 3293-3301 (2014)
[14] Vinyals, O., Fortunato, M., Jaitly, N.: Pointer networks. In: Proceedings of 28th Conference on Neural Information Processing Systems, pp. 2692-2700 (2015)
[15] Mele, U.J., Chou, X., Gambardella, L.M., Montemanni, R: Reinforcement learning and additional rewards for the traveling salesman problem. In: Proceedings of the 7th IEEE International Conference on Industrial Engineering and Applications, pp. 170-176 (2020)
[16] Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural combinatorial optimization with reinforcement learning (2016). arXiv:1611.09940
[17] Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: Proceedings of the 30th Conference on Neural Information Processing Systems, pp. 3844-3852 (2016)
[18] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations (2017)
[19] Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., van den Driessche, G., et al.: Mastering the game of Go with deep neural networks and tree search. Nature 529, 484-489 (2016)
[20] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., et al.: Mastering the game of Go without human knowledge. Nature 550, 354-359 (2017)
[21] Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., et al.: Mastering Atari, Go, chess and shogi by planning with a learned model. Nature 588, 604-609 (2020)
[22] Nair, V., Hinton, G.E.: Rectified linear units improve restricted Boltzmann machines. In: Proceedings of the 27th International Conference on International Conference on Machine Learning. Omnipress (2010)
[23] Guzmán-Rivera, A., Batra, D., Kohli, P.: Multiple choice learning: learning to produce multiple structured outputs. In: Proceedings of the 25th Conference on Neural Information Processing Systems, pp. 1799-1807 (2012)
[24] Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525-547 (2012)
[25] Battiti, R., Protasi, M.: Reactive local search for the maximum clique problem. Algorithmica 29(4), 610-637 (2001)
[26] Feo, T.A., Resende, M.G.C., Smith, S.H.: A greedy randomized adaptive search procedure for maximum independent set. Oper. Res. 42(5), 860-878 (1994)
[27] Akiba, T., Iwata, Y.: Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover. Theor. Comput. Sci. 609(I), 211-225 (2016)
[28] McKay, B.D.: Practical graph isomorphism. Congr. Numer. 30, 45-87 (1980)
[29] McKay, B.D., Piperno, A.: Practical graph isomorphism, II. J. Symb. Comput. 60, 94-112 (2014)
[30] Junttila, T., Kaski, P.: Conflict propagation and component recursion for canonical labeling. In: Marchetti-Spaccamela A., Segal M. (eds.) Theory and Practice of Algorithms in (Computer) Systems, pp. 151-162 (2011)
[31] Montemanni, R., Barta, J., Smith, D.H.: Permutation codes: a branch and bound approach. In: Proceedings of the International Conference on Pure Mathematics, Applied Mathematics, Computational Methods, pp. 86-90 (2014)
[32] Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: Random constraint satisfaction: easy generation of hard (satisfiable) instances. Artif. Intel. 171, 514-534 (2007)
[33] Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: A simple model to generate hard satisfiable instances. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence, pp. 337-342 (2005)
[34] Kingma, D.P., Ba, J.: Adam: a method for stochastic optimization. In: Proceedings of 3rd International Conference on Learning Representations, San Diego. http://arxiv.org/abs/1412.6980 (2015)

Maximum Independent Sets and Supervised Learning

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments

[1]	Tian-De Guo, Yan Liu, Cong-Ying Han. An Overview of Stochastic Quasi-Newton Methods for Large-Scale Machine Learning [J]. Journal of the Operations Research Society of China, 2023, 11(2): 245-275.
[2]	Long The Nguyen, Huong Thu Nguyen, Alexander Diomidovich Afanasiev, Tao Van Nguyen. Automatic Identification Fingerprint Based on Machine Learning Method [J]. Journal of the Operations Research Society of China, 2022, 10(4): 849-860.
[3]	Cai-Hua Chen, Yu-Hang Du, Dong-Dong Ge, Lin Lei, Yin-Yu Ye. Optimization and Operations Research in Mitigation of a Pandemic [J]. Journal of the Operations Research Society of China, 2022, 10(2): 289-304.
[4]	Zhou-Chen Lin. How Can Machine Learning and Optimization Help Each Other Better? [J]. Journal of the Operations Research Society of China, 2020, 8(2): 341-351.