IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v36y2024i6p1501-1521.html
   My bibliography  Save this article

A Dual Bounding Framework Through Cost Splitting for Binary Quadratic Optimization

Author

Listed:
  • Mahdis Bayani

    (Polytechnique Montréal, Montreal, Quebec H3T 1J4, Canada; CIRRELT, Université de Montréal, Montreal, Quebec H3T 1J4, Canada; GERAD, Montreal, Quebec H3T 2A7, Canada)

  • Borzou Rostami

    (Alberta School of Business, University of Alberta, Edmonton, Alberta T6G 2R3, Canada)

  • Yossiri Adulyasak

    (GERAD, Montreal, Quebec H3T 2A7, Canada; HEC Montréal, Montreal, Quebec H3T 2A7, Canada)

  • Louis-Martin Rousseau

    (Polytechnique Montréal, Montreal, Quebec H3T 1J4, Canada; CIRRELT, Université de Montréal, Montreal, Quebec H3T 1J4, Canada)

Abstract

Binary quadratic programming (BQP) is a class of combinatorial optimization problems comprising binary variables, quadratic objective functions, and linear/nonlinear constraints. This paper examines a unified framework to reformulate a BQP problem with linear constraints to a new BQP with an exponential number of variables defined on a graph. This framework relies on the concept of stars in the graph to split the quadratic costs into adjacent and nonadjacent components indicating in-star and out-of-star interactions. We exploit the star-based structure of the new reformulation to develop a decomposition-based column generation algorithm. In our computational experiments, we evaluate the performance of our methodology on different applications with different quadratic structures. The quadratic component of the problem is dealt with in the column generation master problem and its subproblem. Results indicate the superiority of the framework over one of the state-of-the-art solvers, GUROBI, when applied to various benchmark reformulations with adjacent-only or sparse quadratic cost matrices. The framework outperforms GUROBI in terms of both dual bound and computational time in almost all instances.

Suggested Citation

  • Mahdis Bayani & Borzou Rostami & Yossiri Adulyasak & Louis-Martin Rousseau, 2024. "A Dual Bounding Framework Through Cost Splitting for Binary Quadratic Optimization," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1501-1521, December.
  • Handle: RePEc:inm:orijoc:v:36:y:2024:i:6:p:1501-1521
    DOI: 10.1287/ijoc.2021.0186
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2021.0186
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2021.0186?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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:inm:orijoc:v:36:y:2024:i:6:p:1501-1521. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.