Puli - A Problem-Specific OMT Solver

EasyChair Preprint 371

Abstract

In our previous papers, we investigated several aspects of applying Optimization Modulo Theories (OMT) solvers to Wireless Sensor Networks (WSNs). None of the solvers we used in our experiments scaled enough for WSNs of common size in practice. This is particularly true when investigating additional dependability and security constraints on WSNs of high density.

In this paper, we propose an idea of speeding up the OMT solving process by taking into consideration some resources in the systems and by applying regression analysis on those resource values. For instance, in WSNs, the electrical charge in the batteries of sensor nodes can be considered to be a resource that is being consumed as approaching the maximal lifetime of the network. Another example is the knapsack problem where the remaining capacity of the knapsack can be used as such a resource. We show how to integrate this idea in search algorithms in the OMT framework and introduce a new OMT solver called Puli. We present experiments with Puli on WSN and knapsack benchmarks, which show remarkable improvements in the number of solved instances as well as computation time compared to existing solvers. Furthermore, we show that further significant improvement can be realized on so-called monotonous problems, such as WSN optimization, for which Puli can generate more precise assertions. We present Puli as a work-in-progress prototype that we are planning to upgrade to an official release soon, which we want to make publicly available.

Keyphrases: Knapsack, OMT, SMT, WSN, Wireless Sensor Network

@booklet{EasyChair:371,
  author    = {Gergely Kovásznai and Csaba Biró and Balázs Erdélyi},
  title     = {Puli - A Problem-Specific OMT Solver},
  doi       = {10.29007/96p4},
  howpublished = {EasyChair Preprint 371},
  year      = {EasyChair, 2018}}