Objective Coefficient Rounding and Almost Symmetries in Binary Programs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918243542761472 |
|---|---|
| author | Kuzinowicz, Dominik Lichocki, Paweł Mexi, Gioni Pfetsch, Marc E. Pokutta, Sebastian Zimmer, Max |
| author_facet | Kuzinowicz, Dominik Lichocki, Paweł Mexi, Gioni Pfetsch, Marc E. Pokutta, Sebastian Zimmer, Max |
| contents | This article investigates the interplay of rounding objective coefficients in binary programs and almost symmetries. Empirically, reducing the number of significant bits through rounding often leads to instances that are easier to solve. One reason can be that the amount of symmetries increases, which enables solvers to be more effective when they are exploited. This can signify that the original instance contains 'almost symmetries'. Furthermore, solving the rounded problems provides approximations to the original objective values. We empirically investigate these relations on instances of the capacitated facility location problem, the knapsack problem and a diverse collection of additional instances, using the solvers SCIP and CP-SAT. For all investigated problem classes, we show empirically that this yields faster algorithms with guaranteed solution quality. The influence of symmetry depends on the instance type and solver. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_10507 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Objective Coefficient Rounding and Almost Symmetries in Binary Programs Kuzinowicz, Dominik Lichocki, Paweł Mexi, Gioni Pfetsch, Marc E. Pokutta, Sebastian Zimmer, Max Optimization and Control This article investigates the interplay of rounding objective coefficients in binary programs and almost symmetries. Empirically, reducing the number of significant bits through rounding often leads to instances that are easier to solve. One reason can be that the amount of symmetries increases, which enables solvers to be more effective when they are exploited. This can signify that the original instance contains 'almost symmetries'. Furthermore, solving the rounded problems provides approximations to the original objective values. We empirically investigate these relations on instances of the capacitated facility location problem, the knapsack problem and a diverse collection of additional instances, using the solvers SCIP and CP-SAT. For all investigated problem classes, we show empirically that this yields faster algorithms with guaranteed solution quality. The influence of symmetry depends on the instance type and solver. |
| title | Objective Coefficient Rounding and Almost Symmetries in Binary Programs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2512.10507 |