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
- Diffusion Models as Network Optimizers: Explorations and Analysis [71.69869025878856]
generative diffusion models (GDMs) have emerged as a promising new approach to network optimization.
In this study, we first explore the intrinsic characteristics of generative models.
We provide a concise theoretical and intuitive demonstration of the advantages of generative models over discriminative network optimization.
arXiv Detail & Related papers (2024-11-01T09:05:47Z) - On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning [85.75164588939185]
We study the discriminative probabilistic modeling problem on a continuous domain for (multimodal) self-supervised representation learning.
We conduct generalization error analysis to reveal the limitation of current InfoNCE-based contrastive loss for self-supervised representation learning.
arXiv Detail & Related papers (2024-10-11T18:02:46Z) - 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) - 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) - 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.