# Correlated Mutations for Integer Programming

arXiv: https://arxiv.org/abs/2506.22526 · HTML: https://mlsanity.com/paper/2506.22526/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 33 references that are in the map.
- First posted on arXiv 27 Jun 2025.

## Builds on (most cited first, 5 of 5)

- [IOHanalyzer: Detailed Performance Analyses for Iterative Optimization Heuristics](https://mlsanity.com/paper/2007.03953/) (2020)
- [CMA-ES with Margin: Lower-Bounding Marginal Probability for Mixed-Integer Black-Box Optimization](https://mlsanity.com/paper/2205.13482/) (2022)
- [On the Covariance-Hessian Relation in Evolution Strategies](https://mlsanity.com/paper/1806.03674/) (2018)
- [The Subspace Flatness Conjecture and Faster Integer Programming](https://mlsanity.com/paper/2303.14605/) (2023)
- [Abnormal Mutations: Evolution Strategies Don't Require Gaussianity](https://mlsanity.com/paper/2502.03148/) (2025)

## Abstract (arXiv)

Even with the recent theoretical advancements that dramatically reduced the complexity of Integer Programming (IP), heuristics remain the dominant problem-solvers for this difficult category. This study seeks to establish the groundwork for Integer Evolution Strategies (IESs), a class of randomized search heuristics inherently designed for continuous spaces. IESs already excel in treating IP in practice, but accomplish it via discretization and by applying sophisticated patches to their continuous operators, while persistently using the ℓ2-norm as their operation pillar. We lay foundations for discrete search, by adopting the ℓ1-norm, accounting for the suitable step-size, and questioning alternative measures to quantify correlations over the integer lattice. We focus on mutation distributions for unbounded integer decision variables. We briefly discuss a couple of candidate discrete probabilities induced by the uniform and binomial distributions, which we show to possess less appealing theoretical properties, and then narrow down to the Truncated Normal (TN) and Double Geometric (DG) distributions. We explore their theoretical properties, including entropy functions, and propose a procedure to generate scalable correlated mutation distributions. Our investigations are accompanied by extensive numerical simulations, which consistently support the claim that the DG distribution is better suited for unbounded integer search. We link our theoretical perspective to empirical evidence indicating that an IES with correlated DG mutations outperformed other strategies over non-separable quadratic IP. We conclude that while the replacement of the default TN distribution by the DG is theoretically justified and practically beneficial, the truly crucial change lies in adopting the ℓ1-norm over the ℓ2-norm.