A new discrete filled function method for solving large scale max-cut problems (Q438797)

The max-cut problem on an undirected graph \(G(V,E)\) with vertex set \(V\), edge set \(E\), and \(W\) as a symmetric weighted adjacency matrix of this graph with \(w_{ij}\neq 0\) for \((i,j)\in E\) and \(w_{ij}=0\) otherwise, is to find a bipartition \((S_1,S_2)\) of \(V\) such that the sum of the weights of the edges connecting the two parts is maximized, that is, \(\max \sum w_{ij}\) for \(i\in S_1\), \(j\in S_2\). There are two main reasons that motivated the authors to propose a new discrete filled function method as a class of global optimization methods to solve the max-cut problem. The first one is that there exist several continuous methods to solve this problem but the solution obtained cannot be guaranteed as a global solution. The methods are described in the introduction of the paper together with corresponding references. The second fact consists in that various filled functions, originally introduced by \textit{R. Ge} [Math. Program., Ser. A 46, No. 2, 191--204 (1990; Zbl 0694.90083)], have been successfully used for solving different optimization problems but very few attempts for the max-cut problem. After some definitions and preliminaries, the authors first define a new discrete filled function based on the structure of the max-cut problem and analyze its properties. Then, the complete algorithm that can greatly reduce the computational time and be applied to large scale max-cut problems is stated. Finally, numerical experiments and comparisons with some heuristic methods on some randomly generated problems and some well-known large scale max-cut problems showing the efficiency of the proposed algorithm are reported.