Pretrained Cost Model for Distributed Constraint Optimization Problems
- URL: http://arxiv.org/abs/2112.04187v1
- Date: Wed, 8 Dec 2021 09:24:10 GMT
- Title: Pretrained Cost Model for Distributed Constraint Optimization Problems
- Authors: Yanchen Deng, Shufeng Kong, Bo An
- Abstract summary: Distributed Constraint Optimization Problems (DCOPs) are an important subclass of optimization problems.
We propose a novel directed acyclic graph schema representation for DCOPs and leverage the Graph Attention Networks (GATs) to embed graph representations.
Our model, GAT-PCM, is then pretrained with optimally labelled data in an offline manner, so as to boost a broad range of DCOP algorithms.
- Score: 37.79733538931925
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Distributed Constraint Optimization Problems (DCOPs) are an important
subclass of combinatorial optimization problems, where information and controls
are distributed among multiple autonomous agents. Previously, Machine Learning
(ML) has been largely applied to solve combinatorial optimization problems by
learning effective heuristics. However, existing ML-based heuristic methods are
often not generalizable to different search algorithms. Most importantly, these
methods usually require full knowledge about the problems to be solved, which
are not suitable for distributed settings where centralization is not realistic
due to geographical limitations or privacy concerns. To address the generality
issue, we propose a novel directed acyclic graph representation schema for
DCOPs and leverage the Graph Attention Networks (GATs) to embed graph
representations. Our model, GAT-PCM, is then pretrained with optimally labelled
data in an offline manner, so as to construct effective heuristics to boost a
broad range of DCOP algorithms where evaluating the quality of a partial
assignment is critical, such as local search or backtracking search.
Furthermore, to enable decentralized model inference, we propose a distributed
embedding schema of GAT-PCM where each agent exchanges only embedded vectors,
and show its soundness and complexity. Finally, we demonstrate the
effectiveness of our model by combining it with a local search or a
backtracking search algorithm. Extensive empirical evaluations indicate that
the GAT-PCM-boosted algorithms significantly outperform the state-of-the-art
methods in various benchmarks. The pretrained model is available at
https://github.com/dyc941126/GAT-PCM.
Related papers
- Joint Graph Learning and Model Fitting in Laplacian Regularized
Stratified Models [5.933030735757292]
Laplacian regularized stratified models (LRSM) are models that utilize the explicit or implicit network structure of the sub-problems.
This paper shows the importance and sensitivity of graph weights in LRSM, and provably show that the sensitivity can be arbitrarily large.
We propose a generic approach to jointly learn the graph while fitting the model parameters by solving a single optimization problem.
arXiv Detail & Related papers (2023-05-04T06:06:29Z) - Regularization and Optimization in Model-Based Clustering [4.096453902709292]
k-means algorithm variants essentially fit a mixture of identical spherical Gaussians to data that vastly deviates from such a distribution.
We develop more effective optimization algorithms for general GMMs, and we combine these algorithms with regularization strategies that avoid overfitting.
These results shed new light on the current status quo between GMM and k-means methods and suggest the more frequent use of general GMMs for data exploration.
arXiv Detail & Related papers (2023-02-05T18:22:29Z) - End-to-End Pareto Set Prediction with Graph Neural Networks for
Multi-objective Facility Location [10.130342722193204]
Facility location problems (FLPs) are a typical class of NP-hard optimization problems, which are widely seen in the supply chain and logistics.
In this paper, we consider the multi-objective facility location problem (MO-FLP) that simultaneously minimizes the overall cost and maximizes the system reliability.
Two graph neural networks are constructed to learn the implicit graph representation on nodes and edges.
arXiv Detail & Related papers (2022-10-27T07:15:55Z) - Exploiting Temporal Structures of Cyclostationary Signals for
Data-Driven Single-Channel Source Separation [98.95383921866096]
We study the problem of single-channel source separation (SCSS)
We focus on cyclostationary signals, which are particularly suitable in a variety of application domains.
We propose a deep learning approach using a U-Net architecture, which is competitive with the minimum MSE estimator.
arXiv Detail & Related papers (2022-08-22T14:04:56Z) - Late Fusion Multi-view Clustering via Global and Local Alignment
Maximization [61.89218392703043]
Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance.
Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering.
We propose late fusion MVC via alignment to address these issues.
arXiv Detail & Related papers (2022-08-02T01:49:31Z) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
We propose a radically different approach in that no data is required for training the neural networks that produce the solution.
In particular, we reduce the optimization problem to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest.
arXiv Detail & Related papers (2022-03-15T19:21:31Z) - Multi-Task Learning on Networks [0.0]
Multi-objective optimization problems arising in the multi-task learning context have specific features and require adhoc methods.
In this thesis the solutions in the Input Space are represented as probability distributions encapsulating the knowledge contained in the function evaluations.
In this space of probability distributions, endowed with the metric given by the Wasserstein distance, a new algorithm MOEA/WST can be designed in which the model is not directly on the objective function.
arXiv Detail & Related papers (2021-12-07T09:13:10Z) - Conservative Objective Models for Effective Offline Model-Based
Optimization [78.19085445065845]
Computational design problems arise in a number of settings, from synthetic biology to computer architectures.
We propose a method that learns a model of the objective function that lower bounds the actual value of the ground-truth objective on out-of-distribution inputs.
COMs are simple to implement and outperform a number of existing methods on a wide range of MBO problems.
arXiv Detail & Related papers (2021-07-14T17:55:28Z) - 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) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF.
We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
arXiv Detail & Related papers (2020-12-04T15:36:29Z) - Semi-Supervised Learning with Meta-Gradient [123.26748223837802]
We propose a simple yet effective meta-learning algorithm in semi-supervised learning.
We find that the proposed algorithm performs favorably against state-of-the-art methods.
arXiv Detail & Related papers (2020-07-08T08:48:56Z)
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.