Information Technology Reference
In-Depth Information
sea level) in the flooded parcels. Two kinds of information are available:
(i)
The
estimates of the water height in each parcel.
(ii)
The observations on hydraulic
relations between some adjacent parcels.
The flooding problem is represented by the linear constraint network
N
=
(
X, C
)where
X
is a set of continuous variables,
X
i
corresponding to the water
height in parcel
i
.
C
is the set of constraints representing both estimates on
water heights and the hydraulic relations. The constraints are defined as follows:
Estimates on water heights
: Each parcel
i
is associated with the constraints
l
i
≤ X
i
− X
0
and
X
i
− X
0
≤ u
i
,(
X
0
represents the sea height,
X
0
=0).The
scalar
l
i
and
u
i
are respectively the lower and the upper bounds of the interval
delimiting the water height in the parcel
i
.
Hydraulic relations
: An observed flow from the parcel
i
to the parcel
j
is ex-
pressed by the constraint
X
j
0. A hydraulic balance between parcels
i
and
j
is represented by the constraints:
X
j
− X
i
≤
-
X
i
≤
0
.
We associate to the linear constraint network
N
=(
X, C
) a directed edge-
weighted graph,
G
d
=(
X, E
d
), called the
distance graph
.
X
is the set of vertices
corresponding to the variables of the network
N
,and
E
d
is the set of arcs repre-
senting the set of constraints
C
. Each constraint
X
j
−X
i
≤ a
ij
of
C
is represented
by the arc
i → j
, which is weighted by
a
ij
.Inthesequel,
n
is the number of the
vertices of the distance graph
G
d
and
e
is the number of its arcs.
Each of the two considered sources of information is consistent separately,
but conflicts appear when both sources are merged. A conflict is detected when a
flow is observed from the parcel
i
to the parcel
j
while the estimated water height
in
i
is strictly less than the estimated water height in
j
. Since the observations
on hydraulic relations are considered more reliable than the estimates on water
heights, these estimates are
revised
to restore the consistency.
0and
X
i
− X
j
≤
3
Revision
The revision of a linear constraint network consists in the detection of all the con-
flicts in the network, then the identification of a subset of constraints whose the
correction restores the consistency, and finally the correction of such constraints.
3.1
Detection of Conflicts
We present a method which detects the conflicts of a linear constraint network.
This method is based on the following theorem.
Theorem 1.
A linear constraint network is consistent if and only if its corre-
sponding distance graph does not contain elementary negative circuits.
Theorem 1 states that the removal of all the elementary negative circuits in
the distance graph, restores the consistency of its corresponding linear constraint
network. To detect the (elementary) negative circuits in the distance graph of a
flooding problem, we use the result of the following proposition.
Search WWH ::
Custom Search