Probabilistic models for a class of computing costs distributions

Doctorate in Applied Mathematics for Business and EconomicsConstraint Satisfaction Problems are the subject of intense research in Artificial Intelligence and Operations Research, They often exhibit high complexity, requir¬ing a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Randomized search methods have greatly extended our ability to solve hard computational problems. As literature often shows, in some cases, runtime distributions display heavy-tailed behavior. The results in literature are mainly empirical. In this work, we propose a mathematical approach based on probabilistic models. The Constraint Satisfaction Problem studied is the Latin square. We show how the different regimes observed can be captured by a mixture of stable distributions. We also provide search tree models for any degree of heavy-tailedness. Finally, we show how to generate heavy tails in Latin squares. A scale free urn model is presented to set a lower bound for the tail. All our research results have significant economic implications as Constraint Satis¬faction Problems are ubiquitous in scheduling and other typical Operations Research problems. Our results provide modeling tools for the tail behavior of computational costs and give a new insight into the nature of their computational complexity.Problemas de satisfiabilidade com restrições têm sido alvo de muita investigação em Inteligência Artificial e Investigação Operacional. Estes problemas apresentam geralmente uma grande complexidade, sendo necessário usar uma combinação de heurísticas e métodos de procura para os resolver em tempo útil. A introdução de métodos de procura aleatórios permitiu resolver muitos desses problemas computa¬cionais complexos. Muitos dos trabalhos sobre a distribuição dos tempos de computação mostram que esta exibe caudas pesadas. Estes resultados são sobretudo empíricos. Neste tra¬balho, propomos uma abordagem mais matemática, baseada em modelos proba¬bilísticos. O problema estudado é o quadrado latino. Mostra-se como os diferentes regimes observados podem ser reproduzidos através de uma mistura de distribuições estáveis. Também se mostra como reproduzir qualquer tipo de decaimento da cauda da distribuição através de árvores de procura. Finalmente, mostra-se como gerar as caudas pesadas no quadrado latino, apresenta-se uma urna com auto-semelhança para estabelecer um limite inferior para a cauda da distribuição. Os resultados deste trabalho têm implicações económicas, uma vez que os problemas de satisfiabilidade com restrições aparecem em problemas de calendarização e outros problemas de Investigação Operacional. Os resultados apresentados neste trabalho fornecem modelos para a cauda da distribuição dos custos de computação e dão novas pistas para o estudo da sua natureza complexa