arXiv:2203.08209

A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks

Ismail R. Alkhouri, George K. Atia, Alvaro Velasquez

제출 2022-03-15

원문 초록

The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures. In this paper, 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 combinatorial 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. We consider the combinatorial optimization problems of finding maximum independent sets and maximum cliques in a graph. In principle, since these problems belong to the NP-hard complexity class, our proposed approach can be used to solve any other NP-hard problem. Additionally, we propose a universal graph reduction procedure to handle large scale graphs. The reduction exploits community detection for graph partitioning and is applicable to any graph type and/or density. Experimental evaluation on both synthetic graphs and real-world benchmarks demonstrates that our method performs on par with or outperforms state-of-the-art heuristic, reinforcement learning, and machine learning based methods without requiring any data.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.13218v1cs.DS공통 태그 Combinatorial Optimization, graph partitioning

수요가 있는 그래프 분할: 일반화된 컨던턴스와 그 응용

Graph Partitioning with Demands: Generalized Conductance and its Applications

본 논문에서는 일반적인 수요 모델 하에서 다양한 그래프 분할 문제를 연구한다. 각 문제에서 용량 함수 $c\colon E\to \mathbb{N}$와 수요 함수 $w\colon V\times V\to \mathbb{N}$가 주어진 그래프 $G=(V,E,c,w)$가 주어진다. 우리의 주요 관심사는 컷 $(S, \bar{S})$를 찾아 다음 양을 최소화하는 문제이다. \[ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. \] 여기서 $c( S, \bar{S} )$는 $S$와 $S$의 여집합 $\bar{S}$ 사이의 간선 비용이며, $w( S, V )=w( S )+w( S, \bar{S} )$는 $S$ 내부의 내부 수요 $w( S )$와 $S$의 꼭짓점과 $\bar{S}$의 꼭짓점 사이의 수요 $w( S, \bar{S} )$의 합이다. $ψ_w( S )$를 컷 $(S, \bar{S})$의 \emph{generalized conductance}(일반화된 컨던턴스)라 하고, $ψ_w( S )$를 최소화하는 과제를 Generalized Conductance Problem(일반화된 컨던턴스 문제)라 부른다. 주요 기여는 이 목적함수에 대해 $\mathcal{O}(\log n)$-근사 보장을 갖는 알고리즘을 제시하는 것이다. 이 결과는 양방향 환원을 통해 달성된다. 먼저 잘 알려진 Generalized $k$-Multicut Problem으로 환원하고, 이어서 잘릴 수 있는 수요량에 대한 추가 상한 제약이 있는 고전 Sparsest-Cut Problem의 제약 변형으로 환원한다. 더 나아가, 위 절차가 수요가 있는 그래프 분할(Graph Partitioning with Demands)에 대해 $\mathcal{O}(\log n)$-이기준 근사를 얻는 데 사용될 수 있음을 보인다. 여기서 목표는 $G\setminus C$의 모든 연결 성분 $H$에 대해 $w( H )\leq ρ\cdot w( V )$를 만족하는 최소 비용의 간선 부분집합 $C$를 찾는 것이다. 이는 차례로 수요가 있는 계층적 클러스터링(Hierarchical Clustering with Demands)—그래프를 점점 더 세분화된 클러스터로 분할하는 컷의 계층을 찾는 문제—에 대한 $\mathcal{O}(\log n)$-근사를 제공한다. 곱셈형 수요 함수(multiplicative demand functions)의 경우 이러한 보장을 $\mathcal{O}(\sqrt{\log n})$로 개선하며, 트리(tree)의 경우 모든 목적함수에 대해 $\mathcal{O}(1)$-근사를 얻는다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.