Computational Comparison of Exact Solution Methods for 0-1 Quadratic Programs: Recommendations for Practitioners
| Autor: | Richard J. Forrester, Noah Hunt-Isaak |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
021103 operations research Optimization problem Article Subject Computer science Applied Mathematics 0211 other engineering and technologies Binary number 0102 computer and information sciences 02 engineering and technology Solver 01 natural sciences Nonlinear system Quadratic equation 010201 computation theory & mathematics Linearization QA1-939 Variety (universal algebra) Mathematics Integer (computer science) |
| Zdroj: | J. Appl. Math. Journal of Applied Mathematics, Vol 2020 (2020) |
| ISSN: | 1687-0042 1110-757X |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
| Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |