An Alternating Primal Heuristic for Nonconvex MIQCQP with Dynamic Convexification and Parallel Local Branching
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917385726853120 |
|---|---|
| author | Dai, Yongzheng Chen, Chen |
| author_facet | Dai, Yongzheng Chen, Chen |
| contents | We develop a novel primal heuristic for nonconvex Mixed-Integer Quadratically Constrained Quadratic Programs (MIQCQPs). The method is built around a convex approximation that is dynamically adjusted within a feasibility-pump-style alternating heuristic. Approximations are adjusted based on the structure of the MIQCQP instance. Additionally, parallelized local branching is incorporated to further refine detected solutions. This paper builds upon the second-place finalist submission in the 2025 Land-Doig MIP Computational Competition. Our results are validated with computational experiments on instances from QPLIB, finding feasible solutions for three previously unsolved cases and improving the best-known solutions for fifteen instances within five minutes of runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04417 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | An Alternating Primal Heuristic for Nonconvex MIQCQP with Dynamic Convexification and Parallel Local Branching Dai, Yongzheng Chen, Chen Optimization and Control We develop a novel primal heuristic for nonconvex Mixed-Integer Quadratically Constrained Quadratic Programs (MIQCQPs). The method is built around a convex approximation that is dynamically adjusted within a feasibility-pump-style alternating heuristic. Approximations are adjusted based on the structure of the MIQCQP instance. Additionally, parallelized local branching is incorporated to further refine detected solutions. This paper builds upon the second-place finalist submission in the 2025 Land-Doig MIP Computational Competition. Our results are validated with computational experiments on instances from QPLIB, finding feasible solutions for three previously unsolved cases and improving the best-known solutions for fifteen instances within five minutes of runtime. |
| title | An Alternating Primal Heuristic for Nonconvex MIQCQP with Dynamic Convexification and Parallel Local Branching |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.04417 |