Re: how to refomulate this meta-constraint to direct consraint?

2012-10-12T07:12:46Z

This is the accepted answer.
This is the accepted answer.

Hello.

Indeed, it is not possible to use constraint endBeforeStart in a metaconstraint.

It seems to me that in some cases it could be modeled using noOverlap constraint with transition distance. It depends on what exactly do you want to achieve by this constraint. Could qtasks overlap? Is ytasks a typo? Could you describe a little bit more the scheduling problem?

Indeed, it is not possible to use constraint endBeforeStart in a metaconstraint.

It seems to me that in some cases it could be modeled using noOverlap constraint with transition distance. It depends on what exactly do you want to achieve by this constraint. Could qtasks overlap? Is ytasks a typo? Could you describe a little bit more the scheduling problem?

Thank you for your reponse. I am not good at English. But I'll try to make it clear.

First, There is no typo. ytasks and qtasks are different. They are related by this constraint.

They are all noOverlaped(I have implement this).

There is only one quay crane to unload containers from ship to some trucks.
qtasks is for the quay crane, ytasks for trucks. (Of course I also have

ytruckTasks[i][j]

)

I have built a model, this constraint is from the model. and I want to change this constraint to direct constraint for better performance.

hope you can understand me.

Thank you for your reponse. I am not good at English. But I'll try to make it clear.

First, There is no typo. ytasks and qtasks are different. They are related by this constraint.

They are all noOverlaped(I have implement this).

There is only one quay crane to unload containers from ship to some trucks.
qtasks is for the quay crane, ytasks for trucks. (Of course I also have
<pre class="jive-pre">
ytruckTasks[i][j]
</pre>
)

I have built a model, this constraint is from the model. and I want to change this constraint to direct constraint for better performance.

Thank you for your reponse. I am not good at English. But I'll try to make it clear.

First, There is no typo. ytasks and qtasks are different. They are related by this constraint.

They are all noOverlaped(I have implement this).

There is only one quay crane to unload containers from ship to some trucks.
qtasks is for the quay crane, ytasks for trucks. (Of course I also have
<pre class="jive-pre">
ytruckTasks[i][j]
</pre>
)

I have built a model, this constraint is from the model. and I want to change this constraint to direct constraint for better performance.

In this case, I think that it could be modeled using startOfNext function.
From what I understand, there is noOverlap on qtasks. In order to use startOfNext, there also have to be sequence variable qtasks:

dvar sequence quayCrane in all (i in 1..n) qtasks[i]; ... subject to
{ noOverlap(quayCrane); ... forall (i in 1..n) startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, ytasks[i], 1000000); ...

The expression startOfNext above returns start of the immediate successor on ytasks[i] on quayCrane. If ytasks[i] is the last task on quayCrane then the expression returns 1000000. You may need to adjust the value 1000000 to something what makes sense for your data. This model should improve the propagation especially if ytasks cause delays between qtasks.

Let me know if I didn't understand your problem right.

Best regards, Petr

In this case, I think that it could be modeled using startOfNext function.
From what I understand, there is noOverlap on qtasks. In order to use startOfNext, there also have to be sequence variable qtasks:
<pre class="jive-pre">
dvar sequence quayCrane in all (i in 1..n) qtasks[i]; ... subject to
{ noOverlap(quayCrane); ... forall (i in 1..n) startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, ytasks[i], 1000000); ...
</pre>
The expression startOfNext above returns start of the immediate successor on ytasks[i] on quayCrane. If ytasks[i] is the last task on quayCrane then the expression returns 1000000. You may need to adjust the value 1000000 to something what makes sense for your data. This model should improve the propagation especially if ytasks cause delays between qtasks.

Let me know if I didn't understand your problem right.

In this case, I think that it could be modeled using startOfNext function.
From what I understand, there is noOverlap on qtasks. In order to use startOfNext, there also have to be sequence variable qtasks:
<pre class="jive-pre">
dvar sequence quayCrane in all (i in 1..n) qtasks[i]; ... subject to
{ noOverlap(quayCrane); ... forall (i in 1..n) startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, ytasks[i], 1000000); ...
</pre>
The expression startOfNext above returns start of the immediate successor on ytasks[i] on quayCrane. If ytasks[i] is the last task on quayCrane then the expression returns 1000000. You may need to adjust the value 1000000 to something what makes sense for your data. This model should improve the propagation especially if ytasks cause delays between qtasks.

Let me know if I didn't understand your problem right.

It also applies to the explanation:
The expression startOfNext above returns start of the immediate successor of qtasks[i] on quayCrane. If qtasks[i] is the last task on quayCrane then the expression returns 1000000.

I'm sorry about that.

Petr

I just noticed I made a mistake and exchanged ytasks for qtasks inside startOfNext. It should be:
<pre class="jive-pre">
startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, qtasks[i], 1000000);
</pre>
It also applies to the explanation:
The expression startOfNext above returns start of the immediate successor of qtasks[i] on quayCrane. If qtasks[i] is the last task on quayCrane then the expression returns 1000000.

I just noticed I made a mistake and exchanged ytasks for qtasks inside startOfNext. It should be:
<pre class="jive-pre">
startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, qtasks[i], 1000000);
</pre>
It also applies to the explanation:
The expression startOfNext above returns start of the immediate successor of qtasks[i] on quayCrane. If qtasks[i] is the last task on quayCrane then the expression returns 1000000.

I just noticed I made a mistake and exchanged ytasks for qtasks inside startOfNext. It should be:
<pre class="jive-pre">
startOf(ytasks[i]) + 10 <= startOfNext(quayCrane, qtasks[i], 1000000);
</pre>
It also applies to the explanation:
The expression startOfNext above returns start of the immediate successor of qtasks[i] on quayCrane. If qtasks[i] is the last task on quayCrane then the expression returns 1000000.

Dear Petr, is it possibble to improve the following constraint?

forall(i, j in 1..n: i !=j)
{ (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) + delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j]) ;
}

Multiple quay cranes unload containers.
Here,
tasks[i]:Task of unloading container i.
l[i]: bay number of container i.
qcranediff[i][j] id defined by

// Crane number allocated to task i dvar
int qcrane[i in 1..n] in 1..q; dexpr
int qcranediff[i in 1..n][j in 1..n] = qcrane[j]-qcrane[i];

others are constant.

Dear Petr, is it possibble to improve the following constraint?
<pre class="jive-pre">
forall(i, j in 1..n: i !=j)
{ (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) + delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j]) ;
}
</pre>
Multiple quay cranes unload containers.
Here,
tasks[i]:Task of unloading container i.
l[i]: bay number of container i.
qcranediff[i][j] id defined by

<pre class="jive-pre">
// Crane number allocated to task i dvar
int qcrane[i in 1..n] in 1..q; dexpr
int qcranediff[i in 1..n][j in 1..n] = qcrane[j]-qcrane[i];
</pre>
others are constant.

Dear Petr, is it possibble to improve the following constraint?
<pre class="jive-pre">
forall(i, j in 1..n: i !=j)
{ (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) + delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j]) ;
}
</pre>
Multiple quay cranes unload containers.
Here,
tasks[i]:Task of unloading container i.
l[i]: bay number of container i.
qcranediff[i][j] id defined by

<pre class="jive-pre">
// Crane number allocated to task i dvar
int qcrane[i in 1..n] in 1..q; dexpr
int qcranediff[i in 1..n][j in 1..n] = qcrane[j]-qcrane[i];
</pre>
others are constant.

Thank you Petr.
Yes, qcrane[i] is a crane chosen for task i.

l[i] s t delta[i][j]

are all constants.
tasks[i] can overlap.

Thank you Petr.
Yes, qcrane[i] is a crane chosen for task i.
<pre class="jive-pre">
l[i] s t delta[i][j]
</pre>
are all constants.
tasks[i] can overlap.

And I have used optional interval variables and alternatives elsewhere in the model, for example

forall(i in 1..n) alternative(tasks[i], all(k in 1..q ) qcTasks[k][i]);
//quay assignment

For now, I just wonder if the flolowing constraint can be improved

forall(i, j in 1..n: i !=j)
{ (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) + delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j]) ;
}

And I have used optional interval variables and alternatives elsewhere in the model, for example
<pre class="jive-pre">
forall(i in 1..n) alternative(tasks[i], all(k in 1..q ) qcTasks[k][i]);
//quay assignment
</pre>

For now, I just wonder if the flolowing constraint can be improved
<pre class="jive-pre">
forall(i, j in 1..n: i !=j)
{ (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) + delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j]) ;
}
</pre>

And I have used optional interval variables and alternatives elsewhere in the model, for example
<pre class="jive-pre">
forall(i in 1..n) alternative(tasks[i], all(k in 1..q ) qcTasks[k][i]);
//quay assignment
</pre>

For now, I just wonder if the flolowing constraint can be improved
<pre class="jive-pre">
forall(i, j in 1..n: i !=j)
{ (qcranediff[i][j] > maxl(0, (l[j]-l[i]) div (s+1))) => endOf(tasks[j]) + delta[i][j]*t <= startOf(tasks[i]) || endOf(tasks[i]) + delta[i][j]*t <= startOf(tasks[j]) ;
}
</pre>

I'm afraid that there is no equivalent constraint in CP Optimizer. However I still do not understand what exactly the constraint means. Maybe the constraint can be replaced by something what is not equivalent but achieves the desired result.

Let's forget the math for a while. What the constraint means? From what I understand, if two cranes are working on two different tasks and they are "far enough" then there must be certain minimum delay between them. But why? Is there another resource(s) in play? Cannot the constraint be reformulated using state functions for cranes I mentioned in another post?