Uma condição suficiente para otimização global sem retrocesso

Abstract

Resumo: Um problema de satisfação de restrições (CSP, do inglês constraint satisfaction problem) consiste em encontrar uma atribuição de valores a um conjunto de variáveis que satisfaça uma rede de restrições. Técnicas de consistência local desempenham um papel central na resolução de CSPs, excluindo valores que certamente não constituem uma solução do problema. Muitos esforços vêm sendo aplicados na identificação de classes de CSPs relacionando a estrutura da rede (representada por um hipergrafo) com o nível de consistência local que garante uma solução livre de retrocesso, isto é, uma busca que encontra uma solução em um número polinomial de passos em relação ao tamanho da instância. Nesta tese, problemas de otimização global são representados por hipergrafos com um vértice raiz que representa a função objetivo a ser minimizada. Uma forma de decomposição de hipergrafos, chamada decomposição Epífita, é apresentada. Através da decomposição Epífita do hipergrafo de restrições, caracteriza-se uma classe de problemas de otimização onde a consistência de arco relacional direcionada garante uma solução livre de retrocesso. Alcançar consistência relacional exige a adição de novas restrições na rede, alterando a sua estrutura; por essa razão, um método de ramificação e poda intervalar para alcançar uma forma relaxada dessa consistência é proposto, encontrando uma aproximação do mínimo global de problemas de otimização. Um otimizador de código-fonte aberto que implementa esse método, chamado OGRe, é apresentado. A fim de generalizar o conceito de decomposição Epífita a todos os problemas de otimização, um parâmetro de largura de hipergrafos chamado largura epífita é introduzido. Como principal contribuição desta tese, mostra-se que problemas de otimização representados por hipergrafos com largura epífita k possuem decomposições k-Epífitas e são resolvidos sem retrocesso se alcançada k-consistência relacional direcionada forte.

Abstract: A constraint satisfaction problem (CSP) consists of finding an assignment of values to a set of variables that satisfy a constraint network. Local consistency techniques play a central role in solving CSPs, pruning values that surely do not constitute a solution of the problem. Many efforts have been applied to identify classes of CSPs by linking the constraint network structure (represented by a hypergraph) to the level of local consistency that guarantees a backtrack-free solution, i.e., a search that finds a solution in a polynomial number of steps with relation to the size of the instance. In this thesis, global optimization problems are represented by hypergraphs with a root vertex that represents the objective function to be minimized. A form of hypergraph decomposition is introduced, called Epiphytic decomposition. By the Epiphytic decomposition of constraint hypergraphs a class of optimization problems is characterized, for which directional relational arc-consistency ensures a backtrack-free solution. Achieving relational consistency requires the addition of new constraints on the network, changing its structure; for this reason, an interval branch and bound method to enforce a relaxed form of this consistency is proposed, thus finding an approximation for the global minimum of optimization problems. An open-source optimizer that implements this method, namely OGRe, is introduced. In order to generalize the Epiphytic decomposition concept to cover all optimization problems, a hypergraph width parameter is introduced, called epiphytic width. As the main contribution of this thesis, it is shown that optimization problems represented by hypergraphs with epiphytic width k have k-Epiphytic decompositions and are solved in a backtrack-free manner if achieved strong directional relational k-consistency.