Path relinking for unconstrained binary quadratic programming

Yang Wang, Zhipeng Lü, Fred Glover and Jin-Kao Hao

European Journal of Operational Research, 2012, vol. 223, issue 3, 595-604

Abstract: This paper presents two path relinking algorithms to solve the unconstrained binary quadratic programming (UBQP) problem. One is based on a greedy strategy to generate the relinking path from the initial solution to the guiding solution and the other operates in a random way. We show extensive computational results on five sets of benchmarks, including 31 large random UBQP instances and 103 structured instances derived from the MaxCut problem. Comparisons with several state-of-the-art algorithms demonstrate the efficacy of our proposed algorithms in terms of both solution quality and computational efficiency. It is noteworthy that both algorithms are able to improve the previous best known results for almost 40 percent of the 103 MaxCut instances.

Keywords: UBQP; Path relinking; Tabu search; MaxCut (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221712005334
Full text for ScienceDirect subscribers only

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:eee:ejores:v:223:y:2012:i:3:p:595-604

DOI: 10.1016/j.ejor.2012.07.012

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().