Hybrid business process modeling for the optimization of outcome data

Hybrid business process modeling for the optimization of outcome data Luisa Parody∗, María Teresa Gómez-López, Rafael M. Gasca Department of Languages and Computer Systems, University of Seville, Spain Keywords: Hybrid model Business process Constraint programming Data optimization abstract Context: Declarative business processes are commonly used to describe permitted and prohibited actions in a business process. However, most current proposals of declarative languages fail in three aspects: (1) they tend to be oriented only towards the execution order of the activities; (2) the optimization is oriented only towards the minimization of the execution time or the resources used in the business process; and (3) there is an absence of capacity of execution of declarative models in commercial Business Process Management Systems. Objective: This contribution aims at taking into account these three aspects, by means of: (1) the formalization of a hybrid model oriented towards obtaining the outcome data optimization by combining a data-oriented declarative specification and a control-flow-oriented imperative specification; and (2) the automatic creation from this hybrid model to an imperative model that is executable in a standard Business Process Management System. Method: An approach, based on the definition of a hybrid business process, which uses a constraint programming paradigm, is presented. This approach enables the optimized outcome data to be obtained at runtime for the various instances. Results: A language capable of defining a hybrid model is provided, and applied to a case study. Likewise, the automatic creation of an executable constraint satisfaction problem is addressed, whose resolution allows us to attain the optimized outcome data. A brief computational study is also shown. Conclusion: A hybrid business process is defined for the specification of the relationships between declarative data and control-flow imperative components of a business process. In addition, the way in which this hybrid model automatically creates an entirely imperative model at design time is also defined. The resulting imperative model, executable in any commercial Business Process Management System, can obtain, at execution time, the optimized outcome data of the process. 1. Introduction A business process, henceforth referred to as BP, consists of a set of activities that are executed in coordination within an organizational and technical environment. These activities jointly attain a business goal [73]. Several languages propose an imperative representation of business processes. An imperative specification allows business ex-perts to describe an explicit order of execution between activities, and to transform the process into an executable model [1]. Therefore, an imperative description defines exactly how the activities have to be performed, and how the data-flow should be handled (for exam-ple, that activities A, B, and C are executed sequentially, or activities D and E are executed in parallel). However, the knowledge about the systems can sometimes be described by means of the things that are permitted or prohibited. Declarative descriptions enable specification of what has to be done, instead of how it has to be done (for example, activity A cannot be executed before activity B ends). Although imperative models are significantly more understandable than declarative models [14,15,54], declarative specifications can complement an imperative model when an imperative description cannot be performed. This is the reason why se veral authors have proposed languages for the definition of BPs as declarative models [33,43,51,60,63]. In addition, this modeling can be used when the BP cannot always be defined prior to execution time. Indeed, imperative models should be completely known and specified at design time, since they explicitly represent all the allowed sequences of activities. On the other hand, declarative models describe which orders of activities are permitted in an open world assumption (everything that is not explicitly specified is permitted); for example, if activity Ais executed, then activity Bhas to be executed afterwards, and, as long as this rule is satisfied, any behavior is allowed. In this way, at design time, the BP can remain “underspecified”. Unfortunately, there remain three main aspects of these declarative languages that need major improvement: (i) the capacity of the data-oriented description; (ii) the management of the data that optimizes the outcome data of each instance at runtime; and (iii) the necessity to make the declarative models executable and integrate them into a Business Process Management System. Each of these aspects is detailed below: (i) Data-oriented in declarative models: There is a significant number of papers that detect the necessity to include the data relationships description into the BP model. Although certain imperative languages, such as BPMN 2.0 [48], have included components to describe the data exchange during the execution of the process, new extensions have been proposed because the standard has insufficient descriptive capacity, such as in [23,41,42]. The role of data in declarative languages has been oriented to describe how the values of the data at runtime can affect to the activities execution order [4,32,36]. In this paper, the objective at runtime is to ascertain the values of the data to optimize the product obtained from the BP. (ii) Outcome optimization: Since the declarative models provide an underspecified definition of business process requirements at design time, the activities can be executed in different orders at runtime, but still in accordance with these requirements. Due to this fact, declarative models are typically joined to optimization problems. In general, this optimization is oriented towards minimizing the execution time, or reducing the resources used in the BP [26], but not to the optimization of the outcome data of each instance. One of the definitions of BP is “a series of steps designed to produce a product or service” [58]. Therefore, the optimization of the process to obtain the product, or to obtain a better product, is the reason why a company becomes more competitive than others. Therefore, the objective of a company can be oriented towards decreasing the cost of development time, or obtaining the best product on the market in order to be more competitive. Our proposal is focused on this latter group, specifically, in the optimization of the outcome data by mean of supporting customers about the best input data for each instance. (iii) Executable declarative models: Declarative languages enable a description of the temporal order of the activities to be written, and the necessary resources to perform them. However, although several tools are available to execute declarative descriptions, none of them provides anything more than guidelines or recommendations about which activity should be executed at a specific point of an instance. Unfortunately, there are no Business Process Management Systems (BPMS) available for the execution of declarative models in the same way as there are for imperative models. For example, they do not support users in choosing the best input data for each instance, in order to optimize the outcome data of the process. Therefore, declarative description are not used in the daily work of companies. 1.1. Detailing a case study: trip planner In order to understand the weakness of the existing declarative proposals (see Section 5), we introduce an example related to a trip planner. Our proposal can be applied to any example where the objective of a BP is to obtain the data corresponding to the best product (outcome data of the process) based on the customer requirements. The difficulty is that each customer can have different requirements, and the same BP model needs to satisfy the necessities, being flexible in this aspect. The example pertains to a trip planner process, based on that presented in [49] and [50]. The process describes the activities for the booking of flights, reservation of a hotel room, and, if necessary, the renting of a car. In order to minimize the price, the customer can choose among different dates, or can change the airport by traveling to a nearby city with a rented car. For this process, the model is introduced, thereby making it possible to execute the activities in aparallel manner. The problem now is to determine the best combination of data input for the activities in order to minimize the total price. In order to create a workflow process where the activities are involved, the business process shown in Fig. 1 can be modeled with the standard Business Process Model and Notation (BPMN) [48].The process starts with (i) the travel reservation request; follows with (ii) the searching of flights, hotel rooms, and rental car that compose the cheapest travel package that fits customer preferences; (iii) the travel package is offered to the customer; and finally, (iv) the customer, depending on his/her preferences, either formalizes the proposed travel package or cancels it. The problem in this model lies in part (ii), where the search for each component of the trip is performed. This search is in accordance with the availability and the customer requirements: the place to visit, the possible dates, the price, etc. It is possible to combine the activities that represent the three providers (Hotel, Flight, and Car Rental Provider) into a single BP, where the activities are executed in parallel. The question becomes how to determine that the best trip is found (the business product obtained as data output), and which BP model minimizes a value determined by a function in accordance with the outcome data (the total price in this example). Unfortunately, the trip planner problem cannot be modeled using the languages found in the literature, since it is not possible to describe: (i) the unknown input values of the data of the activities; (ii) the objective function according to the data output of the activities; and (iii) how the input values in an activity can affect other activities. 1.2. Our proposal In order to solve the aforementioned limitations, the input data dependencies are dealt with by means of a data-oriented optimization problem. The proposal consists of two parts: (i) Formalization of a hybrid model to represent the outcome data optimization: The Data-Oriented OPTimization DEClarative language, called DOOPT-DEC, is introduced to formalize a model that includes the process requirements referring to the data description in a declarative way. This description can be included in an imperative model that represents the controlflow requirements. More specifically, these requirements are necessary when the input data of each activity is unknown at design time, and need to be described in a declarative way to be discovered for each instance at runtime. In this paper, a new point of view of declarative languages focused on data is presented. (ii) Creation of an imperative model from a declarative description: Imperative specification implies “saying how to do something”, whereas declarative specification supposes “saying what is required and letting the system determine how to achieve it”. The proposal in this paper is focused on building an imperative model which obtains the best combination of data from the activities so that the optimal outcome data is attained, while maintaining the capacities of the declarative description thanks to the use of Constraint Programming in a BPMS. The remainder of the paper is organized as follows: Section 2 introduces the proposed declarative language with data aspects for use in the hybrid model. The possible models that can be created are detailed in Section 3. In addition, Section 3 also explains how this hybrid model can be transformed into an imperative computable model, and how the optimization problem can be solved using the Constraint Programming paradigm. Section 4 includes a brief computational and statistical study of our proposal. Section 5 includes certain related 24hours Cancel Request Customer make Selection Notify Customer to Start Again Update Customer Record (Request Cancelled) Request Cancelled Request Credit Card Information from Customer 24 hours Receive Customer Flight, Hotel Room and Car Rental Reservation Request Package Flights, Hotel Rooms and Car Rental for Customer Review Pay and Book Booking Successfully Completed + Search Flights based on Customer Request Search Hotel Rooms based on Customer Request Evaluate Flights within Customer Criteria Evaluate Hotel Rooms within Customer Criteria Search Rental Car based on Customer Request Evaluate Rental Car within Customer Criteria (i) (ii) (iii) (iv) Travel Search Sub-Process + Present Flights, Hotel Rooms and Car Rental Alternatives to Customer Fig. 1. Example of trip planner [49]. ... PDI1,…,PDIn PDI PDO1,…,PDOm PDO A DI1,…,DIn DI DO1,…,DOm DO C1,…,Cn <<Pre>> C1,…,Cn <<Post>> B DI1,…,DIn DI DO1,…,DOm DO C1,…,Cn <<Pre>> C1,…,Cn <<Post>> C1,…,Cn ID C1,…,Cn ID f: v ADI ADO Fig. 2. Subprocess components. work and its comparison with our proposal. Finally, conclusions are drawn and future work is proposed in Section 6. 2. Formalization of the data-oriented optimization business process languages In this section, the model is formalized and a language with graphical notation, called DOOPT-DEC, is provided to facilitate the description of the data-oriented optimization declarative models. The purpose of the DOOPT-DEC language is to enrich the imperative model by adding the declarative description of the relationships between data. Therefore, the division of the formalization is aligned to the relation between the imperative part of the model (subprocess description) and the declarative specification (subprocess relationships), as shown in Fig. 2. Using this hybrid description, another model exclusively imperative is created by including a constraint programming task to determine at runtime the most appropriate data input to optimize the outcome of the process. In order to introduce the formalization of the data provided and combined (see Fig. 2), the different descriptions to include are divided into: (i) subprocess description, including the descriptions of the components associated with the activities of the imperative part, detailed in Section 2.1; and (ii) subprocess relationships, which is the declarative description of the relationships between the components through the data-flow ( DF), addressed in Section 2.2. 2.1. Subprocess description The subprocess description includes the components associated with the activities, gateways, and control-flow which are known and can be represented in an imperative way. Taking Aas the finite set of activities {A1,..., Ai,..., An} contained in a determined BP, the following definitions are introduced. Definition 2.1. ACTIVITIES_DATA_INPUT (ADI)a nd ACTIVITIES_DATA_OUTPUT (ADO) represent the sets containing, respectively, all the data input and data output involved in the execution of all the activities. Within the set ADI (ADO), containing all the input (output) variables, it is possible to identify the input (output) variables of each activity, defined as follows. Definition 2.2. DATA_INPUT(Ai)andDATA_OUTPUT(Ai)describe the set of data input and output of an activity Aiinvolved in the subprocess, respectively, so that ∀Ai,DATA_INPUT(Ai)⊆ADI,where ADI ⊂DF. And,∀Ai,DATA_OUTPUT(Ai)⊆ADO,where ADO ⊂DF. Since various activities can share the same data input (or output), it is also possible that: DATA_INPUT(Ai)∩DATA_INPUT(Aj)=∅,fori = j. And,DATA_OUTPUT(Ai)∩DATA_OUTPUT(Aj)=∅,fori = j. The unions of all the DATA_INPUT sets and all the DATA_OUTPUT sets of all the activities, constitute the sets ADI and ADO respectively, with non-repetitive elements. ADI ={DATA_INPUT(A1)∪...∪DATA_INPUT(An)} ADO ={DATA_OUTPUT(A1)∪...∪DATA_OUTPUT(An)} Likewise, the specific variables that are inputs or outputs of the overall subprocess can be distinguished. They represent the information that flows from the customer to the subprocess and vice versa: Definition 2.3. PROCESS_DATA_INPUT (PDI)is the set of input variables of the subprocess, which determines the information provided and defined by the customer. PDI is composed of a subset of variables of ADI. PDI ⊆ADI Definition 2.4. PROCESS_DATA_OUTPUT (PDO)is the set of output variables of the subprocess. PDO is composed of a subset of variables of ADO. 2.2. Subprocess relationships There exist different relationships between the data inputs and data outputs defined in the subprocess description. Those relationships are expressed as constraints, both at activity and at process level, giving rise to the subprocess relationships, with the following definitions: Definition 2.5. PRE(Ai) is the set of constraints that limits the specific values of the DATA_INPUT(Ai) that must be satisfied to execute activity Ai. Likewise, POST(Ai) is the set of constraints that limits the specific values of the DATA_OUTPUT(Ai) that must be satisfied after the execution of activity Ai. Definition 2.6. INPUT_CONSTRAINT (OUTPUT_CONSTRAINT)relates the values of variables of PDI (PDO) with variables of DATA_INPUT (DATA_OUTPUT) of each activity. These constraints limit the possible value that the DATA_INPUT (DATA_OUTPUT)can take according to the PDI (PDO) values in each instance, and the possible values between the input and output of the activities. Definition 2.7. OBJECTIVE_FUNCTION (OBJ_FUNC),is an optimization function defined in terms of the data output of the activities (ADO). The objective of this optimization function is either to maximize or to minimize some of the output data that represent the business product, which constitutes the outcome of the process. OBJ_FUNC :f(v⊆ADO)→value,where fis MAXor MIN The result of this optimization problem is a set of input values that satisfies the optimization function, the pre and post-conditions of the activities, and also satisfies the input and output constraints. The set of input values that optimizes the output is found at runtime. The role of the constraints is to determine the possible values that this input and output data can take. All the constraints (INPUT_CONSTRAINTS,OUTPUT_CONS−TRAINTS,PRE and POST) are always defined at design time by a business expert who is familiar with the problem, although they are solved for each instance at runtime. Among every possible tuples of solutions that satisfy the constraints, the outcome of the subprocess will be the one which optimizes the variable defined in the optimization function. 2.3. Grammar and graphical notation The formalization presented above, used as a data-oriented optimization process, includes: the data of the process, the data of the activities, the objective function, and the constraints. These constraints are defined by the following grammar, where Variable and Constant, can be defined in the Integer, Natural, Float, Dates, and String domains. On the other hand, Set is defined as a set of Constant values of a specific Variable. Constraint :=Atomic_Constraint BOOL_OP Constraint |Atomic_Constraint |‘¬’ Constraint |Variable SET_FUNCTION Set BOOL_OP :=‘∨’|’∧’|‘→’ SET_FUNCTION :=‘∈’|‘∈ ’ Atomic_Constraint :=function PREDICATE function function :=Variable FUNCTION_SYMBOL function |Variable |Constant PREDICATE :=‘=’|‘= ’|‘<’|‘≤’|‘>’|‘≥’ {For the String domain only ‘=’ and ‘ = ’ are allowed} FUNCTION_SYMBOL :=‘+’|‘−’|‘∗’|‘/’ {These operators are only applicable to Numerical variables} A graphical notation, called DOOPT-DEC (Data-Oriented OPTimization DEClarative language), is defined in order to include these components into a BP model easily. DOOPT-DEC enables an imperative description focused on the control-flow perspective, using BPMN, to be combined with a declarative description of the data perspective of the subprocess. The existing BPMN components are combined with the new data components Fig. 3. DOOPT-DEC Graphical Components. in order to support the specification of data-oriented optimization processes. More specifically, in order to define each activity, the definition and notation given by the standard BPMN are followed. This implies that the activities participating in the optimization could be of any of the types described by the BPMN (script, manual, service, ...), and could also include any of the markers (sub-process, loop, parallel,...). On the other hand, the data objects defined in the formalization (ADI,ADO,PDI,and PDO) also follow the definition and notation given by BPMN. The DOOPT-DEC notation is incremented only in terms of the information carried by the arrows, which now include the name of the type of input and output data (ADI/PDI,and ADO/PDO). Therefore, DOOPT-DEC introduces the new data components related to the constraints (pre- and post-conditions, input and output constraints, and the objective function), whose definitions were previously limited through the grammar. All these components of the model are graphically represented by the symbols shown in Fig. 3. 2.4. Specification applied to the trip planner In this section, the formalization is applied to the Travel Search subprocess presented in Section 1.1, in order to find the cheapest travel package that fits customer preferences. In the example, there are nine PDIs whose values are provided by the customer as input data: •departingFrom: city from where the customer departs. •setDepartingFrom: set of possible departure cities where the flight can be taken. •goingTo: destination city. •setGoingTo: the set of possible arrival cities for the flight, containing the destination city itself and/or cities from where the destination city can be reached by using a rental car. •earlyDepartDate and lateDepartDate: the earliest and last day when the customer prefers to depart, respectively. •earlyReturnDate and lateReturnDate: the earliest and last day when the customer prefers to return, respectively. •hotelPreferences: some preferences related to the hotel (single or double room, star-rated, etc.). Given a data input (that is, specific values for the aforementioned eight PDIs), each activity calculates the price of its sought product. The activities and their ADI are detailed below. •Flight Search Activity (AF) returns the price of flight for a tuple of values for the data input. Fig. 4 shows the components related to the Flight Search Activity represented with DOOPT-DEC. DATA_INPUT (AF)={departingFrom,goingTo,departDate, returnDate} DATA_OUTPUT (AF)={priceFlight, flightInformation}where f lightIn formation ={outwardArrivalDate,returnArrivalDate, seat, ...} Certain existing pre and post-conditions include: Fig. 4. Flight Search Activity specified with DOOPT-DEC. PRE (AF)={departDate ≥systemDate1∧returnDate ≥departDate ∧departingFrom = goingTo} POST (AF)={flightInformation = null →priceFlight >0} •Hotel Search Activity (AH) is used to determine the cost of booking a hotel room. DATA_INPUT(AH)={location, checkInDate, check- OutDate, preferences} DATA_OUTPUT (AH)={priceHotel, hotelInformation} Certain existing pre and post-conditions include: PRE (AH)={checkInDate ≥systemDate ∧checkInDate <checkOut- Date} POST (AH)={hotelInformation = null →priceHotel >0} •Car Rental Search Activities (ACR1and ACR2) are used to determine the price of renting a car. Two cars can be rented during the trip, one at the source (ACR1), and another at the destination (ACR2). Nevertheless, the price for renting both cars is represented by ACRx,wherexcan take the values 1 or 2, and depends on these entries: DATA_INPUT (ACRx)={departingFrom, goingTo, departDate, returnDate} DATA_OUTPUT (ACRx)={priceCarRx, carRxInformation} Certain existing pre and post-conditions include: PRE (ACRx)={departDate ≥systemDate ∧departDate <returnDate} POST (ACRx)={carRxInformation = null →priceCarRx>0} In this case, the outputs of the process (PDO)aretheoutputsofthe activities, which contain the information about the elements composing the trip, as well as the total price of the trip (price). Therefore, the customer only provides data to the subprocess: the set of dates/cities, and some preferences related to the hotel. Then, each search activity only uses the necessary data, as detailed in its specification, for the searching. On the one hand, the subprocess can have input data that is not used by some search activity: for example, the Flight Search Activity takes the possible dates and cities given by the customer to the subprocess, meanwhile, the Hotel Search Activity takes the possible dates, the destination city and the preferences. On the other hand, the subprocess can have input data that is not used in thesamewaybytheactivities:forexample,theinputdatarelatedto the departure date in the subprocess is a set of values, while is a single value in case of the Flight Search Activity. In both cases, the constraints between the input data of the subprocess and the activities are specified as INPUT_CONSTRAINTS at design time. In the same way, the subprocess returns different data with respect to those returned by the activities, and it is necessary to define, at design time, how these data are calculated and related with the output data of the activities. Therefore, the OUTPUT_CONSTRAINTS define these relationships between these output data of the activities and the data returned by the subprocess to the customer. Although in the experimentation evaluation all the constraints have been included, only the most representative constraints have been formulated in this section. Regarding the relationships between the data input and output that belong to the subprocess and the activities, the most representatives INPUT_CONSTRAINTS and OUTPUT_CONSTRAINTS are detailed below: 1The variable systemDate corresponds to the date and time zone in which the customer is located when requesting the search. •INPUT_CONSTRAINTS: −From the input data introduced by the customer, the possible values of the departure date (IC1) and return date (IC2) of the flights are obtained, satisfying the following constraints: (IC1) earlyDepartDate ≤AF.departDate ≤lateDepartDate (IC2) earlyReturnDate ≤AF.returnDate ≤lateReturnDate −The constraints that describe the possible values of the departure airport (IC3) and arrival airport (IC4) of the flight have to satisfy the possibilities of the input data proposed by the customer. (IC3) AF.departingFrom ∈setDepartingFrom (IC4) AF.goingTo ∈setGoingTo −The date of check-in into the hotel has to match with the arrival date of the outward flight (IC5). (IC5) AH.checkInDate =AF.outwardArrivalDate −The date of check-out has to match with the return date of the flight (IC6). (IC6) AH.checkOutDate =AF.returnDate −If the flight does not depart from the departure location (IC7), then the rental of a car (CR1) is necessary. (IC7) departingFrom = AF.departingFrom →{ACR1. departingFrom =departingFrom ∧ACR1.goingTo = AF.departingFrom ∧ACR1.departDate =AF.departDate ∧ ACR1.returnDate =AF.returnArrivalDate} −If the flight arrives at the destination city (IC8), then it is not necessary to rent a car. (IC8) goingTo =AF.goingTo →AF.goingTo =AH.location −If the flight does not arrive at the destination city (IC9), then the rental of a car (CR2) is necessary. (IC9) goingTo = AF.goingTo →{ACR2.departingFrom = AF.goingTo ∧ACR2.goingTo =goingTo ∧ACR2.departDate = AF.outwardArrivalDate ∧ACR2.returnDate =AF.returnDate} •OUTPUT_CONSTRAINTS: −The total price of the trip is the sum of all the prices returned by the activities, as presented in constraint (OC1). (OC1) totalPrice =priceF light +priceHotel +priceCarR1+ priceCarR2 In this example, the optimization involves the minimization of the total price of the trip, which is composed of the cost of buying flight tickets, staying in a hotel room, and renting cars for the departure and arrival cities. OBJ_FUNC :(MIN,totalPrice) All these components of the Travel Search subprocess are represented in Fig. 5. 3. Data-oriented optimization model approaches Previous sections present how to formalize the data optimization problem through the use of a special hybrid model. In addition, the aim of our proposal is also to reach a computable solution usable by the companies. It implies the possibility to deploy the hybrid model in a commercial BPMS, therefore it should be totally described using an imperative model. To build this imperative model, it is necessary to analyze the relation between the PDI,PDO,DI,DO,all the constraints and the optimization function. One of the aspects to analyze in deep is how the possible values for the ADO and PDO can be obtained for each possible ADI and PDI combination (with or without executing the activities). For the Travel Search subprocess, the objective function is to minimize the totalPrice, which, a priori, can only be known when the activities are executed at runtime and the values for the priceFlight, priceHotel, priceCarR1,andpriceCarR2are calculated. However, it would be also possible to know the output values of the activities using the input values and the pre and post-conditions. For example, if the Fig. 5. Example of trip planner described using DOOPT-DEC. a, b DI c DO White-Box Activity <<Pre>> c=a+b <<Post>> Fig. 6. White-box Model Example. priceHotel can be calculated by means of a function described in a post-condition (i.e. priceHotel =(checkOutDate −checkInDate)∗50), and the same occurs with the rest of the prices. In these cases, it is unnecessary to execute the activities to calculate the totalPrice. This implies the possibility of finding the best input data to optimize the outcome including every constraints in a COP (see Section 3.1), and solving it in a local manner. By avoiding the execution of the activities, the complexity and the way in which the problem is solved in an imperative model is reduced and simplified. If it is not possible, every possible ADI combination must be generated and used as input data of the activities to obtain the outputs. Therefore, regarding the knowledge about the behavior of the activities described by the pre and post-conditions, two different imperative models could be created: •White-box model: This is used when the subprocess is formed by white-box activities, which entails that the output values of the variables can be obtained in terms of the input values and the pre- and post-conditions, and it is unnecessary to execute an activity to ascertain its output, as shown in Fig. 6. In this case, the a, b DI c DO Black-Box Activity <<Pre>> c>0 <<Post>> Fig. 7. Black-box Model Example. optimization problem can be modeled and solved in a local manner, since the execution of the activities is unnecessary. •Black-box model: This is used when the problem is formed by black-box activities, which entails that, given a set of input values, the pre and post-conditions of the activities are insufficient to ascertain the output values, as shown in Fig. 7. In this case, it is necessary to execute the activities to obtain the specific values for the data output, since the model is unknown by the BP itself until the execution. However, the creation of all the possible combinations of values for the data input can be modeled and solved locally. Using these combinations of input data values in the execution of the activities, it is possible to obtain the output data used in the objective function that optimize the outcome of the process. The black-box approach is faced in [50], where an executable architecture is presented to solve the combination and execution of activities for the optimization of the objective function. Therefore, in this paper, we focus on solving only the white-box approach. 3.1. Background in constraint satisfaction problem A Constraint Satisfaction Problem (CSP) represents a reasoning framework consisting of variables, domains, and constraints. Formally, it is defined as a tuple X, D, C,whereX={x1,x2,..., xn} is a finite set of variables, D={d(x1), d(x2), ..., d(xn)} is a set of domains of the values of the variables, and C={C1,C2,...,Cm} is a set of constraints. Each constraint Ciis defined as a relation Ron a subset of variables V={xi,x j,...,xl}, called the constraint scope. The relation Rmay be represented as a subset of the Cartesian product {d(xi)× d(xj)×...×d(xl)}. A constraint Ci=(Vi,R i) simultaneously specifies the possible values of the variables in Vin order to satisfy R.LetVk= {xk1,xk2, ..., xkl}beasubsetofX,andanl-tuple(xk1,xk2, ..., xkl) from {d(xk1),d(xk2),...,d(xkl)}aninstantiation of the variables in Vk, then an instantiation is a solution if and only if, it satisfies all the constraints C. If an objective function O, is included in a CSP, it is called a Constraint Optimization Problem (COP), defined as a tuple X, D, C, O. A COP is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function implies maximizing or minimizing a variable that can represent a numerical combination of others by means of a function. The details of how the COP is created are explained below. In order to solve a COP, a combination of search and consistency techniques is commonly used [10]. The consistency techniques remove inconsistent values from the domains of the variables during or before the search. During the search, a propagation process is executed which analyzes the combination of values of variables where the constraints are satisfiable and where the values that cannot improve the best solution found until the moment are eliminated. Several local consistency and optimization techniques have been proposed as ways of improving the efficiency of search algorithms [71]. 3.2. How to obtain an imperative business process model from a white-box specification In order to create and solve an entirely imperative model using the definitions in Section 2, this contribution proposes to introduce in the model a COP with the constraints, data, and the objective function. The focus is placed on how a COP can be automatically built. Although the creation of the COP is performed only once at design time, the resolution of the COP occurs for each instance at runtime, to obtain the optimized outcome in function of the customer requirements. The use of Constraint Programming enables the combination of the variables to represent the model and ascertain those values of the output data that optimize the objective function. We propose that this COP can be set-up as a script activity (as shown in Fig. 8) within an executable model to manage the possible values of the input data variables of the activities. Firstly, it is necessary to highlight that the specification of the COP is very similar to the formalized DOOPT-DEC model, since both are declarative models that define the problem but not how to solve it. The advantage of using a COP is that it is not only a way to represent the problem, but it also provides a way to find a solution through a constraint solver (Choco Solver [7] in our case), and, at execution time, to find the concrete values that optimize the defined function. In order to design a model that involves all the variables and constraints that describe the data-oriented optimization process, the following COP structure is proposed: •X:DF,which includes the variables corresponding to each item of the data belonging to PDI,PDO,DATA_INPUT(A1), ..., DATA_INPUT(An), DATA_OUTPUT(A1), ...,DATA_OUTPUT(An). •D: Domain depending on the DF variables. The values of the domain depend on each instance of the BP. •C:PRE(A1)∧POST(A1)∧... ∧PRE(An)∧POST(An)∧ INPUT_CONSTRAINTS ∧OUTPUT_CONSTRAINTS ∧{Instantiation of the PDI with the values of the specific instance} •O:OBJECTIVE_FUNCTION The automatic creation of the COP from the subprocess description and subprocess relationships is carried out using a model-to-text transformation. In our case, Epsilon [16] has been used. Among other things, Epsilon provides a family of languages and tools for code generation and model-to-model transformation. The automatic creation consists of going over each element of the DOOPT-DEC language and transforming it into the corresponding text in the COP. With the aim of being independent of the technology used, DOOPT-DEC language is proposed, and then, to allow its execution, this language should be translated into the specific language used by any of the existing CSP solver. This translation is always straightforward and easy. Firstly, each element of the DOOPT-DEC language has been detailed in this paper, and the specific elements of the COP depends on the CSP solver chosen. Secondly, Epsilon provides a language, such as ETL [17], which allows us to define the correspondence between the elements of both languages as explained before. And finally, once a specific instance is defined in the DOOPT-DEC language, the automatic creation is carried out and the resulting COP is obtained. As mentioned previously, the created COP is included as a script activity [48] within an imperative model in order to evaluate the declarative data information at instantiation time. This COP provides the best input data for the activities that optimizes the outcome data of the subprocess. The basis of the automatic creation is to use the subprocess description and relationships in order to create a COP in a script activity connected to the subprocess. Then, this imperative model can be executed in any of the commercial BPMSs. Therefore, the configuration of this script activity depends on the mechanisms provided by the modeling tool of the BPMS used, and also on the BPMS engine capabilities. Regardless of the BPMS used, the COP can be solved using any of the existing COP solvers which connects the script activity with an external solver. Finally, the resulting business process, for any customer requirements, is capable of searching for the cheapest travel plan for a given set of dates and cities. In other words, the result after having solved the COP in our running example is the combination of dates and cities in which the customer should travel. This combination is the one with the minimal price, which meets the objective function. 3.3. Implementation of white-box model approach In our case, the BPMS employed to design and execute the BPs is Bonita Open SolutionTM [8] since it is an open-source application with a free distribution, and is commonly used in the private market. We have created a connector, which is the way in which Bonita Open SolutionTM links an activity with a service or application that executes a functionality. The new connector, called COP Script, enables the inclusion of a COP code into an activity and permits its resolution. COP Script has been implemented with the libraries provided by the COP solvers, Choco Solver [7] in our case. The business modeler can therefore use this connector to link the COP solver with the script activity. Fig. 9 shows an example of how a business modeler can include the generated COP into any script activity using the COP Script connector in Bonita Open SolutionTM. Finally, at runtime, when an instance reaches the script activity with the specific valuation of data, the COP is solved and the result is obtained2. 2The code of the resulting COP is available at http://www.lsi.us.es/quivir/index.php/ Main/WhiteBox.ThisCOPmustbeincludedasascripttaskinaBonitaOpenSolution TM project using the COP script connector, and the Choco solver Choco web-site. Fig. 8. White box transformation. Fig. 9. Choco Script Task Configuration in Bonita Open SolutionTM. 3.4. White-box model approach applied to trip planner A clear example of white-box approach in the trip planner example occurs when the cost of each part of the travel is included in different travel brochures, such as the offers available at travel agencies. In this case, since the prices are pre-established for specific date and conditions, the sub-process knows, without executing the activities, the data input and output relation for each part of the trip. For example, all flights from Seville to London, regardless of the date, costs 100 euros in May (AF.departDate ≥“2014 −05 −01 ∧AF.departDate ≤ “2014 −05 −31 −→ priceF light =100). Since the travel brochures are accessible and public, and cannot change for the dates published, then this information can be included in the COP. The COP generated from the model specified in Section 2.4 is shown in Table 1. 4. Empirical evaluation In this section, the experimental results corresponding to the performed evaluation are shown, the obtained results are discussed, and the limitations of our proposal are laid out. 4.1. Experimental design Since the generated COP is created depending on the declarative model, it is formatted only once, and at design time. The COP creation is performed linearly in accordance with the size of the model, that is, the number of variables and constraints. For this reason, it is not timeconsuming. The execution problem, and the bottleneck involved, is the resolution of the COP at runtime, where the critical point of our proposal lies. Since the optimization of the output has been mapped into a COP, the time spent during the optimization is linked to the complexity of solving this COP. This has been analyzed in great depth over recent decades [6], and depends on two parameters: the width of the graph and the order parameter. On the one hand, the width of the graph represents the relation among the constraints, where the tractability in CSPs is due to the structure of the constraint network, and where the tree-structured CSPs have polynomial complexity (linear with respect to the number of variables, and quadratic with respect to the cardinal of the domain of the variables). On the other hand, the order parameter, defined as the ratio of the number of forbidden tuples to Fig. 10. Number of possible combinations for each test case. Table 1 Constraint optimization problem for outcome data optimization. //Variables: earlyDepartDate: Date lastDepartDate: Date priceFlight: Integer ... //Pre and post-conditions AF:A F.departDate >SystemDate AF.departDate ≥“2014 −05 −01 ∧ AF.returnDate ≤“2014 −05 −31 →priceFlight =100 ... AH:A H.checkOutDate >AH.checkInDate AH.checkOutDate >AH.checkInDate ... // Input and Output Constraints AF.returnDate =AH.checkOutDate earlyDepartDate ≤AF.departDate AF.departDate ≤lastDepartDate ... //Optimization function: TotalPrice =priceF light +priceHotel +priceCarR1+priceCarR2 //Objective minimize(totalPrice) the total number of possible combinations, determines the partition of the problems space into under-constrained (several possible solutions), over-constrained (no possible solutions) and just-constrained (a set of a low number of possible solutions) problems. In the first two cases, the problems are scalable, but in just-constrained problems, a significant increase of solving cost could occur and the scalability would not be possible [29]. For these reasons, no general affirmation can be given concerning the efficiency in a generic way of our proposal, since our declarative specification permits any type and any number of numerical constraints; therefore, the evaluation time depends on the specific problem. Depending on the number of constraints associated to a COP, and the number of variables, the COP evaluation time remains variable. For this reason, and with the aim of performing the evaluation of our proposal, the resulting COP of the case study is executed over a set of 150 generated test cases. Each test case establishes a different number of values for the PDI,since the variables provided to the process determine the complexity of the resolution and the number of possible combinations. Likewise, the different values for each data in PDI generate, in turn, a number of combinations for PDI variables. This implies that each test case considerably increases the number of combinations, as shown in the table and plot in Fig. 10. Since some of the variables of the PDI are sets, depending on the different possibilities, the number of combinations increases whenever the sets grow. For example, if the “earlyDepartDate” is “23-12-2014” and “lateDepartDate” is “13-01-2015”, then there are 22 possible days to depart, and this implies different combinations with the rest of the variables, such as returnDate, departingFrom and goingTo. Since not all the combinations are possible solutions of the problem, Fig. 10 also indicates the number of possible solutions for each test. For example, it is possible that there is no available flight to go to any of the destination airports for a specific combination of dates. In that case, this combination is not a solution to the problem and should be discarded. 4.2. Experimental result The main purpose of the experimental evaluation is the determination of the computing time (seconds), the memory used (MB), and the quotients between the time and used memory needed to solve the COP of the example. In order to highlight the importance of the optimization, the measurements have been carried out over the COP. The study has been made with a branch and bound search (called optimized option) and without it (called all solution option) to analyze how the consistency techniques used in COPs can improve the evaluation time. The test cases were measured using a PC with an Intel Core i7- 2675QM CPU with a 2.2 GHz processor and 8.00 GB of RAM. On the one hand, Fig. 11 shows the memory used to solve the COP. It is possible to notice that, for the optimized option, the memory used almost remains steady regardless of the number of permutations. Meanwhile, the behavior of all solution option is exponential. On the other hand, the behavior of the execution time also fits an exponential model for all solution options (see Fig. 12). However, it is necessary to highlight that the evaluation time almost remains steady for the various tests, although the number of possible combinations for the PDI variables increases exponentially for the different tests presented. It is possible thanks to the use of propagation and consistence techniques in Constraint Programming. 4.3. Scope of applicability of our proposal In this paper, the focus is on data-oriented optimization processes, whose main goal is to obtain an outcome data optimization starting from the specification of the data and the constraints involved in the process. As a consequence of the declarative model described in the previous subsections, the scope of application of our proposal is limited by various characteristics: •The knowledge concerning the possible values of the variables managed during the business process instance. If the relation of the values of the input and output variables are unknown, then the resolution of the COP is insufficient to help the customer during the business execution to achieve an objective. Since the inference of