A diving heuristic for mixed-integer problems with unbounded semi-continuous variables
Katrin Halbig et al.
What the paper says
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.
2 citations
Evidence weight
Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40
| F · citation impact | 0.25 × 0.4 = 0.10 |
| M · momentum | 0.55 × 0.15 = 0.08 |
| V · venue signal | 0.50 × 0.05 = 0.03 |
| R · text relevance † | 0.50 × 0.4 = 0.20 |
† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.