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

Fengmin Xu (), Chengxian Xu () and Jiuquan Ren ()
Additional contact information
Fengmin Xu: School of Electronic and Information Engineering, Xi'an Jiaotong University, Xi'an, 710049, P. R. China
Chengxian Xu: Department of Mathematics, Faculty of Science, Xi'an Jiaotong University, Xi'an, 710049, P. R. China
Jiuquan Ren: Department of Mathematics, Faculty of Science, Xi'an Jiaotong University, Xi'an, 710049, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2009, vol. 26, issue 04, 445-456

Abstract: 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.

Keywords: Max-cut problem; feasible direction algorithm; NCP function; continuation approach; convergence (search for similar items in EconPapers)
Date: 2009
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595909002298
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:26:y:2009:i:04:n:s0217595909002298

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595909002298

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().