Algoritmos de ramificação e poda aprimorados por aprendizado profundo na resolução do problema da clique máxima

Abstract

This work addresses the Maximum Clique Problem (MCP) in graphs, a well-known challenge in graph theory and combinatorial optimization. Exact algorithms are computationally expensive, and heuristic algorithms designed for MCP rely on good initial solutions. Therefore, the application of machine learning (ML) methods to solve the MCP is considered. The main goal is to use ML models to decide the branching order for Branch and Bound (B&B) algorithms that solve the MCP. Initially, the MCP and B&B algorithms are addressed. Subsequently, neural networks are presented as a powerful tool for learning branching patterns in search trees. Finally, the results of integrating ML with B&B algorithms that solve the MCP are presented.