Seminário de Otimização Combinatória Aritmética afim e aplicações em otimização Jorge Stolfi Sexta-feira, 14 de junho sala: IC2-96 horario: 18hs Resumo: ======= A aritmética afim (AA) é um modelo computacional que, da mesma forma que a aritmética intervalar clássica (AI), objetiva fornecer garantias /a posteriori/ para resultados de cálculos aproximados e/ou que envolvem dados incertos. Enquanto que o modelo AI armazena apenas um intervalo garantido para cada variável, o modelo AA armazena também informações sobre a correlação entre diferentes variáveis. Graças a esta informação adicional, o erro de uma aproximação calculada com AA é normalmente quadrático na largura dos intervalos de entrada, em vez de linear. Tanto AI quanto AA podem servir de base para algoritmos "semi-garantidos" de resolução e otimização de equações não lineares, tipo propagação de restrições e divide-e-limita. Apesar do custo por operação de AA ser mais elevado que o da AI, a maior precisão assintótica da primeira permite eliminar mais rapidamente as partes irrelevantes do domínio --- especialmente em aplicações onde a resposta deve ser calculada com resolução elevada. Ao contrário de métodos baseados em diferenciação automática, a aritmética afim pode ser usada em princípio mesmo para funções não diferenciáveis, descontínuas, ou com detalhes em múltiplas escalas, adaptando-se automaticamente a essas situações. Esta propriedade pode torná-la interessante em problemas de otimização combinatória, como problemas de programação linear e não linear inteira.