Information Technology Reference
In-Depth Information
The revision of a constraint cannot generate new conflicts and we have the
following theorem.
Theorem 4.
If the constraints corresponding to a vertex cover of the conflict
graph of a flooding problem are corrected, then the consistency of the problem is
restored.
4
Revision Methods
We propose in the following, two revision mothods : the
partial revision
and the
global revision
which offer a good compromise between minimality and eciency
of revision.
4.1
Partial Revision
The
partial revision
method consists first in identifying the list
L
of all the
conflicts (
i, j, d
) and in sorting it according to the ascending order of the distances
d
. In the second phase, it takes a bundle
L
formed of the
n
first conflicts of the list
L
, then computes a minimal vertex cover
C
m
of the conflict graph corresponding
to
L
. The constraints of
C
m
are revised and all the corresponding conflicts are
removed from
L
. The second phase is repeated until all the conflicts of
L
are
removed. The complexity of the
partial revision
algorithm is
O
(
n
2
2
2
n
)inthe
worst case (see [4] for details).
4.2
The Global Revision
The
global revision
method detects all the conflicts, then computes a ”good”
subset of constraints whose the correction restores the consistency. This con-
straint subset corresponds to a ”good” vertex cover of the conflict graph which
is computed by the
Good-Cover
procedure. The complexity of the
global revision
algorithm is
O
(
n
2
e
) ([4]).
5
Experimental Results
The revision algorithms presented in this paper are implemented in
C
and run on
a pentium 4, 2.4 MHz with 512 MB of RAM. They are both tested on the real-
world flooding problem in the Herault valley and on random flooding instances.
The real flooding problem contains 180 parcels and 630 constraints. Both
methods solve eciently the problem (in less than 1 second) and their perfor-
mances are comparable. We then experiment them on random instances of the
flooding problem.
Generation of random flooding problems is based on two parameters: the
number of variables
n
, and the constraint density
d
whichisdefinedby
d
=
number of constraints
n
(
n−
1)
. The thightness
t
of the constraints is represented by the
Search WWH ::
Custom Search