Optimal and Automatic Transactional Web Service Composition with Dependency Graph and 0-1 Linear Programming

In this article, we propose a model based on 0-1 linear programming for automatically determining a transactional composite web service (CWS) from a service dependency graph that optimizes a QoS measure. The QoS measure used in this model can be either a classical weighted sum of QoS criteria or a minmax-type criterion (e.g. response time). The transactional properties are a set of rules that ensures a reliable execution of the resulting CWS. The proposed 0-1 linear program is solved using a standard solver (CPLEX). Our experiments show that this new exact model surpasses two main related approaches: an approximate one based on transactional requirements and an exact one, based on 0-1 linear programming (LP), but not dealing with transactional properties. In a large majority of the test sets used for our experiments, our model finds a better solution more rapidly than both related approaches and is able to guarantee its optimality. Moreover, our model is able to find the optimal solutions of big size test sets, as the ones proposed by the Web Service Challenge 2009.