27 Formal Analysis of Critical Infrastructures by Structural Identification Using Constraint Programming Paradigm 257 techniques to improve the performance and scalability of the approach. The following discussion provides some details about the basics of CSPs essential for the understanding of rest of the paper. A CSP can be defined as a 4-tuple <V,D,C,L> where; • V Dfv1;v2; : : : ;vng is a set of variables • DDfd1;d2; : : : ;dng is a set of domains for prospective variables • C Dfc1;c2; : : : ;cng is a set of constraints over the variables • L is a set of labels that maps constraints to the pair of variables and corresponding domains, formally; LW Ci !.vi ;di / Each variable vi can assume any value in the corresponding non empty domain di . The constraint ci 2 C is defined over a pair (vi , di ) through a label function li L. In the process of finding a satisfiable solution, different values are assigned to the variable (in set V) from domain set (D) through constraint propagation algorithms (also called filtering/contraction algorithms). The evaluation of the label (true/false) determines whether the corresponding assignments to variables for a given constraint lead to a satisfiable solution or not. While assigning values to different variable (through “systematic search process”) consistency algorithms [13] take into account whether any violation of constraints has occurred during any assignment. If it is determined that there is constraint violation, backtracking is performed to find a new satisfiable assignment. This whole process is called constraint propagation [13]. The paradigm for solving CSPs through integration of Systemic Search and Arc Consistency techniques is called Constraint Programming (CP) [10–12]. Therefore, constraint programming is a domain in which the relationships among variables are defined in the form of constraints. It differs from conventional imperative programming since, rather than defining the flow of the program in sequential steps, it describes the criteria which all solutions must adhere. A sub-domain of constraint programming that deals with variables over the set of reals and integrates interval arithmetic with conventional constraint programming is called Interval Constraint Programming (ICP). Interval arithmetic, or interval based computation, is a method that has been an area of interest for mathematicians since early 1930s as a means of placing bounds on round off errors in mathematical computations and measurement errors in experimentation [14–16]. The notion of interval arithmetic combined with constraint programming can be very useful. In interval arithmetic, variable functions, and relations among them (constraints) are defined over intervals rather than exact values. Therefore, rather than defining the exact value of a variable/constant it is defined over an interval, assuming that it may take any value within that interval. The Cartesian product of intervals (Interval Vectors) generates boxes (cf. Eq. 27.5), which can be contracted according to given set of constraints using the concepts from contractor programming [17]. Formally, a variable “X” defined over an interval and the realization of boxes (cf. Fig. 27.1) can be explained as follows: X W Œa;b !fX 2Rja X bg (27.4) ŒX DŒx1 Œx2 Œx3 : : : Œxn (27.5) Fig. 27.1 Realization of box ŒX DŒx1 Œx2 and its contraction [ ] [x2] [x1] x1 x2 ] [ System à I X+ :Upper bound X− :Lower bound C([X]) [X] Rn
RkJQdWJsaXNoZXIy MTMzNzEzMQ==