A diving heuristic for mixed-integer problems with unbounded semi-continuous variables
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913548538478592 |
|---|---|
| author | Halbig, Katrin Hoen, Alexander Gleixner, Ambros Witzig, Jakob Weninger, Dieter |
| author_facet | Halbig, Katrin Hoen, Alexander Gleixner, Ambros Witzig, Jakob Weninger, Dieter |
| contents | Semi-continuous decision variables arise naturally in many real-world applications. They are defined to take either value zero or any value within a specified range, and occur mainly to prevent small nonzero values in the solution. One particular challenge that can come with semi-continuous variables in practical models is that their upper bound may be large or even infinite. In this article, we briefly discuss these challenges, and present a new diving heuristic tailored for mixed-integer optimization problems with general semi-continuous variables. The heuristic is designed to work independently of whether the semi-continuous variables are bounded from above, and thus circumvents the specific difficulties that come with unbounded semi-continuous variables. We conduct extensive computational experiments on three different test sets, integrating the heuristic in an open-source MIP solver. The results indicate that this heuristic is a successful tool for finding high-quality solutions in negligible time. At the root node the primal gap is reduced by an average of 5 % up to 21 %, and considering the overall performance improvement, the primal integral is reduced by 2 % to 17 % on average. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_19411 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A diving heuristic for mixed-integer problems with unbounded semi-continuous variables Halbig, Katrin Hoen, Alexander Gleixner, Ambros Witzig, Jakob Weninger, Dieter Optimization and Control 90C10, 90C59, 90C90 Semi-continuous decision variables arise naturally in many real-world applications. They are defined to take either value zero or any value within a specified range, and occur mainly to prevent small nonzero values in the solution. One particular challenge that can come with semi-continuous variables in practical models is that their upper bound may be large or even infinite. In this article, we briefly discuss these challenges, and present a new diving heuristic tailored for mixed-integer optimization problems with general semi-continuous variables. The heuristic is designed to work independently of whether the semi-continuous variables are bounded from above, and thus circumvents the specific difficulties that come with unbounded semi-continuous variables. We conduct extensive computational experiments on three different test sets, integrating the heuristic in an open-source MIP solver. The results indicate that this heuristic is a successful tool for finding high-quality solutions in negligible time. At the root node the primal gap is reduced by an average of 5 % up to 21 %, and considering the overall performance improvement, the primal integral is reduced by 2 % to 17 % on average. |
| title | A diving heuristic for mixed-integer problems with unbounded semi-continuous variables |
| topic | Optimization and Control 90C10, 90C59, 90C90 |
| url | https://arxiv.org/abs/2403.19411 |