IDEAS home Printed from https://ideas.repec.org/a/ids/ijores/v26y2016i1p13-33.html
   My bibliography  Save this article

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

Author

Listed:
  • Mark Lewis
  • Gary Kochenberger

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.

Suggested Citation

  • Mark Lewis & Gary Kochenberger, 2016. "Probabilistic multistart with path relinking for solving the unconstrained binary quadratic problem," International Journal of Operational Research, Inderscience Enterprises Ltd, vol. 26(1), pages 13-33.
    • Handle: RePEc:ids:ijores:v:26:y:2016:i:1:p:13-33
    as

    Download full text from publisher

    File URL: http://www.inderscience.com/link.php?id=75647
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Mark W. Lewis & Amit Verma & Todd T. Eckdahl, 2021. "Qfold: a new modeling paradigm for the RNA folding problem," Journal of Heuristics, Springer, vol. 27(4), pages 695-717, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ids:ijores:v:26:y:2016:i:1:p:13-33. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sarah Parker (email available below). General contact details of provider: http://www.inderscience.com/browse/index.php?journalID=170 .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.