Student author: Noah Hunt-Isaak

Document Type


Publication Date






Publication Title

Journal of Applied Mathematics


This paper is concerned with binary quadratic programs (BQPs), which are among the most well-studied classes of nonlinear integer optimization problems because of their wide variety of applications. While a number of different solution approaches have been proposed for tackling BQPs, practitioners need techniques that are both efficient and easy to implement. We revisit two of the most widely used linearization strategies for BQPs and examine the effectiveness of enhancements to these formulations that have been suggested in the literature. We perform a detailed large-scale computational study over five different classes of BQPs to compare these two linearizations with a more recent linear reformulation and direct submission of the nonlinear integer program to an optimization solver. The goal is to provide practitioners with guidance on how to best approach solving BQPs in an effective and easily implemented manner.


This published version is made available on Dickinson Scholar with the permission of the publisher. For more information on the published version, visit Hindawi's Website.

Copyright © 2020 Richard J. Forrester and Noah Hunt-Isaak. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Open access publication of this article was made possible with grant support from Waidner-Spahr Library distributed through the Dickinson College Research & Development Committee.



Included in

Mathematics Commons