Benchmarking Metaheuristics for Mixed-Integer Optimization

Abstract

Mixed-integer optimization (MIO) involves solving a problem defined by both discrete and continuous decision variables. Although common in real-world applications, MIO is difficult to solve because traditional metaheuristics are primarily designed for a single variable type. This paper compares six different strategies identified in a recent survey, categorizing them as either global strategies (GS), which treat the decision vector as a unified type, or decomposition-based strategies (DS), which split the problem into continuous and discrete subproblems. We benchmark these strategies based on a genetic algorithm across the 24 functions of the COCO BBOB-mixint test suite. The results show that GS are more efficient at performing simple functions and are more robust in multi-modal landscapes. As expected, however, DS are vulnerable to variable interdependencies. A resolution limit has been identified for high conditioning functions, whereby all strategies reach a performance ceiling. This is partly because the landscape features are smaller than the minimum integer step size of 1, causing the algorithm to exceed the optimal level. These results suggest that future research should explore hybrid metaheuristics to overcome the inherent constraints of the integer grid.