MEGO: Learning Mixture-of-Experts for General-Purpose Binary Optimization.

Area of Science:

• Computer Science
• Artificial Intelligence
• Operations Research

Background:

• Discrete optimization is crucial across science and engineering.
• Existing optimizers often require problem-specific customization.
• There is a need for general-purpose optimizers for binary problems.

Purpose of the Study:

• Introduce MEGO, a novel neural optimizer for general-purpose binary optimization.
• Demonstrate MEGO's broad applicability and minimal customization requirements.
• Showcase MEGO's ability to generalize across diverse problem classes.

Main Methods:

• MEGO utilizes a mixture-of-experts architecture trained without domain knowledge.
• A routing policy dynamically activates relevant expert models for new problem instances.
• MEGO was evaluated on six diverse problem classes, including classic and real-world applications.

Main Results:

• MEGO demonstrates strong generalization capabilities, even to unseen real-world problems.
• It significantly outperforms widely-used general-purpose optimizers in solution quality.
• MEGO achieves superior efficiency compared to existing optimizers.
• MEGO offers a novel computational approach for problem similarity quantification and classification.

Conclusions:

• MEGO is a highly effective and general-purpose neural optimizer for binary optimization.
• Its ability to generalize and outperform existing methods highlights its potential for broad scientific and engineering applications.
• MEGO introduces a new paradigm for computational problem classification based on similarity.