A discrete filled function algorithm for approximate global solutions of max-cut problems (Q939569)

There have been very few attempts in using the filled function methods to solve max-cut or other combinatorial optimization problem. The max-cut problem can be expressed as a discrete quadratic optimization problem. This paper proposes a discrete filled function algorithm to find approximate global solutions for NP-hard max-cut problems. The proposed algorithm is implemented by a two-phase cycle. In the first phase, a local minimizer is obtained by using the 1-neighborhood local search in the objective function of the discrete quadratic optimization problem. In the second phase, the discrete filled function from some neighbor points of the local optimizer is minimized. The two cycles are iterated until the stopping conditions are met. Some numerical experimental results are presented.