SMT-based Verification Applied to Non-convex Optimization Problems

• Rodrigo Araújo UFAM
• Iury Bessa UFAM
• Lucas Carvalho Cordeiro University of Oxford / UFAM
• João Edgar Chaves Filho UFAM

Resumo

This paper presents a novel, complete, and flexible optimization algorithm, which relies on recursive executions that re-constrains a model-checking procedure based on Satisfiability Modulo Theories (SMT). This SMT-based optimization technique is able to optimize a wide range of functions, including non-linear and non-convex problems using fixed-point arithmetic. Although SMT-based optimization is not a new technique, this work is the pioneer in solving non-linear and non-convex problems based on SMT; previous applications are only able to solve integer and rational linear problems. The proposed SMT-based optimization algorithm is compared to other traditional optimization techniques. Experimental results show the efficiency and effectiveness of the proposed algorithm, which finds the optimal solution in all evaluated benchmarks, while traditional techniques are usually trapped by local minima.

Palavras-chave: Model checking, Genetic algorithms, Cost function, Embedded systems, Benchmark testing, satisfiability modulo theory (SMT), model checking, optimization, global minima, non-convex problems