IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v71y2023i2p471-486.html
   My bibliography  Save this article

A Convex Reformulation and an Outer Approximation for a Large Class of Binary Quadratic Programs

Author

Listed:
  • Borzou Rostami

    (Lazaridis School of Business and Economics, Wilfrid Laurier University, Waterloo, Ontario N2L 3C7, Canada; Canada Excellence Research Chair (CERC) in Data Science for Real-Time Decision Making, Polytechnique Montreal, Montreal, Quebec H3C 3A7, Canada; Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Montreal, Quebec H3T 1J4, Canada)

  • Fausto Errico

    (Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, Montreal, Quebec H3T 1J4, Canada; Department of Civil Engineering, Ecole de Technologie Superieure de Montreal, Montreal, Quebec H3C 1K3, Canada; Group for Research in Decision Analysis, Montreal, Quebec H3T1J4, Canada)

  • Andrea Lodi

    (Canada Excellence Research Chair (CERC) in Data Science for Real-Time Decision Making, Polytechnique Montreal, Montreal, Quebec H3C 3A7, Canada; Jacobs Technion-Cornell Institute, Cornell Tech and Technion, Cornell University, New York, New York 10044)

Abstract

In this paper, we propose a general modeling and solving framework for a large class of binary quadratic programs subject to variable partitioning constraints. Problems in this class have a wide range of applications as many binary quadratic programs with linear constraints can be represented in this form. By exploiting the structure of the partitioning constraints, we propose mixed-integer nonlinear programming (MINLP) and mixed-integer linear programming (MILP) reformulations and show the relationship between the two models in terms of the relaxation strength. Our solution methodology relies on a convex reformulation of the proposed MINLP and a branch-and-cut algorithm based on outer approximation cuts, in which the cuts are generated on the fly by efficiently solving separation subproblems. To evaluate the robustness and efficiency of our solution method, we perform extensive computational experiments on various quadratic combinatorial optimization problems. The results show that our approach outperforms the state-of-the-art solver applied to different MILP reformulations of the corresponding problems.

Suggested Citation

  • Borzou Rostami & Fausto Errico & Andrea Lodi, 2023. "A Convex Reformulation and an Outer Approximation for a Large Class of Binary Quadratic Programs," Operations Research, INFORMS, vol. 71(2), pages 471-486, March.
    • Handle: RePEc:inm:oropre:v:71:y:2023:i:2:p:471-486
    DOI: 10.1287/opre.2021.2241
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2021.2241
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2021.2241?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:oropre:v:71:y:2023:i:2:p:471-486. 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.