Revisiting some classical linearizations of the quadratic binary optimization problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916205581828096 |
|---|---|
| author | Punnen, Abraham P. Kaur, Navpreet |
| author_facet | Punnen, Abraham P. Kaur, Navpreet |
| contents | In this paper, we present several new linearizations of a quadratic binary optimization problem (QBOP), primarily using the method of aggregations. Although aggregations were studied in the past in the context of solving system of Diophantine equations in non-negative variables, none of the approaches developed produced practical models, particularly due to the large size of associate multipliers. Exploiting the special structure of QBOP we show that selective aggregation of constraints provide valid linearizations with interesting properties. For our aggregations, multipliers can be any non-zero real numbers. Moreover, choosing the multipliers appropriately, we demonstrate that the resulting LP relaxations have value identical to the corresponding non-aggregated models. We also provide a review of existing explicit linearizations of QBOP and presents the first systematic study of such models. Theoretical and experimental comparisons of new and existing models are also provided. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09437 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Revisiting some classical linearizations of the quadratic binary optimization problem Punnen, Abraham P. Kaur, Navpreet Discrete Mathematics Optimization and Control In this paper, we present several new linearizations of a quadratic binary optimization problem (QBOP), primarily using the method of aggregations. Although aggregations were studied in the past in the context of solving system of Diophantine equations in non-negative variables, none of the approaches developed produced practical models, particularly due to the large size of associate multipliers. Exploiting the special structure of QBOP we show that selective aggregation of constraints provide valid linearizations with interesting properties. For our aggregations, multipliers can be any non-zero real numbers. Moreover, choosing the multipliers appropriately, we demonstrate that the resulting LP relaxations have value identical to the corresponding non-aggregated models. We also provide a review of existing explicit linearizations of QBOP and presents the first systematic study of such models. Theoretical and experimental comparisons of new and existing models are also provided. |
| title | Revisiting some classical linearizations of the quadratic binary optimization problem |
| topic | Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2404.09437 |