Análise da aplicação do Delayed Improvement Local Search ao problema Max-SAT

Oproblema da Satisfatibilidade Máxima (Max-SAT) é um problema clássico da otimi zação combinatória amplamente abordado por métodos de busca local baseados em movimentos 1-Flip. Entretanto, estratégias tradicionais de pivotamento, como Best Improvement Local Search (BILS) e First Improvement Local Search (FILS), tendem a convergir rapidamente para ótimos lo cais de baixa qualidade. Neste trabalho, investigamos a aplicação do Delayed Improvement Local Search (DILS) ao problema Max-SAT. O método utiliza pré-condições de otimalidade local deri vadas de desigualdades de busca local para priorizar soluções aprimorantes potencialmente menos associadas à convergência prematura. O DILS foi comparado experimentalmente com as estraté gias BILS e FILS em instâncias SAT e UNSAT da biblioteca SATLIB. Os resultados mostraram que o DILS foi capaz de alcançar soluções competitivas e, em diversas instâncias, superiores às estratégias tradicionais, especialmente em cenários UNSAT, embora apresente maior esforço com putacional por iteração.