Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Correlated Mutations for Integer Programming

Created by
  • Haebom

Author

Ofer M. Shir, Michael Emmerich

Outline

This paper is a study on the foundation of Integer Evolutionary Strategy (IES), a new heuristic technique for solving integer programming (IP) problems. Existing IESs are discretized and modified to apply the algorithms designed for continuous spaces to IP problems, which are discrete spaces, and operate based on the $\ell_2$-norm. This study adopts the $\ell_1$-norm, considers an appropriate step size, and explores an alternative method for measuring correlations on integer grids to establish a foundation for discrete search. In particular, we focus on mutation distributions for infinite integer decision variables, point out the limitations of discrete probability distributions based on uniform and binomial distributions, and focus on the truncated normal distribution (TN) and double geometric distribution (DG). We analyze their theoretical properties, including the entropy function, and propose a procedure for generating scalable correlated mutation distributions. Through extensive numerical experiments, we demonstrate that the DG distribution is more suitable for infinite integer search, and empirically verify that IESs using correlated DG mutations outperform other strategies in nonseparable quadratic IP problems. In conclusion, we emphasize that although replacing the TN distribution with the DG distribution provides theoretical justification and practical advantages, adopting the $\ell_1$-norm instead of the $\ell_2$-norm is a more significant change.

Takeaways, Limitations

Takeaways:
We propose a new IES design method based on the $\ell_1$-norm and show that it can improve the efficiency of solving integer programming problems.
The superiority of the DG distribution as a mutation distribution for infinite integer variables is proven theoretically and experimentally.
We propose a scalable procedure to generate correlated mutation distributions.
We experimentally verify the superior performance of DG-based IES in non-separable quadratic IP problems.
Limitations:
This study focuses on infinite integer decision variables, and additional research on finite integer variables is needed.
The performance of the proposed method has been evaluated only for certain types of IP problems, so additional experiments on more diverse problem types are needed.
The analysis of discrete probability distributions based on the uniform distribution and the binomial distribution has been covered relatively briefly. A more in-depth analysis may be required.
👍