Abstract
Real-world applications frequently involve complex discrete optimization problems where designing specialized solvers is labor-intensive and requires deep domain expertise. This paper introduces MEGO (Mixture-of-Experts as General-purpose Optimizers), a novel neural optimizer trained via a data-driven Learning-to-Optimize (L2O) approach. MEGO functions as a foundation model for optimization problems with binary decision variables. By leveraging a mixture of neural experts trained on diverse problem experiences, MEGO can actively select and fine-tune relevant models to generate high-quality solutions for unseen tasks. Evaluated across six problem classes—including classic mathematical benchmarks and real-world applications in compilers, network analysis, and 3D reconstruction—MEGO significantly outperforms standard general-purpose optimizers in both efficiency and solution quality, sometimes even surpassing specialized state-of-the-art tools.
Introduction
Discrete optimization—the process of finding the optimal combination of binary choices—is a cornerstone of fields ranging from drug discovery to social network analysis. Traditionally, practitioners face a difficult trade-off: employ a specialized optimizer, which requires intense manual engineering, or a general-purpose optimizer (like Genetic Algorithms or Bayesian Optimization), which can be slow and sensitive to hyper-parameter tuning.
MEGO addresses this by applying the L2O paradigm to create a domain-agnostic, "off-the-shelf" neural optimizer. It treats previous optimization runs not as ephemeral logs, but as valuable data to learn the underlying "language" of optimization landscapes.
MEGO: A Mixture-of-Experts Approach
The core of MEGO is an architecture based on a Mixture-of-Experts (MoE), designed to capture structural patterns in high-dimensional discrete spaces.
1. Expert Architecture and Training
Each expert model $M_j$ is a Variational Autoencoder (VAE) integrated with a latent score predictor. The VAE maps discrete solutions into a smooth, continuous latent space, allowing the model to navigate the typically "rugged" discrete landscape more effectively. Experts are trained on "experience sets" $E_j$ to simultaneously reconstruct solutions and predict their objective values.
2. Three-Step Deployment
When presented with a new problem instance $I_{new}$, MEGO follows a systematic deployment pipeline:
- Routing: The system samples random solutions to identify which existing experts' predictions correlate most strongly (using Pearson and Spearman coefficients) with the actual objective function of the new problem.
- Fine-tuning: The decoders of the selected experts are rapidly adjusted to align their internal representations with the specific landscape of $I_{new}$.
- Generation: The fine-tuned experts generate a batch of high-quality candidate solutions. These can serve as final results or as a "warm-start" for other search algorithms.
Experimental Setup
The study employs a "train on simple, test on complex" methodology to validate generality:
- Training Set: 27 instances from three classic classes: Generalized One-max (OM), Knapsack Problem (KP), and Max-cut Problem (MC).
- Testing Set: 72 instances, including higher-dimensional versions of the training classes and three entirely unseen real-world applications:
- Compiler Arguments Optimization (CA): Minimizing executable size in GCC.
- Complementary Influence Maximization (CIM): Social network analysis.
- Anchor Selection (AS): 3D reconstruction in computer vision.
Results and Performance
MEGO demonstrates remarkable sample efficiency and solution quality across all tested domains:
- Acceleration: MEGO reached target solution qualities 3.6x to 5.1x faster than standard baselines like Genetic Algorithms (GA) and Bayesian Optimization (BO).
- State-of-the-Art Comparison: In compiler argument optimization, MEGO (when used to warm-start BO) outperformed SMARTEST, a specialized tool designed specifically for that task.
- Scalability: The performance advantage remained consistent as problem dimensionality increased from 40 to 100 variables, indicating superior scaling compared to traditional black-box methods.
Discussion and Future Directions
Beyond optimization performance, MEGO provides a novel perspective on problem similarity. By analyzing which experts are activated for specific tasks, the authors discovered that problem-space similarity often transcends traditional academic categories. For instance, certain compiler tuning tasks were found to be structurally more similar to Knapsack problems than to other compiler instances.
While MEGO represents a significant step toward general-purpose L2O, several avenues for future work remain. Currently, the model is restricted to binary decision variables; extending this to integer or continuous variables is a priority. Additionally, as the pool of experts grows, strategies for efficient expert management and the exploration of "scaling laws" for optimization—how performance scales with the volume of training experience—will be critical for the next generation of neural optimizers.
Summary updated