Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners
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 n...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2020-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2020/5974820 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832565997601554432 |
|---|---|
| author | Richard J. Forrester Noah Hunt-Isaak |
| author_facet | Richard J. Forrester Noah Hunt-Isaak |
| author_sort | Richard J. Forrester |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-6a3650432c544e3dba7f4091cbdfe04c |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2020-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-6a3650432c544e3dba7f4091cbdfe04c2025-02-03T01:05:28ZengWileyJournal of Applied Mathematics1110-757X1687-00422020-01-01202010.1155/2020/59748205974820Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for PractitionersRichard J. Forrester0Noah Hunt-Isaak1Dickinson College, Carlisle, Pennsylvania, USADickinson College, Carlisle, Pennsylvania, USAThis 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.http://dx.doi.org/10.1155/2020/5974820 |
| spellingShingle | Richard J. Forrester Noah Hunt-Isaak Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners Journal of Applied Mathematics |
| title | Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners |
| title_full | Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners |
| title_fullStr | Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners |
| title_full_unstemmed | Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners |
| title_short | Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners |
| title_sort | computational comparison of exact solution methods for 0 1 quadratic programs recommendations for practitioners |
| url | http://dx.doi.org/10.1155/2020/5974820 |
| work_keys_str_mv | AT richardjforrester computationalcomparisonofexactsolutionmethodsfor01quadraticprogramsrecommendationsforpractitioners AT noahhuntisaak computationalcomparisonofexactsolutionmethodsfor01quadraticprogramsrecommendationsforpractitioners |