A CONTINUATION APPROACH USING NCP FUNCTION FOR SOLVING MAX-CUT PROBLEM

作者：Xu Fengmin^*; Xu Chengxian; Ren Jiuquan

来源：Asia Pacific Journal of Operational Research, 2009, 26(4): 445-456.

DOI：10.1142/S0217595909002298

• Max-cut problem
• feasible direction algorithm
• NCP function
• continuation approach
• convergence

A continuous approach using NCP function for approximating the solution of the max-cut problem is proposed. The max-cut problem is relaxed into an equivalent nonlinearly constrained continuous optimization problem and a feasible direction method without line searches is presented for generating an optimal solution of the relaxed continuous optimization problem. The convergence of the algorithm is proved. Numerical experiments and comparisons on some max-cut test problems show that we can get the satisfactory solution of max-cut problems with less computation time. Furthermore, this is the first time that the feasible direction method is combined with NCP function for solving max-cut problem, and similar idea can be generalized to other combinatorial optimization problems.

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