Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2501.05052 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913949158473728 |
|---|---|
| author | Huang, Weimin Isenberg, Natalie M. Drgona, Jan Vrabie, Draguna L Dilkina, Bistra |
| author_facet | Huang, Weimin Isenberg, Natalie M. Drgona, Jan Vrabie, Draguna L Dilkina, Bistra |
| contents | Mixed Binary Quadratic Programs (MBQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and chemical and energy systems. Large-scale MBQPs are challenging to solve with exact algorithms due to the combinatorial search space and nonlinearity. Primal heuristics have been developed to quickly identify high-quality solutions to challenging combinatorial optimization problems. In this paper, we propose an extension for two well-established rounding-based primal heuristics, RENS and Undercover. Instead of using the optimal solution to a relaxation for variable rounding and search as in RENS, we use a suboptimal relaxation solution of the MBQP as the basis for rounding and guidance for searching over a restricted subproblem where a certain percentage of binary variables are free. We apply a similar idea to the Undercover heuristic that fixes a variable cover to the rounded relaxation values. Instead, we relax a subset of the cover variables based on the suboptimal relaxation and search over a larger restricted subproblem. We evaluate our proposed methods on synthetic MBQP benchmarks and real-world wind farm layout optimization problem instances. The results show that our proposed heuristics identify high-quality solutions within a small time limit and significantly reduce the primal gap and primal integral compared to RENS, Undercover, and solvers with additional primal heuristics integrated inside Branch-and-Bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05052 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient Primal Heuristics for Mixed Binary Quadratic Programs Using Suboptimal Rounding Guidance Huang, Weimin Isenberg, Natalie M. Drgona, Jan Vrabie, Draguna L Dilkina, Bistra Optimization and Control Mixed Binary Quadratic Programs (MBQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and chemical and energy systems. Large-scale MBQPs are challenging to solve with exact algorithms due to the combinatorial search space and nonlinearity. Primal heuristics have been developed to quickly identify high-quality solutions to challenging combinatorial optimization problems. In this paper, we propose an extension for two well-established rounding-based primal heuristics, RENS and Undercover. Instead of using the optimal solution to a relaxation for variable rounding and search as in RENS, we use a suboptimal relaxation solution of the MBQP as the basis for rounding and guidance for searching over a restricted subproblem where a certain percentage of binary variables are free. We apply a similar idea to the Undercover heuristic that fixes a variable cover to the rounded relaxation values. Instead, we relax a subset of the cover variables based on the suboptimal relaxation and search over a larger restricted subproblem. We evaluate our proposed methods on synthetic MBQP benchmarks and real-world wind farm layout optimization problem instances. The results show that our proposed heuristics identify high-quality solutions within a small time limit and significantly reduce the primal gap and primal integral compared to RENS, Undercover, and solvers with additional primal heuristics integrated inside Branch-and-Bound. |
| title | Efficient Primal Heuristics for Mixed Binary Quadratic Programs Using Suboptimal Rounding Guidance |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2501.05052 |