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

Borzou Rostami (), Fausto Errico () and Andrea Lodi ()
Additional contact information
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

Operations Research, 2023, vol. 71, issue 2, 471-486

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.

Keywords: Optimization; binary quadratic program; convex reformulation; outer approximation; variable partitioning constraint (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2241 (application/pdf)

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:inm:oropre:v:71:y:2023:i:2:p:471-486

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().