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

Mark Lewis, Gary Kochenberger
International Journal of Operational Research,Vol. 26, Issue 1, Pages: 13-33.

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 …
[Full Text]