Learning Mixture-of-Experts for General-Purpose Black-Box Discrete Optimization

Shengcai Liu, Zhiyuan Wang, Yew-Soon Ong, Xin Yao, Ke Tang

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.

Overview of the MEGO framework, including expert architecture, training, routing, fine-tuning, and solution generation.

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

Abstract

Real-world applications involve various discrete optimization problems. Designing a specialized optimizer for each of these problems is challenging, typically requiring significant domain knowledge and human efforts. Hence, developing general-purpose optimizers as an off-the-shelf tool for a wide range of problems has been a long-standing research target. This article introduces MEGO, a novel general-purpose neural optimizer trained through a fully data-driven learning-to-optimize (L2O) approach. MEGO consists of a mixture-of-experts trained on experiences from solving training problems and can be viewed as a foundation model for optimization problems with binary decision variables. When presented with a problem to solve, MEGO actively selects relevant expert models to generate high-quality solutions. MEGO can be used as a standalone sample-efficient optimizer or in conjunction with existing search methods as an initial solution generator. The generality of MEGO is validated across six problem classes, including three classic problem classes and three problem classes arising from real-world applications in compilers, network analysis, and 3D reconstruction. Trained solely on classic problem classes, MEGO performs very well on all six problem classes, significantly surpassing widely used general-purpose optimizers in both solution quality and efficiency. In some cases, MEGO even surpasses specialized state-of-the-art optimizers. Additionally, MEGO provides a similarity measure between problems, yielding a new perspective for problem classification. In the pursuit of general-purpose optimizers through L2O, MEGO represents an initial yet significant step forward.
BibTeX
@misc{liu2024learning,
  author = {Shengcai Liu and Zhiyuan Wang and Yew-Soon Ong and Xin Yao and Ke Tang},
  title = {{Learning Mixture-of-Experts for General-Purpose Black-Box Discrete Optimization}},
  year = {2024},
  eprint = {2405.18884},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2405.18884},
}
Figure