A Two Layer Mixed Integer Programming Model for Dynamic Composite Webservice Selection in Virtual Organizations Inspired by Layering as Optimization Decomposition

Abstract

The key motivation for virtual organizations (VOs) is the need for business agility against a highly volatile and globally competitive market. The agility includes the ability to dynamically and efficiently package and deliver highly customized services that maximally satisfy the utility of service consumer demands over the Internet. Dynamic webservice composition (DWSC) is an essential Information Communication Technology (ICT) enabler of this form of agility in VOs. However, dynamic webservice composition remains a multiple criteria decision making (MCDM) nondeterministic polynomial (NP) hard optimization problem despite more than 10 years of extensive research. This makes the applicability of DWSC to problems of industrial relevance currently limited. Mixed Integer Programming (MIP) is the most widely used technique in efficiently modelling the problem. There are two MIP models for the DWSC problem: a local planning strategy, herein L-MIP and a global planning strategy hereafter S-MIP. L-MIP is provably polynomial time and practically multiple times faster than S-MIP. However L-MIP lacks the ability to capture global inter workflow task webservice Quality of Service (QoS) constraints and generally is less optimal relative to S-MIP. It has been demonstrated that L-MIP generates composite webservices that are 20% to 30% worse in quality with respect to S-MIP. S-MIP on the other hand guarantees global optimality but is susceptible to exponential state space explosion, making the strategy limited to problems in which the number of service providers per business workflow task n is small. This thesis aimed to design a DWSC MIP global planning strategy that is more efficient than S-MIP. The second objective was to evaluate the performance of the proposed strategy versus S-MIP and L-MIP in terms of runtime efficiency and solution quality. The study proposed a two layer MIP model dubbed SLUM: Service Layered Utility Maximization. SLUM is inspired by the theory of Layering as Optimization Decomposition. Unlike all the existing DWSC MIP models that formulate and solve a single MIP model, in SLUM there are two hierarchically layered MIP models. One layer attempts to maximize the utility of service consumers and the other attempts to maximize the utility of virtual enterprise brokers. The DWSC is then solved sequentially. Efficiency gains from SLUM over S-MIP are hypothesized due to space reduction. The study used both theoretical and empirical methodologies to evaluate the performance of SLUM against S-MIP and L-MIP in terms of two metrics: running time and relative solution quality (RSQ). Our first main contribution is that we derive a theoretic running time model of SLUM and using L-Hospital’s Law, show that the theoretic speedup of SLUM with respect to S-MIP is given by the function (𝟐)𝒌 𝟏+ ρ ,𝑤ℎ𝑒𝑟𝑒 ρ=(Π(n−ε𝑖)𝑘1)/(𝒏𝒌), n is the number of service providers per business workflow task, k is the number of sequential workflow tasks, ε𝑖 is the number of service providers against the ith workflow task who fail to satisfy the webservice QoS requirements during the optimization process at the first layer. The study defines the parameter ρ as the Composite Service Phase Transition Rate. ρ lies on the interval [0,1]. The significance of the model is that at any one time instance, as ρ→0, implying very few service providers proceed for phase two optimization process, a virtual enterprise broker could expect relative speedup of up to (𝟐)𝒌, so that when k=2, SLUM is bound to be nearly 4 times faster than S-MIP. On the other hand when ρ→1, meaning that very few service providers get eliminated during phase one, the virtual enterprise broker could expect average speedups of up to (𝟐)𝒌−𝟏. Therefore at k=2, SLUM is expected to be nearly 2 times faster than S-MIP on average. Thus, we show that for other values of ρ, the expected speedup of SLUM with respect to S-MIP is bound to be on the interval [(𝟐)𝒌−𝟏,(𝟐)𝒌]. Our other major contributions were through experimentation. In the first set of experiments on the running time performance was investigated. Seven different setups were designed with each experiment having a unique ρ value. The value of k was fixed at 2. The following methods were used for data analysis: statistical regression analysis , scalability curves ( speed up vs number of service providers), differential calculus using L-Hospital’s Law, empirical relative complexity analysis, speedup vs ρ curves. Our second major contribution is that from the empirical results we show that the (𝟐)𝒌 𝟏+ ρ approximately holds in practice. This was verified using L-Hospital’s Rule and polynomial regression curve fitting. We found that the empirical expected speedup values at each of the 𝜌 values were all below but in close range with the theoretical values. For example at ρ =0.0296, an expected speedup of 3.6 was obtained against the theoretical 3.885. Further, the speedup vs ρ plot confirmed the inverse relation between speedup and ρ in (𝟐)𝒌 𝟏+ ρ . The empirical relative complexity coefficients β1 obtained for the various ρ values, were between 0.783 for the lowest ρ value and 0.96 for the highest ρ value. Moreover the β1 values were generally proportional to ρ . The deductions here are that for all 𝜌 SLUM is asymptotically faster than S-MIP. The second deduction is that asymptotic speedup of SLUM with respect to S-MIP is inversely proportional to ρ. This further verifies the model (𝟐)𝒌 𝟏+ ρ . On the other hand, the initial relative performance parameter β0 obtained via empirical relative complexity analysis generally showed that S-MIP is 1.3 times faster than SLUM initially. Using L-Hospital’s Law, exponential regression functions as well as the scalability curves, we found that at a constant ρ value, the speedup of SLUM with respect to S-MIP grows as the number of service providers grow larger but eventually reaches a limit. Further, that below ten service providers per task, S-MIP is generally faster than SLUM, beyond which SLUM is faster. The study also established L-MIP is several orders faster than both S-MIP and SLUM, and that the running time of L-MIP has a polynomial upperbound. On the other hand, the study also established that even though SLUM is on average and asymptotically faster than S-MIP, both of them have an empirical running time model bound between polynomial and exponential growth. Thus both models are superpolynomial, further confirming the NP hardness of the DWSC problem. On the other hand, our empirical results on RSQ, show that SLUM has an average RSQ of 93%, which is 7% less optimal compared to S-MIP, while L-MIP has an RSQ value of 87% which is 6% less optimal than SLUM. We conclude that if there is no need for global constraints at all, L-MIP is recommended over S-MIP and SLUM. However, if end user global constraints is a critical concern, optimality is a critical concern and the number of service providers per task is generally below 10, S-MIP should be used. SLUM is preferred over the two models if global constraints are critically needed and the number of service providers per task is above 10. Therefore virtual enterprise brokers could mix the three models in order to maximize their value and the value of their service consumers. Keywords: Dynamic Composite Webservice Selection, Mixed Integer Programming, Layering, Optimization, Decomposition, Virtual Organizations.