single propagator
Akbar
akbarhome at gmail.com
Wed Feb 14 15:52:03 CET 2007
This is not the question about mozart programming language but
question about constraint programming. I have to solve "building a
house" problem (http://www.mozart-oz.org/documentation/fdt/node47.html#section.scheduling.house)
with constraint programming method. I have to make the solver engine
(that means I can not use mozart) my self. First I give domain for
each variables that is 0 until 29 (the sum of tasks duration) minus
their duration. So the domain for task a is 0..22, task b is 0..26
and so on. Then I have this precedence constraint:
a + 7 <= b, b + 3 <= c, and so on.
I propagate the domain (make it smaller) using these constraints. For
example, using constraint a + 7 <= b, I can propagate domain a & b to
0..19 (domain a), 7..26 (domain b), and so on until the propagator is
stable. I get these smaller domains:
a => 0..10
b => 7..21
c => 10..24
d => 7..17
e => 15..27
f => 15..25
g => 15..28
h => 7..23
i => 16..26
j => 18..28
After this, reading the document from that url, I am confuse how to
make a single propagator. I don't understand this sentence:
"Thus, we will use a single propagator in the script providing the
same propagation as the quadratic number of reified constraints."
My situation for now is like this. That is the most restricted domains
that I can get. I define the capacity constraint one by one (yeah, I
am aware of it will increase quadratically in the number of tasks on a
resource). Using backtracking and branch and bound, I can solve the
problem. But it takes too long. 37 seconds (I can find the optimal
solution in 2 seconds but I need those 37 seconds to make sure it is
the optimal solution). I wonder how to make those domain more
restricted. The combination number is still high.
Thank you.
More information about the mozart-users
mailing list