Database Reference
In-Depth Information
into smaller, manageable blocks (CSPs), that can be solved independently (also,
possibly, concurrently), while providing the exact same solution as that of the orig-
inal CSP. Due to the exponential nature of solving the CSP, such a decomposition
strategy, if successful, can substantially improve the runtime that is required by the
integer programming solver to solve the CSP, and thus significantly ameliorate the
total time of the hiding algorithm.
The basic idea behind the proposed decomposition strategy relies on the follow-
ing properties of the formulated CSP:
Type of optimization criterion The objective function of the CSP requires the
minimization of the sum of non-negative values. Thus, it holds that
i=1
x
i
) = min(
b
1
b
2
å
i=b
1
+1
b
N
å
i=b
n
+1
N
i=1
x
i
)+min(
min(
x
i
)+: : :+min(
x
i
)
, where b
1
< b
2
< : : : < b
n
are integers in (1; N) defining splitting points in [1; N]
2
.
Type of constraints/variables Based on the problem at hand there may exist sets
of variables x
i
and their related constraints c
j
, which are independent from one
another. As an example, if c
1
: x
1
+ x
2
1 and c
2
: x
3
+ x
4
+ x
5
2 are two
constraints of the CSP, then these constraints can be solved independently since
they involve different x
i
variables and thus do not interfere with one another.
To identify if a given CSP is decomposable, the methodology that is proposed
by Menon, et al. [47] involves (i) the construction of a constraints-by-transactions
matrix for the problem at hand, and (ii) the examination of the structure of this
matrix to determine if any rearrangement of its rows and/or columns leads to the
identification of independent blocks. A block is called independent if it involves a set
of constraints (equivalently rows) and a set of transactions (equivalently columns)
that do not participate to any other block.
An example of a constraints-by-transactions matrix is presented in
Table 13.1.
As one can observe from the structure of this matrix, matrix M is decomposable
since the rearrangement of its rows and columns leads to the appearance of two
independent blocks, denoted by singly and doubly underlining the corresponding
elements, respectively. As a result of this structure, the original CSP that involved
constraints c
1
: : : c
4
and transactions T
1
: : : T
7
can be decomposed into two smaller
CSPs, one having constraints c
1
; c
3
and transactions T
3
; T
6
; T
7
, and the other having
2
One can easily notice that the same property holds in the case of maximizing a sum of variables
x
i
that can attain non-negative values, i.e. it holds that
i=1
x
i
) = max(
b
1
N
b
2
å
i=b
1
+1
b
N
å
i=b
n
+1
i=1
x
i
)+max(
max(
x
i
)+: : :+max(
x
i
)
, where b
1
< b
2
< : : : < b
n
are integers in (1; N) defining splitting points in [1; N]. This interesting
property is also discussed in Chapter 17, since it plays a key role in the parallelization process of
exact knowledge hiding algorithms.
