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.

Forrester, Richard J., and Noah Hunt-Isaak. Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners. Journal of Applied Mathematics (2020): Article ID 5974820, 21 pp. https://doi.org/10.1155/2020/5974820

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.

Richard Forrester is a professor of Mathematics and Data Analytics at Dickinson College.

Noah Hunt-Isaak, Dickinson College Class of 2020.

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. https://www.hindawi.com/journals/jam/2020/5974820/