A discrete filled function algorithm embedded with continuous approximation for solving max-cut problems

作者：Ling, Ai-Fan^*; Xu, Cheng-Xian; Xu, Feng-Min

来源：European Journal of Operational Research, 2009, 197(2): 519-531.

DOI：10.1016/j.ejor.2008.07.026

• Combinatorial optimization
• Global optimization
• Filled function
• Max-cut
• Continuation method
• Local search

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

• 出版日期2009-9-1
• 单位西安交通大学