Estudo da eficiência das restrições iniciais na resolução do problema da clique máxima com programação linear inteira

Abstract

This study investigates the efficiency of applying initial constraints in solving the Maximum Clique Problem (MCP) using Integer Linear Programming (ILP). MCP is a classic problem in Graph Theory, widely applied in various fields such as bioinformatics, social networks, and signal transmission analysis. The research focuses on the mathematical formulation of the problem and the implementation of a specific solver, SCIP, to evaluate the impact of initial constraints on processing time optimization. To this end, experimental tests were conducted with graphs of different sizes and densities, comparing the solver’s performance with and without the application of constraints. The results indicate that the inclusion of vertex-coloring-based constraints significantly reduces execution time, making the method more efficient for large and complex graphs. It is concluded that the use of initial constraints is a promising strategy for optimizing combinatorial problems modeled by ILP.