Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2512.15070 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908717940736000 |
|---|---|
| author | While, Alexander Chen, Chen |
| author_facet | While, Alexander Chen, Chen |
| contents | Formulation symmetry in mixed-integer programming (MIP) can hinder solver performance by inducing redundant search, but detecting such symmetries is also a significant computational challenge. This paper explores the potential for quantum computing to handle symmetry detection. Quantum is a promising alternative to classical compute, but this emerging technology has limited hardware capacity in terms of input problem size. This paper explores the use of Quadratic Unconstrained Binary Optimization (QUBO) models for symmetry detection, as QUBO is the canonical format for quantum optimization platforms. To help address the input size bottleneck, we develop full, reduced, and decomposed QUBO as well as QUBO-Plus formulations for MIP symmetry detection. Computational experiments on the MIPLIB 2017 benchmark are used to estimate the quantum computing resources needed for practical problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_15070 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | QUBO Formulations for MIP Symmetry Detection While, Alexander Chen, Chen Optimization and Control Formulation symmetry in mixed-integer programming (MIP) can hinder solver performance by inducing redundant search, but detecting such symmetries is also a significant computational challenge. This paper explores the potential for quantum computing to handle symmetry detection. Quantum is a promising alternative to classical compute, but this emerging technology has limited hardware capacity in terms of input problem size. This paper explores the use of Quadratic Unconstrained Binary Optimization (QUBO) models for symmetry detection, as QUBO is the canonical format for quantum optimization platforms. To help address the input size bottleneck, we develop full, reduced, and decomposed QUBO as well as QUBO-Plus formulations for MIP symmetry detection. Computational experiments on the MIPLIB 2017 benchmark are used to estimate the quantum computing resources needed for practical problems. |
| title | QUBO Formulations for MIP Symmetry Detection |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2512.15070 |