A Dual Bounding Framework Through Cost Splitting for Binary Quadratic Optimization

Mahdis Bayani (), Borzou Rostami (), Yossiri Adulyasak () and Louis-Martin Rousseau ()
Additional contact information
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

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1501-1521

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.

Keywords: binary quadratic programming; combinatorial optimization; column generation; semi-assignment problem; multiple object tracking problem (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.0186 (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:orijoc:v:36:y:2024:i:6:p:1501-1521

Access Statistics for this article

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