Database Reference
In-Depth Information
maximize(u
12
+u
22
+u
42
+u
52
)
subject to
u
12
+u
22
+u
42
+u
52
< 3
where fu
12
; u
22
; u
42
; u
52
g2f0; 1g
and
maximize(u
63
+u
64
+u
73
+u
74
+u
83
+u
84
)
<
:
u
63
u
64
+u
73
u
74
+u
83
u
84
< 3
u
63
+u
73
+u
83
3
u
64
+u
74
+u
84
1
subject to
where fu
63
; u
64
; u
73
; u
74
; u
83
; u
84
g2f0; 1g
Fig. 17.3: Equivalent CSPs for the provided example.
17.1.2 Decomposition of Large Independent Components
The structural decomposition of the original CSP allows one to break the original
large problem into numerous smaller subproblems that can be solved independently,
thus significantly reduce the runtime that is necessary to attain the overall hiding so-
lution. However, as it can be noticed, both (i) the number of subproblems, and (ii)
the size of each subproblem, are totally dependent on the underlying CSP and on
the structure of the constraints matrix. As an effect, there exist problem instances
which are not decomposable and other instances which experience a notable im-
balance in the size of the produced components. Thus, in what follows, we discuss
two methodologies from [25] which allow us to decompose large individual com-
ponents that are nonseparable through the structural decomposition approach. In
both methodologies, the goal is to minimize the number of variables that are shared
among the newly produced components, which are now dependent.
17.1.2.1 Decomposition Using Articulation Points
To decompose an independent component one needs to identify the least amount
of u
nm
variables which, when discarded from the various inequalities of this CSP,
produce a CSP that is structurally decomposable. The following strategy can be
employed to identify the u
nm
variables that will be discarded. First, an undirected
graph G(V;E) in which each vertex v 2V corresponds to a u
nm
variable and each
edge e 2E connects vertexes that participate to the same constraint, is generated.
Graph G can be constructed in linear time and provides an easy way to model the
network of constraints and involved variables in the input CSP. Since the input CSP
is not structurally decomposable, graph G will have to be connected.
