Databases Reference
In-Depth Information
Tabl e 5.
A set of ground clauses that can be aggregated
g
i
c w
g
1
x
1
∨ ¬y
1
∨ y
2
1.0
g
2
x
2
∨ ¬y
1
∨ y
2
1.0
g
3
¬x
3
∨ ¬y
1
∨ y
2
1.0
g
4
¬x
4
∨ ¬y
1
∨ y
3
1.0
g
5
i
c
w
x
1
∨
x
2
∨
¬x
3
∨
¬x
4
∨ ¬y
1
∨ y
3
1.0
x
5
∨
¬y
1
∨ y
2
1.0
¬y
1
0.5
x
5
∨
¬y
1
0.5
that aggregates sets of ground clauses so as to make the resulting ILP have (a)
fewer variables (b) fewer constraints and (c) its context-specific symmetries more
exposed to the ILP solver's symmetry detection heuristics.
We first demonstrate that evidence often introduces symmetries in the result-
ing sets of ground clauses and, therefore, at the level of ILP constraints. The
proposed approach aggregates ground clauses, resulting in smaller constraint ma-
trices and aiding symmetry detection algorithms of the ILP solvers. The solvers
apply heuristics to test whether the ILP's constraint matrix exhibits symmetries
in form of permutations of its columns and rows. For a comprehensive overview
of existing principles and algorithms for detecting and exploiting symmetries in
integer linear programs we refer the reader to [54,53,76,9]. We describe cutting
plane aggregation in two steps. First, we explain the aggregation of ground for-
mulas and, second, we describe the compilation of aggregated formulas to ILP
constraints.
Definition 2.
Let G
be a set of n weighted ground clauses and let c be a
ground clause. We say that G can be aggregated with respect to c if (a) all ground
clauses in G have the same weight and (b) for every g
i
∈
⊆G
G,
1
≤
i
≤|
G
|
, we have
that g
i
=
i
∨
c where
i
is a (unnegated or negated) literal for each i,
1
≤
i
≤|
G
|
.
Example 4.
Table 5 lists a set of 5 ground clauses. The set of clauses
{
g
1
,g
2
,g
3
}
can be aggregated with respect to
¬
y
1
∨
y
2
sincewecanwriteeachofthese
ground clauses as
i
∨¬
x
3
.
Before we describe the advantages of determining ground clauses that can be
aggregated and the corresponding ILP formulation encoding these sets of clauses,
we provide a typical instance of a Markov logic network resulting in a large
number of clauses that can be aggregated.
y
1
∨
y
2
with
1
:=
x
1
,
2
:=
x
2
,and
3
:=
¬
Example 5.
Let us consider the clause
cancer
(
x
)andletusas-
sume that there are 100 constants
C
1
, ..., C
100
for which we have evidence
smokes
(
C
i
)
,
1
¬
smokes
(
x
)
∨
100
,
let
y
i
be the ILP variable corre-
sponding to the ground atom
cancer
(
C
i
). The naive formulation would contain
100 constraints
y
i
≥
≤
i
≤
100. For 1
≤
i
≤
z
i
and the objective of the ILP with respect to these clauses
would be max 1
.
5
z
1
+
...
+1
.
5
z
100
. Instead, we can aggregate the ground clauses
cancer
(
C
i
)
,
1
≤
i
≤
100
,
for
c
=
false
and
i
=
cancer
(
C
i
)
,
1
≤
i
≤
100.
Let
G
be a set of ground clauses with weight
w
and let
c
be a ground clause.
Moreover, let us assume that
G
can be aggregated with respect to
c
,thatis,that
⊆G
