Databases Reference
In-Depth Information
Tabl e 4.
An example of the ILP formulation
weight ground clause
max
1
.
1
z
1
−
0
.
5
z
2
subject to
x
1
+(1
− x
2
)+
x
3
≥ z
1
(1
− x
1
)+
x
2
≤
2
· z
2
(1
− x
1
)+
x
2
≥
1
1
.
1
x
1
∨¬x
2
∨ x
3
−
0
.
5
¬x
1
∨ x
2
∞
x
1
∨ x
2
false or true. For every ground clause
g
∈G
with weight
w>
0
,w
∈
R
,
we add
a novel binary variable
z
g
and the following constraint to the ILP:
x
+
(1
−
x
)
≥
z
g
.
∈
L
+
(
g
)
∈
L
−
(
g
)
Please note that if any of the ground atoms
in the ground clause is set to false
(true) by the given evidence, we do not include it in the linear constraint.
For every
g
with weight
w
g
<
0
,w
∈
R
,
we add a novel binary variable
z
g
and the following constraint to the ILP:
x
+
∈L
−
(
g
)
L
+
(
g
)
L
−
(
g
)
−
x
)
≤
|
|
|
|
)
z
g
.
(1
(
+
∈L
+
(
g
)
For every
g
with weight
w
g
=
∞
, that is, a hard clause, we add the following
linear constraint to the ILP:
x
+
∈L
−
(
g
)
(1
−
x
)
≥
1
∈L
+
(
g
)
If a ground clause has zero weight we do not have to add the corresponding
constraint.
Finally, the objective of the ILP is:
max
g∈G
w
g
z
g
,
where we sum over weighted ground clauses only,
w
g
is the weight of
g
,and
z
g
∈{
is the binary variable previously associated with ground clause
g
.We
compute a MAP state by solving the ILP whose solution corresponds one-to-one
toaMAPstate
x
where
x
i
=
true
if the corresponding ILP variable is 1 and
x
i
=
false
otherwise.
For example, Table 4 depicts three clauses with
w>
0,
w<
0, and
w
=
∞
,
and the respective ILP formulations.
0
,
1
}
7.3 Constraint Aggregation
In this section we optimize the compilation of
sets
of weighted ground clauses
to
sets
of linear constraints. More concretely, we introduce a novel approach
