A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems |
| |
Authors: | Ai-Fan Ling Cheng-Xian Xu Feng-Min Xu |
| |
Institution: | Department of Scientific Computing and Applied Software, Xi’an Jiaotong University, Xi’an 710049, PR China |
| |
Abstract: | In this paper, a discrete filled function algorithm embedded with continuous approximation is proposed to solve max-cut problems. A new discrete filled function is defined for max-cut problems, and properties of the function are studied. In the process of finding an approximation to the global solution of a max-cut problem, a continuation optimization algorithm is employed to find local solutions of a continuous relaxation of the max-cut problem, and then global searches are performed by minimizing the proposed filled function. Unlike general filled function methods, characteristics of max-cut problems are used. The parameters in the proposed filled function need not to be adjusted and are exactly the same for all max-cut problems that greatly increases the efficiency of the filled function method. Numerical results and comparisons on some well known max-cut test problems show that the proposed algorithm is efficient to get approximate global solutions of max-cut problems. |
| |
Keywords: | Combinatorial optimization Global optimization Filled function Max-cut Continuation method Local search |
本文献已被 ScienceDirect 等数据库收录! |