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

• URL: http://arxiv.org/abs/2405.18884v1
• Date: Wed, 29 May 2024 08:41:08 GMT
• Title: Learning Mixture-of-Experts for General-Purpose Black-Box Discrete Optimization
• Authors: Shengcai Liu, Zhiyuan Wang, Yew-Soon Ong, Xin Yao, Ke Tang,
• Abstract summary: This article introduces MEGO, a novel general-purpose neural 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. MEGO actively selects relevant expert models to generate high-quality solutions.
• Score: 45.243090644194695
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Autoformulation of Mathematical Optimization Models Using LLMs [50.030647274271516]
  We develop an automated approach to creating optimization models from natural language descriptions for commercial solvers. We identify the three core challenges of autoformulation: (1) defining the vast, problem-dependent hypothesis space, (2) efficiently searching this space under uncertainty, and (3) evaluating formulation correctness.
  arXiv  Detail & Related papers  (2024-11-03T20:41:38Z)
• LLMOPT: Learning to Define and Solve General Optimization Problems from Scratch [16.174567164068037]
  We propose a unified learning-based framework called LLMOPT to boost optimization generalization. LLMOPT constructs the introduced five-element formulation as a universal model for learning to define diverse optimization problem types. We evaluate the optimization generalization ability of LLMOPT and compared methods across six real-world datasets.
  arXiv  Detail & Related papers  (2024-10-17T04:37:37Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• Solving General Natural-Language-Description Optimization Problems with Large Language Models [34.50671063271608]
  We propose a novel framework called OptLLM that augments LLMs with external solvers. OptLLM accepts user queries in natural language, convert them into mathematical formulations and programming codes, and calls the solvers to calculate the results. Some features of OptLLM framework have been available for trial since June 2023.
  arXiv  Detail & Related papers  (2024-07-09T07:11:10Z)
• Deep-ELA: Deep Exploratory Landscape Analysis with Self-Supervised Pretrained Transformers for Single- and Multi-Objective Continuous Optimization Problems [0.5461938536945723]
  In this work, we propose a hybrid approach, Deep-ELA, which combines (the benefits of) deep learning and ELA features. Our proposed framework can either be used out-of-the-box for analyzing single- and multi-objective continuous optimization problems, or subsequently fine-tuned to various tasks.
  arXiv  Detail & Related papers  (2024-01-02T12:41:17Z)
• A Study of Scalarisation Techniques for Multi-Objective QUBO Solving [0.0]
  Quantum and quantum-inspired optimisation algorithms have shown promising performance when applied to academic benchmarks as well as real-world problems. However, QUBO solvers are single objective solvers. To make them more efficient at solving problems with multiple objectives, a decision on how to convert such multi-objective problems to single-objective problems need to be made.
  arXiv  Detail & Related papers  (2022-10-20T14:54:37Z)
• Dynamic Multi-objective Ensemble of Acquisition Functions in Batch Bayesian Optimization [1.1602089225841632]
  The acquisition function plays a crucial role in the optimization process. Three acquisition functions are dynamically selected from a set based on their current and historical performance. Using an evolutionary multi-objective algorithm to optimize such a MOP, a set of non-dominated solutions can be obtained.
  arXiv  Detail & Related papers  (2022-06-22T14:09:18Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Learning to Optimize: A Primer and A Benchmark [94.29436694770953]
  Learning to optimize (L2O) is an emerging approach that leverages machine learning to develop optimization methods. This article is poised to be the first comprehensive survey and benchmark of L2O for continuous optimization.
  arXiv  Detail & Related papers  (2021-03-23T20:46:20Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making. We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
  arXiv  Detail & Related papers  (2020-06-18T19:11:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.