Otimização de sistemas intervalares não lineares acíclicos

Abstract

Resumo: Intervalos permitem uma representação aproximada de números reais, com a qual podemos modelar matematicamente problemas do mundo real de uma forma menos restritiva que a modelagem sobre restrições reais. Assim, podemos definir problemas intervalares de decisão e otimização que são relaxamentos da Programação Não Linear usual. Recentemente, técnicas utilizadas em algoritmos para o problema da Satisfatibilidade Booleana foram aplicadas na solução de problemas intervalares de decisão, utilizando a álgebra intervalar para refinar intervalos e obter soluções que satisfaçam um conjunto de restrições sob uma precisão preestabelecida. Embora essa abordagem não resolva problemas de otimização, ela apresenta um método para extrair uma solução real de uma solução intervalar, se o problema apresentar determinadas características. Neste trabalho, estendemos esse método, definindo uma classe de problemas para os quais é possível a extração de uma solução real mesmo sem a garantia de todas as condições exigidas pelos resolvedores anteriores. Além disso, mostramos que o método estendido pode ser utilizado para resolver algumas classes de problemas de otimização.

Abstract: Intervals allow an approximate representation of real numbers. With them, one can model real word problems in a less restrictive way than using constraints over real numbers. Thus, one can define problems of decision and optimization over intervals that are relaxation of the usual Nonlinear Programming. Recently, techniques that are used to solve the Boolean Satisfiability problem have been implemented on algorithms for interval decision problems, applying interval arithmetics to refine intervals and obtain a solution that satisfy the set of constraints under a precision error. Although this approach does not apply for optimization problems, it introduces a method of extracting a real solution of an interval one, if the problem has some specific features. In this work we extend this method and define a class of problems for which it is possible to extract a real solution even without ensuring all conditions required by the preview solvers. Furthermore, we show that the extended method can also be applied to some set of optimization problems.