A diving heuristic for mixed-integer problems with unbounded semi-continuous variables

Halbig K, Hoen A, Gleixner A, Witzig J, Weninger D (2025)

Publication Type: Journal article

Publication year: 2025

Journal

EURO Journal on Computational Optimization Springer

Book Volume: 13

Article Number: 100107

DOI: 10.1016/j.ejco.2025.100107

Abstract

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.

Authors with CRIS profile

Katrin Halbig Lehrstuhl für Analytics & Mixed-Integer Optimization Dieter Weninger Department Mathematik

Involved external institutions

Konrad-Zuse-Zentrum für Informationstechnik / Zuse Institute Berlin (ZIB) DE Germany (DE) SAP AG/SAP SE DE Germany (DE)

How to cite

APA:

Halbig, K., Hoen, A., Gleixner, A., Witzig, J., & Weninger, D. (2025). A diving heuristic for mixed-integer problems with unbounded semi-continuous variables. EURO Journal on Computational Optimization, 13. https://doi.org/10.1016/j.ejco.2025.100107

MLA:

Halbig, Katrin, et al. "A diving heuristic for mixed-integer problems with unbounded semi-continuous variables." EURO Journal on Computational Optimization 13 (2025).

BibTeX: Download