Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems

• URL: http://arxiv.org/abs/2102.03002v1
• Date: Fri, 5 Feb 2021 05:23:26 GMT
• Title: Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems
• Authors: Yiwei Bai, Wenting Zhao, Carla P. Gomes
• Abstract summary: ZTop is a simple yet effective model selection and ensemble mechanism for learning to solve problems. We show how ZTopping, using a ZTop ensemble strategy with a given deep learning approach, can significantly improve the performance of the current state-of-the-art deep learning approaches.
• Score: 21.411742165753456
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: There has been an increasing interest in harnessing deep learning to tackle combinatorial optimization (CO) problems in recent years. Typical CO deep learning approaches leverage the problem structure in the model architecture. Nevertheless, the model selection is still mainly based on the conventional machine learning setting. Due to the discrete nature of CO problems, a single model is unlikely to learn the problem entirely. We introduce ZTop, which stands for Zero Training Overhead Portfolio, a simple yet effective model selection and ensemble mechanism for learning to solve combinatorial problems. ZTop is inspired by algorithm portfolios, a popular CO ensembling strategy, particularly restart portfolios, which periodically restart a randomized CO algorithm, de facto exploring the search space with different heuristics. We have observed that well-trained models acquired in the same training trajectory, with similar top validation performance, perform well on very different validation instances. Following this observation, ZTop ensembles a set of well-trained models, each providing a unique heuristic with zero training overhead, and applies them, sequentially or in parallel, to solve the test instances. We show how ZTopping, i.e., using a ZTop ensemble strategy with a given deep learning approach, can significantly improve the performance of the current state-of-the-art deep learning approaches on three prototypical CO domains, the hardest unique-solution Sudoku instances, challenging routing problems, and the graph maximum cut problem, as well as on multi-label classification, a machine learning task with a large combinatorial label space.

Related papers

• EnsIR: An Ensemble Algorithm for Image Restoration via Gaussian Mixture Models [70.60381055741391]
  Image restoration challenges related to illposed problems, resulting in deviations between single model predictions and ground-truths. Ensemble learning aims to address these deviations by combining the predictions of multiple base models. We employ an expectation (EM)-based algorithm to estimate ensemble weights for prediction candidates. Our algorithm is model-agnostic and training-free, allowing seamless integration and enhancement of various pre-trained image restoration models.
  arXiv  Detail & Related papers  (2024-10-30T12:16:35Z)
• GOAL: A Generalist Combinatorial Optimization Agent Learning [0.05461938536945722]
  GOAL is a model capable of efficiently solving multiple hard optimization problems (COPs) Goal consists of a single backbone plus light-weight problem-specific adapters for input and output processing. We show that GOAL is only slightly inferior to the specialized baselines while being the first multi-task model that solves a wide range of COPs.
  arXiv  Detail & Related papers  (2024-06-21T11:55:20Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  We study the problem of model selection in offline RL with value function approximation. We propose the first model selection algorithm for offline RL that achieves minimax rate-optimal inequalities up to logarithmic factors. We conclude with several numerical simulations showing it is capable of reliably selecting a good model class.
  arXiv  Detail & Related papers  (2022-11-03T17:32:34Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• A Unified Analysis of Dynamic Interactive Learning [5.474944738795308]
  Previous work by Emamjomeh-Zadeh et al. [ 2020] introduced dynamics into interactive learning as a way to model non-static user preferences. We give a framework that captures both of the models analyzed by [Emamjomeh-Zadeh et al., 2020], which allows us to study any type of concept evolution. We also study an efficient algorithm where the learner simply follows the feedback at each round.
  arXiv  Detail & Related papers  (2022-04-14T16:03:37Z)
• On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization [6.935838847004389]
  Combinatorial optimization problems (COPs) on the graph with real-life applications are canonical challenges in Computer Science. The underlying principle of this approach is to deploy a graph neural network (GNN) for encoding both the local information of the nodes and the graph-structured data. We use the security-aware phone clone allocation in the cloud as a classical quadratic assignment problem (QAP) to investigate whether or not deep RL-based model is generally applicable to solve other classes of such hard problems.
  arXiv  Detail & Related papers  (2021-08-08T19:12:04Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems [4.692304496312442]
  This paper introduces a new deep learning approach to approximately solve the Covering Salesman Problem (CSP) In this approach, given the city locations of a CSP as input, a deep neural network model is designed to directly output the solution. It is trained using the deep reinforcement learning without supervision.
  arXiv  Detail & Related papers  (2021-02-11T07:25:04Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  We present SUNRISE, a simple unified ensemble method, which is compatible with various off-policy deep reinforcement learning algorithms. SUNRISE integrates two key ingredients: (a) ensemble-based weighted Bellman backups, which re-weight target Q-values based on uncertainty estimates from a Q-ensemble, and (b) an inference method that selects actions using the highest upper-confidence bounds for efficient exploration.
  arXiv  Detail & Related papers  (2020-07-09T17:08:44Z)
• Stepwise Model Selection for Sequence Prediction via Deep Kernel Learning [100.83444258562263]
  We propose a novel Bayesian optimization (BO) algorithm to tackle the challenge of model selection in this setting. In order to solve the resulting multiple black-box function optimization problem jointly and efficiently, we exploit potential correlations among black-box functions. We are the first to formulate the problem of stepwise model selection (SMS) for sequence prediction, and to design and demonstrate an efficient joint-learning algorithm for this purpose.
  arXiv  Detail & Related papers  (2020-01-12T09:42:19Z)
• Learning fine-grained search space pruning and heuristics for combinatorial optimization [5.72274610208488]
  We propose a framework for leveraging machine learning techniques to scale-up exact optimization algorithms. Our framework learns the relatively simpler task of pruning the elements in order to reduce the size of the problem instances. We show that our framework can prune a large fraction of the input graph and still detect almost all of the maximum cliques.
  arXiv  Detail & Related papers  (2020-01-05T13:10:39Z)

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.