Probabilistic multistart with path relinking for solving the unconstrained binary quadratic problem

Mark Lewis and Gary Kochenberger

International Journal of Operational Research, 2016, vol. 26, issue 1, 13-33

Abstract: The unconstrained binary quadratic problem (UBQP) has been shown to be an excellent framework from which to solve many types of problems, both constrained and unconstrained. In this paper we investigate a solution technique for UBQP that is based on perturbing a solution by drawing from the distribution of variables' estimated effect as determined via an unbiased design of experiments (DOE) sampling of the solution space. Solution perturbation is followed by a steepest ascent local search with path relinking. A simple implementation on benchmark problems compares well in time and solution quality with published results on benchmark problems of size up to 7,000 variables. A new set of larger problems having up to 15,000 variables and with non-uniform magnitude distributions of the elements in Q are also investigated and provide evidence that magnitude distributions of Q values affect problem difficulty. These large difficult problem instances required a more sophisticated path relinking approach as well as dynamic adjustments to perturbation sampling.

Keywords: multi-start heuristics; path relinking; unconstrained binary quadratic problem; UBQP; preprocessing; local search; design of experiments; DOE; benchmark problems; solution perturbation; probabilistic multistart; perturbation sampling. (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=75647 (text/html)
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:ids:ijores:v:26:y:2016:i:1:p:13-33

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().