Or-tools: HELP: Split tasks in jobShop like problem

[gustavo-barros]

Hi,

I'm trying to solve a jobShop like problem for a factory floor operations scheduling. I'm using CPSolver.

The problem is that I have a factory Plant that works on a set of predefined work shifts. Each machine can have it's own work shift for each day of the calendar. So I configure the model to distribute the tasks only in the allowed time period.

The difficult part happens when there is a task length that exceeds the length of the available work shift time. The solver simply move the entire task to the next day shift or next allowed time space. So I was wondering, is there a way to make the solver split the task between two work shifts?

See the image below, the orange blocks are the allowed ones defined in the machine shift for that specific day. The purple ones are not allowed to be used because is the time that the factory shutdown. The blue block (30002/1) for example is a block that I wanted to be splitted, because it has no dependencies and there is a free space at it's left as shown in the image:

After this procedure, the result should be something like this image below, and this behaviour should be applied to each task that fits in this case and are longer than the available space:

[lperron]

Pre-compute which tasks can be splitted, create more than 1 intervals. (2
in your case), constraint the sum of durations to be the total duration.
Do you need something else ?

And as I said in another mail, please use the CP-SAT solver.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 26 avr. 2019 à 21:15, gustavo-barros [e-mail] a
écrit :

Hi,

I'm trying to solve a jobShop like problem for a factory floor operations
scheduling. I'm using CPSolver.

The problem is that I have a factory Plant that works on a set of
predefined work shifts. Each machine can have it's own work shift for each
day of the calendar. So I configure the model to distribute the operations
only in the allowed time period.

The difficult part happens when there is a operation length that exceeds
the length of the available work shift time. The solver simply move the
entire operation to the next day shift or next allowed time space. So I was
wondering, is there a way to make the solver split the operation between
two work shifts?

See the image below, the orange blocks are the allowed ones defined in the
machine shift for that specific day. The purple ones are not allowed to be
used because is the time that the factory shutdown. The blue block
(30002/1) for example is a block that I wanted to be splitted, because it
has no dependencies and there is a free space at it's left as shown in the
image:

[image: image]
https://user-images.githubusercontent.com/36746102/56830314-67c80900-683c-11e9-991a-eb3800b482b9.png

After this procedure, the result should be something like this image
below, and this behaviour should be applied to each operation that fits in
this case and are longer than the available space:

[image: image]
https://user-images.githubusercontent.com/36746102/56830402-9d6cf200-683c-11e9-9170-1df064f69175.png

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223, or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3PHNQUNJQTLACP4YYTPSNIDPANCNFSM4HIZUSHA
.

[EduSikora]

Pre-compute which tasks can be splitted, create more than 1 intervals. (2 ...

@lperron Does this mean that we will need to split every task by a single unit of time and group them using a constraint?

Ie: task that lasts 3 units of time, will turn into 3 tasks of 1 unit of time each??

What if we have 5000 tasks? Won’t the solver take a long time to solve?

I don’t know if I understood your answer correctly.. any simple example code would be much appreciated..

Thanks!!

_{Sent with GitHawk}

[lperron]

no, if a task duration is less than <= 2 x the smallest time span, split it
in 2. Force the duration of the first interval to be at least one. Make the
second optional.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le sam. 27 avr. 2019 à 15:22, EduSikora [e-mail] a écrit :

Pre-compute which tasks can be splitted, create more than 1 intervals. (2
...

@lperron https://github.com/lperron Does this mean that we will need to
split every task by a single unit of time and group the using a constraint?

Ie: task that lasts 3 units of time, will turn into 3 tasks of 1 unit of
time each??

What if we have 5000 tasks? Won’t the solver take a long time to solve?

I don’t know if I understood your answer correctly.. any simple example
code would be much appreciated..

Thanks!!

Sent with GitHawk http://githawk.com

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223#issuecomment-487285829,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KEVG2HTBJDODEB5PDPSRHRVANCNFSM4HIZUSHA
.

[gustavo-barros]

Hi Iperron,

Thank you for your reply.

I didn't understand your solution. The problem is that we can only know if a task should be splitted after it was distributed using the solver. We are trying to avoid running the solver, making adjustments and running it again. We need to be efficient.

If we pre-compute, we would not know wich one to split in advance. And even if we apply a splitting logic over all tasks at the beginning we would end up with thousands of tasks, at least the double of the total amount, right? Because most of then have length <= 2xSmallestTimeSpan. That's probably would be impractical because we want to tackle large problems.

How can we achieve this behaviour using the solver?

We are currently setting the disabled periods (purple) like this:

where:

and

key = startTime
deactivatedPeriod = duration.

Then we run this:

Where:

_DataProcessor.GetOdfsCount()
returns the jobs count

So the solver knows where not to put the tasks. There is another way that would help we achieve the mentioned behaviour? Or this would not change anything?

We need this functionallity to be able to use ORTools solver in our project.

[lperron]

In previous threads on the mailing list, I discussed the options for having
tasks spanning across breaks.
That is a task interrupted by a break would resume as soon as the breaks
stop ?

Would you be interested in that ?

Now, about the split green block.
You could force all blocks to belong to different break structure. For
instance impose a min distance between split tasks, or having one optional
tasks per work period and per task.

You also post-process the solution to merge the green blocks.

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 29 avr. 2019 à 15:50, gustavo-barros [e-mail] a
écrit :

Hi Iperron,

Thank you for your reply.

I didn't understand your solution. The problem is that we can only know if
a task should be splitted after it was distributed using the solver. We are
trying to avoid running the solver, making adjustments and running it
again. We need to be efficient.

If we pre-compute, we would not know wich one to split in advance. And
even if we apply a splitting logic over all tasks at the beginning we would
end up with thousands of tasks, at least the double of the total amount,
right? Because most of then have length <= 2xSmallestTimeSpan. That's
probably would be impractical because we want to tackle large problems.

How can we achieve this behaviour using the solver?

[image: image]
https://user-images.githubusercontent.com/36746102/56898389-4d25a800-6a67-11e9-8459-9db053c61581.png

We are currently setting the disabled periods (purple) like this:

[image: image]
https://user-images.githubusercontent.com/36746102/56899290-7c3d1900-6a69-11e9-9686-6993b9d5f8ce.png

where:
[image: image]
https://user-images.githubusercontent.com/36746102/56899416-c1f9e180-6a69-11e9-8dcc-590fedaa9808.png
and

key = startTime
deactivatedPeriod = duration.

Then we run this:
[image: image]
https://user-images.githubusercontent.com/36746102/56899985-2b2e2480-6a6b-11e9-9394-6b0b78987235.png

[image: image]
https://user-images.githubusercontent.com/36746102/56899944-0fc31980-6a6b-11e9-8550-d34ab3cf1910.png

Where:

_DataProcessor.GetOdfsCount()
returns the jobs count

So the solver knows where not to put the tasks. There is another way that
would help we achieve the mentioned behaviour? Or this would not change
anything?

We need this functionallity to be able to use ORTools solver in our
project.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223#issuecomment-487587340,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3NHFWYINSVCYH3A6I3PS34K3ANCNFSM4HIZUSHA
.

[gustavo-barros]

That is a task interrupted by a break would resume as soon as the breaks
stop ?

That's exactly what we need. Look at machine_0 in the image. See the purple (1 hour length) break interval after the first orange interval. That's a lunch break for example. So if a worker start a task in the first orange interval and leaves for lunch, it stops the task while lunch break and resume after the worker come back from the lunch time. The same happen when the task is longer than the day shift, it must resume in the next shift. That's the behaviour we want.

How can we do that?

[lperron]

Can you look at:

https://groups.google.com/forum/?hl=en#!searchin/or-tools-discuss/FlexibleJobShop$20with$20Machine$20Calendars%7Csort:date/or-tools-discuss/DA_4Pniwhn8/BH2vO5K1BgAJ

The last message in the thread is, IMO, the best option, It requires
pre-processing, but it should work.

Above, you have the second option with split intervals.

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 29 avr. 2019 à 17:19, gustavo-barros [e-mail] a
écrit :

That is a task interrupted by a break would resume as soon as the breaks
stop ?

That's exactly what we need. Look at machine_0 in the image. See the
purple (1 hour length) break interval after the first orange interval.
That's a lunch break for example. So if a worker start a task in the first
orange interval and leaves for lunch, it stops the task while lunch break
and resume after the worker come back from the lunch time. That's the
behaviour we want.

How can we do that?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223#issuecomment-487622611,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3IEY327OVAY6GCJ5JLPS4GZJANCNFSM4HIZUSHA
.

[gustavo-barros]

Hey Laurent,

I tried to implement that idea with no success. I don't know if I grasp the idea correctly. This was my try:

Doing this I reached a no solution answer.

I didn't understand how it could split the tasks when there is a deactivated shift. How those dx parameters are set? Is during the solver running process?

I'm hitting a dead end here :(

I understand that "start" is all possible start states, "duration" is the range that durations can vary and "end" is the range where it can end, starting from 0 to 20 (max) in your case example; Then you create those boolean dx's variables.

and here seems you are setting constraints to set the booleans variables to true if they are attended, for example: if a task starts at any number between and including [0..1] U [14..15], d4 will be activated to true as says this constraint

and then it will set the task duration to 4 because d4 is true as

Is there any sense in what I told, or I completely miss the point? I need your help to understand this.

[lperron]

at the minimum, intervals should be non-overlapping.
But this would not change the unsat part.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 29 avr. 2019 à 21:07, gustavo-barros [e-mail] a
écrit :

Hey Laurent,

I tried to implement that idea with no success. I don't know if I grasp
the idea correctly. This was my try:
[image: image]
https://user-images.githubusercontent.com/36746102/56917475-f4b7d000-6a91-11e9-87df-d4371348eb5a.png

Doing this I reached a no solution answer.

I didn't understand how it could split the tasks when there is a
deactivated shift. How those dx parameters are set? Is during the solver
running process?

I'm hitting a dead end here :(

I understand that "start" is all possible start states, "duration" is the
range that durations can vary and "end" is the range where it can end,
starting from 0 to 20 (max) in your case example; Then you create those
boolean dx's variables.

[image: image]
https://user-images.githubusercontent.com/36746102/56919958-5713cf00-6a98-11e9-8cc0-9632d8aaaba0.png

and here seems you are setting constraints to set the booleans variables
to true if they are attended, for example: if a task starts at any number
between and including [0..1] U [14..15], d4 will be activated to true as
says this constraint
[image: image]
https://user-images.githubusercontent.com/36746102/56919676-9e4d9000-6a97-11e9-92fe-81b2005d8660.png

and then it will set the task duration to 4 because d4 is true as
[image: image]
https://user-images.githubusercontent.com/36746102/56919802-e7054900-6a97-11e9-8e23-771585debadd.png

Is there any sense in what I told, or I completely miss the point? I need
your help to understand this.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223#issuecomment-487704993,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3MAOIPXUZFQJA5JOT3PS5BPJANCNFSM4HIZUSHA
.

[lperron]

Read the doc on NewEnumeratedIntVar, you need a flattened list on interval.

{1, 2, 3, 5, 7, 8, 9} is written as [1, 3, 5, 5, 7, 9]

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 29 avr. 2019 à 21:11, Laurent Perron [e-mail] a écrit :

at the minimum, intervals should be non-overlapping.
But this would not change the unsat part.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68
53 00

Le lun. 29 avr. 2019 à 21:07, gustavo-barros [e-mail] a
écrit :

Hey Laurent,

I tried to implement that idea with no success. I don't know if I grasp
the idea correctly. This was my try:
[image: image]
https://user-images.githubusercontent.com/36746102/56917475-f4b7d000-6a91-11e9-87df-d4371348eb5a.png

Doing this I reached a no solution answer.

I didn't understand how it could split the tasks when there is a
deactivated shift. How those dx parameters are set? Is during the solver
running process?

I'm hitting a dead end here :(

I understand that "start" is all possible start states, "duration" is the
range that durations can vary and "end" is the range where it can end,
starting from 0 to 20 (max) in your case example; Then you create those
boolean dx's variables.

[image: image]
https://user-images.githubusercontent.com/36746102/56919958-5713cf00-6a98-11e9-8cc0-9632d8aaaba0.png

and here seems you are setting constraints to set the booleans variables
to true if they are attended, for example: if a task starts at any number
between and including [0..1] U [14..15], d4 will be activated to true as
says this constraint
[image: image]
https://user-images.githubusercontent.com/36746102/56919676-9e4d9000-6a97-11e9-92fe-81b2005d8660.png

and then it will set the task duration to 4 because d4 is true as
[image: image]
https://user-images.githubusercontent.com/36746102/56919802-e7054900-6a97-11e9-8e23-771585debadd.png

Is there any sense in what I told, or I completely miss the point? I need
your help to understand this.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223#issuecomment-487704993,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3MAOIPXUZFQJA5JOT3PS5BPJANCNFSM4HIZUSHA
.

[KorpEduardoSikora]

Hi @lperron,

We're trying to understand and implement what you're saying, and at the same time we're learning about the OR Tools and its solver functionality.

Is there any tool (ie: skype) that we can chat in 'real-time'? Maybe we can share our screen too..
I sent you a message on what I believe it's your skype's account.

We really need this functionality or the Google OR Tools will not fit our project needs..

at the minimum, intervals should be non-overlapping. But this would not change the unsat part. Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53 00 Le lun. 29 avr. 2019 à 21:07, gustavo-barros [e-mail] a écrit :
…
Hey Laurent, I tried to implement that idea with no success. I don't know if I grasp the idea correctly. This was my try: [image: image] https://user-images.githubusercontent.com/36746102/56917475-f4b7d000-6a91-11e9-87df-d4371348eb5a.png Doing this I reached a no solution answer. I didn't understand how it could split the tasks when there is a deactivated shift. How those dx parameters are set? Is during the solver running process? I'm hitting a dead end here :( I understand that "start" is all possible start states, "duration" is the range that durations can vary and "end" is the range where it can end, starting from 0 to 20 (max) in your case example; Then you create those boolean dx's variables. [image: image] https://user-images.githubusercontent.com/36746102/56919958-5713cf00-6a98-11e9-8cc0-9632d8aaaba0.png and here seems you are setting constraints to set the booleans variables to true if they are attended, for example: if a task starts at any number between and including [0..1] U [14..15], d4 will be activated to true as says this constraint [image: image] https://user-images.githubusercontent.com/36746102/56919676-9e4d9000-6a97-11e9-92fe-81b2005d8660.png and then it will set the task duration to 4 because d4 is true as [image: image] https://user-images.githubusercontent.com/36746102/56919802-e7054900-6a97-11e9-8e23-771585debadd.png Is there any sense in what I told, or I completely miss the point? I need your help to understand this. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1223 (comment)>, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3MAOIPXUZFQJA5JOT3PS5BPJANCNFSM4HIZUSHA .

[lperron]

No, I have no time for chat, and I am on vacation.

Have you read:

https://github.com/google/or-tools/blob/master/ortools/sat/doc/integer_arithmetic.md

and more generally

https://github.com/google/or-tools/blob/master/ortools/sat/doc/README.md

(it seems github markdown rendering is down though).

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 29 avr. 2019 à 22:04, KorpEduardoSikora [e-mail]
a écrit :

Hi @lperron https://github.com/lperron,

We're trying to understand and implement what you're saying, and at the
same time we're learning about the OR Tools and its solver functionality.

Is there any tool (ie: skype) that we can chat in 'real-time'? Maybe we
can share our screen too..
I sent you a message on what I believe it's your skype's account.

We really need this functionality or the Google OR Tools will not fit our
project needs..

at the minimum, intervals should be non-overlapping. But this would not
change the unsat part. Laurent Perron | Operations Research |
[email protected] | (33) 1 42 68 53 00 Le lun. 29 avr. 2019 à 21:07,
gustavo-barros [email protected] a écrit :
… <#m_-161962866676888796_>
Hey Laurent, I tried to implement that idea with no success. I don't know
if I grasp the idea correctly. This was my try: [image: image]
https://user-images.githubusercontent.com/36746102/56917475-f4b7d000-6a91-11e9-87df-d4371348eb5a.png
Doing this I reached a no solution answer. I didn't understand how it could
split the tasks when there is a deactivated shift. How those dx parameters
are set? Is during the solver running process? I'm hitting a dead end here
:( I understand that "start" is all possible start states, "duration" is
the range that durations can vary and "end" is the range where it can end,
starting from 0 to 20 (max) in your case example; Then you create those
boolean dx's variables. [image: image]
https://user-images.githubusercontent.com/36746102/56919958-5713cf00-6a98-11e9-8cc0-9632d8aaaba0.png
and here seems you are setting constraints to set the booleans variables to
true if they are attended, for example: if a task starts at any number
between and including [0..1] U [14..15], d4 will be activated to true as
says this constraint [image: image]
https://user-images.githubusercontent.com/36746102/56919676-9e4d9000-6a97-11e9-92fe-81b2005d8660.png
and then it will set the task duration to 4 because d4 is true as [image:
image]
https://user-images.githubusercontent.com/36746102/56919802-e7054900-6a97-11e9-8e23-771585debadd.png
Is there any sense in what I told, or I completely miss the point? I need
your help to understand this. — You are receiving this because you were
mentioned. Reply to this email directly, view it on GitHub <#1223
(comment)
https://github.com/google/or-tools/issues/1223#issuecomment-487704993>,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3MAOIPXUZFQJA5JOT3PS5BPJANCNFSM4HIZUSHA
.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223#issuecomment-487723264,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3IO5SF6EZ2X4MF5PV3PS5IGFANCNFSM4HIZUSHA
.

[gustavo-barros]

Hi Laurent,

Sorry to bother you in your vacation. But this is very important to us, if you could help we will really appreciate it. I read all the examples you sent me, studied it and made several trials and errors here but something seems not to fit. There is something missing. Could you send me an example code related to our problem? So that it could enlight the path for us?

Our first valid shift is:
[8..12] U [13..18]

If we could simply simulate the case in wich a task starts at 11, stops at 12 and resume at 13 would be enough for us to continue.

[lperron]

I have pushed

https://github.com/google/or-tools/blob/master/ortools/sat/samples/scheduling_with_calendar_sample_sat.py

Which outputs

start=8 duration=3 across=0

start=9 duration=3 across=0

start=10 duration=3 across=0

start=11 duration=4 across=1

start=12 duration=4 across=1

start=14 duration=3 across=0

start=15 duration=3 across=0

It should be easy to adapt to other languages.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 30 avr. 2019 à 14:18, gustavo-barros [e-mail] a
écrit :

Hi Laurent,

Sorry to bother you in your vacation. But this is very important to us, if
you could help we will really appreciate it. I read all the examples you
sent me, studied it and made several trials and errors here but something
seems not to fit. There is something missing. Could you send me an example
code related to our problem? So that it could enlight the path for us?

Our first valid shift is:
[8..12] U [13..18]

If we could simply simulate the case in wich a task starts at 11, stops at
12 and resume at 13 would be enough for us to continue.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223#issuecomment-487929313,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3IINLVPLYH4VQSMNPLPTA2IDANCNFSM4HIZUSHA
.

[gustavo-barros]

Thank you Laurent,

Now I understand your logic. The problem is that my code have a different structure. It was based initially in this code:
https://github.com/google/or-tools/blob/stable/examples/dotnet/JobshopSat.cs

So I tried to apply your logic:

[MY ORIGINAL CODE]

where odf = job
and operation = task

[AFTER TRYING TO APPLY YOUR IDEA]

Of course my attempt is wrong, because my start is a IntVar not an NewEnumeratedIntVar. It found no solutions. But I think the answer is something like this.

When my code is working it writes to the console something like this:

Machine 5:
Task O1J5M5D6 starts at 8

If starts at 8; duration = 6

I'm trying to do, following your idea, when starts at 11 for example it answers me:

Machine 5:
Task O1J5M5D7 starts at 11

If starts at 11; duration = 7

Same thing, but with a different model data structure. How can I do this?

[lperron]

You can add start != break value if you want to the model.

You can also use AddLinearSumWithBounds() API (no need to create the tuple
.

I do not understand your question.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 30 avr. 2019 à 20:34, gustavo-barros [e-mail] a
écrit :

Thank you Laurent,

Now I understand your logic. The problem is that my code have a different
structure. It was based initially in this code:

https://github.com/google/or-tools/blob/stable/examples/dotnet/JobshopSat.cs

So I tried to apply your logic:

[MY ORIGINAL CODE]

where odf = job
and operation = task
[image: image]
https://user-images.githubusercontent.com/36746102/56982513-e16f3800-6b57-11e9-8a23-4dc76e7f7668.png

[AFTER TRYING TO APPLY YOUR IDEA]
[image: image]
https://user-images.githubusercontent.com/36746102/56982540-f1871780-6b57-11e9-9048-c87a667e7908.png

Of course my attempt is wrong, because my start is a IntVar not an
NewEnumeratedIntVar. It found no solutions. But I think the answer is
something like this.

When my code is working it writes to the console something like this:

Machine 5:
Task O1J5M5D6 starts at 8

If starts at 8; duration = 6

I'm trying to do, following your idea, when starts at 11 for example it
answers me:

Machine 5:
Task O1J5M5D7 starts at 11

If starts at 11; duration = 7

Same thing, but with a different model data structure. How can I do this?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223#issuecomment-488065009,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3I3NGZGPODNTPYVEE3PTCGKPANCNFSM4HIZUSHA
.

[gustavo-barros]

Hi Laurent,
I noticed that you added new features in the current version:

In the example you showed, the duration of the task could be 4 or 3 if is crossing or not. But how can I express thousands of tasks that can be expanded like that over the intervals?

For example, I have 4 different tasks with different durations. If they cross the interval they will be added up 1 unit of time, right. For example:

tasks durations:

• task_0: duration = 3
• task_1: duration = 4
• task_2: duration = 6
• task_3: duration = 7

if task_0 start at 12 AM it will end at 16 PM, hence duration = 4
if task_1 start at 12 AM it will end at 17 PM, hence duration = 5
if task_2 start at 11 AM it will end at 18 PM, hence duration = 7
if task_3 start at 10 AM it will end at 18 PM, hence duration = 8

So in summary:

• task_0: duration = {3 , 4}
• task_1: duration = {4, 5}
• task_2: duration = {6, 7}
• task_3: duration = {7, 8}

It is possible to define a range like this?

duration = model.NewIntVar(3, 8, 'duration')

meaning that duration ranges of 3 to 8? Or should I do something like this?

duration = model.NewIntVarFromDomain( cp_model.Domain.FromIntervals([(3, 4), (4, 5), (6, 7), (7, 8)]), 'duration')

Now, if I have different intervals durations? For example, imagine the lunch break is at 13 PM to 14 PM and after 18 PM is the shutdown break interval. So it will span from 18 PM to 8 AM. And if a task with duration 4 start at 17 PM it should span until 8 AM, so duration is 18. With these NewIntVarFromDomain, can I express this case also?

[gustavo-barros]

Hey Laurent,

See the red box, "operation.Duration" is the value I want to change depending on a BoolVar. How can I make that?

So I was trying to apply your example in my code in such a way I could change the operation.Duration value depending on the change of the "duration" variable, as the image show below:

In this case "operation.Duration" would be 4 if "across" is true.

Is this possible? How can I do that?

[gustavo-barros]

Something like this:

[lperron]

Exactly.
As a small optimization, you can write model.Add(duration == 3 + across);
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

*De : *gustavo-barros [e-mail]
*Date : *mer. 15 mai 2019 à 20:13
*À : *google/or-tools
*Cc : *Laurent Perron, Mention

Something like this:

[image: image]
https://user-images.githubusercontent.com/36746102/57798806-ed482600-7723-11e9-8c10-912abe031bda.png

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3N2U5ORPWH4XLKQDATPVRHENA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVPP3IA#issuecomment-492764576,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3OHNSJ3Y5QOOOWHMRTPVRHENANCNFSM4HIZUSHA
.

[gustavo-barros]

I'm just trying some random values while I'm testing, I end up with this scenario:

I added a property of type "IntVar" called "ComputedDuration" to the "operation" class. Added a NewIntVar called "operationDuration" and added it to a list of IntVar. My expectation is, duration will be calculed depending on cross inside the solver and stored in my "operationDuration" variable and then inside the list, that I hope I can access after the calculation. But I can't, I get something like this:

In that I just have the domain (possible values) but not the duration itself.
How can I retrieve this duration value after the calculation by the solver?

[lperron]

If there is a variable attached, you can ask the solver the value of that
variable in the solution.
You just need to store that variable.

Furthermore, when creating the duration variable, please try to restrict
the bounds of the variable as much as possible (prefer [3--8] instead of
[0--horizon]).
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

*De : *gustavo-barros [e-mail]
*Date : *mer. 15 mai 2019 à 21:51
*À : *google/or-tools
*Cc : *Laurent Perron, Mention

I'm just trying some random values while I'm testing, I end up with this

scenario:

[image: image]
https://user-images.githubusercontent.com/36746102/57804108-43bb6180-7730-11e9-9ca6-65bfd9fc1d09.png

I added a property of type "IntVar" called "ComputedDuration" to the
"operation" class. Added a NewIntVar called "operationDuration" and
added it to a list of IntVar. My expectation is, duration will be calculed
depending on cross inside the solver and stored in my
"operationDuration" variable and then inside the list, that I hope I
can access after the calculation. But I can't, I get something like this:

[image: image]
https://user-images.githubusercontent.com/36746102/57804369-e83da380-7730-11e9-83f7-9f9e5024c00b.png

[image: image]
https://user-images.githubusercontent.com/36746102/57804387-f1c70b80-7730-11e9-818a-992d09116dd0.png

In that I just have the domain (possible values) but not the duration
itself.
How can I retrieve this duration value after the calculation by the solver?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3MRO2RFKWGJEP5543DPVRSU5A5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVPYIKQ#issuecomment-492799018,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3OW5RSGUTMXJH5LF53PVRSU5ANCNFSM4HIZUSHA
.

[gustavo-barros]

Ok Laurent, here are the major changes:

So I tried to ask the solver for the value here:

is that right?
check the variable names changing. Where duration00 is the duration for the job 0 and task 0, and duration30 is the duration for the job 3 and task 0.

That

solver.Value(var)

should return me the duration value?

here is the scenario I'm trying to do, all tasks has lenght 3. So aproximately at 02:45-03:00 it should expand to +1 in lenght. Disregard the time scale, is not configured right.

[gustavo-barros]

I'm almost there, but something is still not right.

[lperron]

either

model.Add(Duration == data.duration + across)

or

model.Add(duration == data.Duration).OnlyEnforceIf(across.Not())
model.Add(duration == data.Duration + 1).OnlyEnforceIf(across)

Not a mix.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

*De : *gustavo-barros [e-mail]
*Date : *mer. 15 mai 2019 à 22:39
*À : *google/or-tools
*Cc : *Laurent Perron, Mention

Ok Laurent, here are the major changes:
>

[image: image]
https://user-images.githubusercontent.com/36746102/57807073-d19a4b00-7736-11e9-955f-9feeb24ee166.png

So I tried to ask the solver for the value here:
[image: image]
https://user-images.githubusercontent.com/36746102/57807184-09a18e00-7737-11e9-9419-bd09a26b74b0.png

is that right?
check the variable names changing. Where duration00 is the duration for
the job 0 and task 0, and duration30 is the duration for the job 3 and task
0.
[image: image]
https://user-images.githubusercontent.com/36746102/57807256-2fc72e00-7737-11e9-988a-546c564739ad.png
[image: image]
https://user-images.githubusercontent.com/36746102/57807310-4ec5c000-7737-11e9-83ec-e01daeddebde.png

That

solver.Value(var)

should return me the duration value?

here is the scenario I'm trying to do, all tasks has lenght 3. So
aproximately at 02:45-03:00 it should expand to +1 in lenght. Disregard the
time scale, is not configured right.

[image: image]
https://user-images.githubusercontent.com/36746102/57807733-22f70a00-7738-11e9-893c-ce051fcf0dc6.png
[image: image]
https://user-images.githubusercontent.com/36746102/57807762-3013f900-7738-11e9-9907-a22b7413d7f7.png

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3PB2DNBMGDTHNPLR63PVRYGXA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVP4EEQ#issuecomment-492814866,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3JEZJMFEC37W4YPVEDPVRYGXANCNFSM4HIZUSHA
.

[gustavo-barros]

Yes, I already fixed that. But it still returns 3 for all the data. For the machine_1 should be some 4's.

This give me a impression that maybe something related with the intervals?

[gustavo-barros]

I can provide more code if needed, any ideas?
Really need your help. Seems the durations values are always setted to 3, that's the same as the original data.Duration. For some reason seems it doesn't setting the across state. But I have no sure :(

[gustavo-barros]

Yes, made some tests here. Across state are not being activated

[lperron]

It was in the code I wrote. So debug your code.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

*De : *gustavo-barros [e-mail]
*Date : *mer. 15 mai 2019 à 23:54
*À : *google/or-tools
*Cc : *Laurent Perron, Mention

Yes, made some tests here. Cross state are not being activated
>

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3OTFYTH3WNVNTNJBVLPVSBCBA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVQBZKI#issuecomment-492838057,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KPD3MHOSH44MQU3J3PVSBCBANCNFSM4HIZUSHA
.

[gustavo-barros]

Ok. Can you explain for me how this two methods works or give me a direction where I can find reference about it?

Model.AddLinearExpressionInDomain()

Model.AddLinearConstraint()

I have sure it is something about the intervals that is not right, and then the "across" state is not becoming true.

[lperron]

A domain in a set of values build from values or integer intervals.

AddLinearConstraint(linear_expr, lb, ub) ==
AddLinearExpressionInDomain(linear_expr, new Domain(lb, ub))

The domain class is documented here:

https://github.com/google/or-tools/blob/master/ortools/util/sorted_interval_list.h#L57

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

*De : *gustavo-barros [e-mail]
*Date : *jeu. 16 mai 2019 à 13:56
*À : *google/or-tools
*Cc : *Laurent Perron, Mention

Ok. Can you explain for me how this two methods works or give me a

direction where I can find reference about it?

Model.AddLinearExpressionInDomain()

Model.AddLinearConstraint()

I have sure it is something about the intervals that is not right, and
then the "across" state is not becoming true.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3LYBPHYWKJRKLVW7FLPVVDWRA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVRSLMA#issuecomment-493036976,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3JOJZYPIQCMSSYWRODPVVDWRANCNFSM4HIZUSHA
.

[gustavo-barros]

this is the AddLinearConstraint() method that we are using?

https://github.com/google/or-tools/blob/v7.0/ortools/sat/pb_constraint.h#L150

[lperron]

No, this is an internal propagation code dedicated to pseudo-boolean
constraints (that is linear constraints with Boolean variables).
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

*De : *gustavo-barros [e-mail]
*Date : *jeu. 16 mai 2019 à 14:24
*À : *google/or-tools
*Cc : *Laurent Perron, Mention

this is the AddLinearConstraint() method that we are using?
>
>

https://github.com/google/or-tools/blob/v7.0/ortools/sat/pb_constraint.h#L150

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3K6S4RGCEQ7ILNAJWTPVVG7PA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVRUNEY#issuecomment-493045395,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3JGH22WJZ2GMXISQ73PVVG7PANCNFSM4HIZUSHA
.

[gustavo-barros]

Hey Laurent,
I was right about the domains, now it's working half the logic, thank you. I'm trying to adapt to my scenario, so I still have some doubts.

For example, I have this:

But I would like something like this:

Of course I wouldn't declare the same variable twice. I need this OneTask to receive each one depending on the bool variables.

I'll explain you why I need that. Each machine has different inactive intervals during a day. So I'll try to loop over a array of NewBoolVar for each interval and a array of Durations. Something like this in the case of durations:

I need this because if a task hit the first interval it expands 1x4 blocks (1 hour in four 15 minutes blocks), BUT if a task hit the second interval that goes from 18:00 to 08:00 next day. It should expand 14x4 blocks.
So how can I set my "OneTask" variable depending on my NewBoolVars ?

Here is the image of the first functional expansion:

[lperron]

Have you seen

https://github.com/google/or-tools/blob/f3fd201e68cf75b7720ff5c3cadc599a1d02b54b/examples/dotnet/GateSchedulingSat.cs#L92

?
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

*De : *gustavo-barros [e-mail]
*Date : *jeu. 16 mai 2019 à 20:03
*À : *google/or-tools
*Cc : *Laurent Perron, Mention

Hey Laurent,

I was right about the domains, now it's working half the logic, thank you.
I'm trying to adapt to my scenario, so I still have some doubts.

For example, I have this:
[image: image]
https://user-images.githubusercontent.com/36746102/57874880-f4386c80-77e7-11e9-8118-32f41d2d47ff.png

But I would like something like this:
[image: image]
https://user-images.githubusercontent.com/36746102/57874979-2c3faf80-77e8-11e9-9da7-843564c3f118.png
Of course I wouldn't declare the same variable twice. I need this OneTask
to receive each one depending on the bool variables.

I'll explain you why I need that. Each machine has different inactive
intervals during a day. So I'll try to loop over a array of NewBoolVar for
each interval and a array of Durations. Something like this in the case of
durations:
[image: image]
https://user-images.githubusercontent.com/36746102/57876375-8b52f380-77eb-11e9-86a9-d0e680bc6290.png

I need this because if a task hit the first interval it expands 1x4 blocks
(1 hour in four 15 minutes blocks), BUT if a task hit the second interval
that goes from 18:00 to 08:00 next day. It should expand 14x4 blocks.
So how can I set my "OneTask" variable depending on my NewBoolVars ?

Here is the image of the first functional expansion:
[image: image]
https://user-images.githubusercontent.com/36746102/57875784-17641b80-77ea-11e9-9b19-bc4ca21fde21.png

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3O5N5XR4DA6RCQIFS3PVWOVRA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVSTLTA#issuecomment-493172172,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3PFO4MRS3AW6UZ3R5TPVWOVRANCNFSM4HIZUSHA
.

[gustavo-barros]

There is a way to do set operations like, union, intersect, exclude using Domains? Would be very good if possible.

[gustavo-barros]

For example if we have:

var availableDomain = Domain.FromIntervals(new[]
                    {
                        new long[] {8, 12},
                        new long[] {13, 18},
                        new long[] {27, 31},
                        new long[] {32, 137}
                    });

                    var crossingDomain1 = Domain.FromIntervals(new[]
                    {
                        new long[] {11, 12}
                    });

                    var crossingDomain2 = Domain.FromIntervals(new[]
                    {
                        new long[] {16,17}
                    });

                    notCrossingDomain = availableDomain.Exclude(crossingDomain1);
                    notCrossingDomain.Exclude(crossingDomain2);

// SO WE HAVE AT END
                    notCrossingDomain =
                    {
                        {8, 10},
                        {13, 15},
                        {18, 27},
                        {32, 137}
                    }

Or something like that

[lperron]

It is possible in C++, I did not wrap all functions in C#.
I will do it for 7.2.

Here is the API in C++

https://github.com/google/or-tools/blob/f3fd201e68cf75b7720ff5c3cadc599a1d02b54b/ortools/util/sorted_interval_list.h#L65
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

*De : *gustavo-barros [e-mail]
*Date : *jeu. 16 mai 2019 à 21:56
*À : *google/or-tools
*Cc : *Laurent Perron, Mention

For example if we have:
>

var availableDomain = Domain.FromIntervals(new[]
{
new long[] {8, 12},
new long[] {13, 18},
new long[] {27, 31},
new long[] {32, 137}
});

                var crossingDomain1 = Domain.FromIntervals(new[]
                {
                    new long[] {11, 12}
                });

                var crossingDomain2 = Domain.FromIntervals(new[]
                {
                    new long[] {16,17}
                });

                notCrossingDomain = availableDomain.Exclude(crossingDomain1);
                notCrossingDomain.Exclude(crossingDomain2);

// SO WE HAVE AT END
notCrossingDomain =
{
{8, 10},
{13, 15},
{18, 27},
{32, 137}
}

Or something like that

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3IAV6OSKJGN6CU4MWDPVW36VA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVS4SIQ#issuecomment-493209890,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3PENMXUIGKA5GDFWBDPVW36VANCNFSM4HIZUSHA
.

[gustavo-barros]

Hey Laurent,
I'm almost done with this feature. But I still have some problems. I'm trying to write a sequencial code that simulates a loop with 2 iterations (can be more later, if it works). So I'm doing the things in double to attempt to set these durations variations through different intervals of different lenght ( in this case 2 different intervals). For each block I calculate the crossing and non-crossing domains because it depends on the block lenght.

The first run I setted just the first interval, and it worked as you can see below:

In the second run I setted the second interval, and it also worked as you can see below:

In the third run I tryed to bring all together and setted the first and second intervals, this time things runned wild (don't know why yet) as you can see:

Any ideas?

[gustavo-barros]

How the domains were calculated:

Maybe it should not have intersections between the notCrossings?

[lperron]

I would suggest the following

write a loop for the start

accumulate the duration of the task, skip breaks, and record end and total
duration

bucketize these

duration = 2 on {...}
duration = 3 on {...}

use this in the Domain.FromValues()
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 17 mai 2019 à 17:05, gustavo-barros [e-mail] a
écrit :

How the domains were calculated:

[image: image]
https://user-images.githubusercontent.com/36746102/57937272-f6f49980-789b-11e9-9244-716610bd224c.png

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3MJRQ7C473QZEZCXRLPV3CUDA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVVALRY#issuecomment-493487559,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3N6ZTZH42JTZ7PIBZ3PV3CUDANCNFSM4HIZUSHA
.

[gustavo-barros]

Sorry, I didn't understand how to apply what you said in my code.

[gustavo-barros]

Hey Laurent,

Good news! I was able to solve the problem. Expansions for different intervals lenghts. Give it a look:

But now I'm having a collateral problem. I don't know why the tasks are preferably being put at the right of the available intervals in all cases when its possible. It should be put preferably at left, there is no sense to let the machines idles like that.

Any idea?

[lperron]

short answer, because nobody tells the solver to do so.

long answer: solve the problem once. Store the optimal makespan.
Change the model to fix the makespan and minimize the sum of start times of
tasks
resolve the problem.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 20 mai 2019 à 16:41, gustavo-barros [e-mail] a
écrit :

Hey Laurent,

Good news! I was able to solve the problem. Expansions for different
intervals lenghts. Give it a look:

[image: image]
https://user-images.githubusercontent.com/36746102/58029578-4385e200-7af3-11e9-904b-d580bc1e2ff9.png

But now I'm having a collateral problem. I don't know why the tasks are
being preferably being put at the right of the available intervals in all
cases when its possible. It should be put preferably at left, there is no
sense to let the machines idles like that.

[image: image]
https://user-images.githubusercontent.com/36746102/58029174-7380b580-7af2-11e9-9470-4a7654340126.png

[image: image]
https://user-images.githubusercontent.com/36746102/58029308-a9be3500-7af2-11e9-84d2-e1818d592ec8.png

[image: image]
https://user-images.githubusercontent.com/36746102/58029372-c9edf400-7af2-11e9-97e9-f670c4ab4dc2.png

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3K56RGEIZUZN6B2AQTPWK2DFA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVZBQDY#issuecomment-494016527,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3PXRHM4GBM4UTJ2NLLPWK2DFANCNFSM4HIZUSHA
.

[gustavo-barros]

Hmmm I see.

How can I do that storage procedure following a remodeling process? You have any example for me to see?

[lperron]

After the first Solve(), calling Minimize() again will overwrite the
previous objective.
Then you can add a constraint on the makespan as you built the model.

To speed the second solve(), you can hint the previous solution. But there
are no API currently for that.
Although the code will be small.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 20 mai 2019 à 16:50, gustavo-barros [e-mail] a
écrit :

Hmmm I see.

How can I do that storage procedure following a remodeling process? You
have any example for me to see?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3JUPWA3OOFL5O3GLZ3PWK3BPA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVZCLMA#issuecomment-494020016,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3O3HAXLI36VFSGWFATPWK3BPANCNFSM4HIZUSHA
.

[gustavo-barros]

Something like this:

In wich:

Then solve it with the "allEndings":

If solved as optimal set the allStarts as minimize objective:

Then solve it again?

[gustavo-barros]

You think it is possible to do something like this, without running the solver again?

In this case I have the domain of all available intervals. So if in some way I could tell the solver that the task start should be always bigger or equal to the start of the available interval. But preferably equal or the closest possible. Maybe then running the solver again wouldn't be necessary.

[gustavo-barros]

Hey Laurent,

Have you any material explaining how these works?

DecisionStrategyProto.Types.VariableSelectionStrategy
DecisionStrategyProto.Types.DomainReductionStrategy

There are some options inside those classes like for example "ChooseFirst". I would like to know how each of these works, what it is for, etc.

Also you have something about these:

Model.AddMaxEquality();
Model.Minimize();

And others functions similar to those?

[lperron]

Everything is documented in non C# languages. C# doc tags are just too
painful to use.

https://github.com/google/or-tools/blob/stable/ortools/sat/cp_model.proto

or

https://github.com/google/or-tools/blob/stable/ortools/sat/python/cp_model.py
https://github.com/google/or-tools/blob/stable/ortools/sat/cp_model.proto

For the decision part, the names are quite explicit

Choose first variable, choose variable with min size...
select min value...

AddMaxEquality(target, IntVar[] array) => target == max(array)
Minimize(linear_expr) is the objective to minimize.

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 12:53, gustavo-barros [e-mail] a
écrit :

Hey Laurent,

Have you any material explaining how these works?

DecisionStrategyProto.Types.VariableSelectionStrategy
DecisionStrategyProto.Types.DomainReductionStrategy

There are some options inside those classes like for example
"ChooseFirst". I would like to know how each of these works, what it is
for, etc.

Also you have something about these:

Model.AddMaxEquality();
Model.Minimize();

And others functions similar to those?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3KP4M5CK22YO3FT33TPWPICJA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV3Q6LA#issuecomment-494341932,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3LVLIC6NAEZ2DMU5I3PWPICJANCNFSM4HIZUSHA
.

[gustavo-barros]

Ok, thank you.

By the way, the cp-sat solver runs a non-deterministic algorithm right? Some times I have the impression the solver gives me a different solution just because its a different run.

[lperron]

In parallel yes, it sequential mode, it should not.
We are fixing some bugs on determinism in sequential mode.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 13:08, gustavo-barros [e-mail] a
écrit :

Ok, thank you.

By the way, the cp-sat solver runs a non-deterministic algorithm right?
Some times I have the impression the solver gives me a different solution
just because its a different run.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3JHM6GY425HYHWZQ6TPWPJ4XA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV3SCGY#issuecomment-494346523,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3IDEAMX3IDOI42WGDLPWPJ4XANCNFSM4HIZUSHA
.

[gustavo-barros]

How can I add more complex linear expressions?

For example:

Model.AddLinearExpressionInDomain(start, firstCrossingDomains).OnlyEnforceIf(firstAcross);

It's saying, Start in firstCrossingDomains if/then firstAccross

But I would like something like this:

Start in "FirstDomain" AND End in "SecondDomain" .OnlyEnforceIf(FirstDomain AND SecondDomainBool)

Or some expression like that, can I do that?

[gustavo-barros]

What I need now is to be able to express: If start hits the first crossing area then expand X, if end hits a second crossing area then expand +Y. This would be the situation where a task is long enough to get one or more intervals between it.

[gustavo-barros]

Another way I'm trying is like this:

Model.Add(duration == operation.Duration + 1*4).OnlyEnforceIf(firstAcross);
Or
Model.Add(duration == operation.Duration + 14*4).OnlyEnforceIf(secondAcross);

But if firstAcross & secondAcross then:

ILiteral[] literals = new ILiteral[2];
literals[0] = firstAcross;
literals[1] = secondAcross;
Model.Add(duration == operation.Duration + (14+1)*4).OnlyEnforceIf(literals);

But it didn't worked yet

[lperron]

Don't do that

for each time point, compute the resulting duration

The implement the solution here:

https://github.com/google/or-tools/blob/stable/ortools/sat/doc/integer_arithmetic.md#step-function

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 15:51, gustavo-barros [e-mail] a
écrit :

Another way I'm trying is like this:

Model.Add(duration == operation.Duration + 14).OnlyEnforceIf(firstAcross);
Or
Model.Add(duration == operation.Duration +
144).OnlyEnforceIf(secondAcross);

But if firstAcross & secondAcross then:

ILiteral[] literals = new ILiteral[2];
literals[0] = firstAcross;
literals[1] = secondAcross;
Model.Add(duration == operation.Duration + (14+1)*4).OnlyEnforceIf(literals);

But it didn't worked yet

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3M6R3ZW7HKZEYLOJ7DPWP44XA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV37EJI#issuecomment-494400037,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KPDHQH32DVVTWAO6LPWP44XANCNFSM4HIZUSHA
.

[gustavo-barros]

Following your example, consider the image below. I set number over the task block just to be illustrative. In my case I think I would have 2 variables for my function, start and end. The area between 0 and 16 is inside the crossing area. And the area after 92 means it passed through another interval.

So I created a pseudo code to illustrate what I think is something following your idea. We gonna have a array containing all the intervals durations, that can be many and of different lenght. Then we define the domains where start and end hits and the according summation for the duration.

That's close to what you thinked?

[lperron]

Except the last 3 lines.

Only two bi can be true ?
I would expect the domains attached to b0, b1, b2 to be totally exclusive.
If this is true, then b0 + b2 + b3 == 1.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 16:54, gustavo-barros [e-mail] a
écrit :

Following your example, consider the image below. I set number over the
task block just to be illustrative. In my case I think I would have 2
variables for my function, start and end. The area between 0 and 16
is inside the crossing area. And the area after 92 means it passed through
another interval.

[image: image]
https://user-images.githubusercontent.com/36746102/58106173-0cc8ce00-7bbe-11e9-9c8b-f1057f971f72.png

So I created a pseudo code to illustrate what I think is something
following your idea. We gonna have a aray containing all the intervals
durations, that can be many and of different lenght. Then we define the
domains where start and end hits and the according summation for the
duration.

[image: image]
https://user-images.githubusercontent.com/36746102/58106288-3eda3000-7bbe-11e9-813f-7edbf2a3b982.png

That's close to what you thinked?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3OUZ5RZBN7UBC7MUATPWQELDA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV4FT3A#issuecomment-494426604,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3MAOPED7Y3JTAB6JRDPWQELDANCNFSM4HIZUSHA
.

[gustavo-barros]

The domains are in fact exclusive. But start and end can be inside two of then at the same time right?

For example, if start is in the first domain so b0 is true; in this case the task will be expanded.
And then if by chance the end happens to be in the second or third domains, b2 or b3 will be true also, right? So we have 2 of them being true. Or I'm wrong?

But now something came to my mind, I don't know if when applying the new calculated duration the end value will already be setted, so it can be compared to know if its on the other domain. This work shift problem is getting hard :/

I need in some way know if a expanded task will hit another interval so it will be added up over the intial expansion the next ones durations.

[gustavo-barros]

If you see in the image I sent you, it expands the first interval it encounters, adding up 14 hours. But that expansion makes it hit the next 1 hour interval. But this time it didn't expanded for the second one, wich would result in a 15 hours of sum up.

[lperron]

I am just looking at the start.
From the start, I can deduce the end and the duration.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 17:39, gustavo-barros [e-mail] a
écrit :

If you see in the image I sent you, it expands the first interval it
encounters, adding up 14 hours. But that expansion makes it hit the next 1
hour interval. But this time it didn't expanded for the second one, wich
would result in a 15 hours of sum up.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3M6P7ED62YXFD2N2HTPWQJR7A5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV4KCAA#issuecomment-494444800,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3NUJTVKIXAL3MTPWUDPWQJR7ANCNFSM4HIZUSHA
.

[gustavo-barros]

Hmmm, It might work. I'll try here.

[gustavo-barros]

There is a smart way to know the value of start?

For example:

Literal b0 = model.NewBoolVar("b0");
    model.AddLinearExpressionInDomain(
        start,
        Domain.FromValues(new long[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 })).OnlyEnforceIf(b0);
    model.Add(duration == operation.Duration + SUM(intervalsDurations[1];intervalsDurations[1]) * 4).OnlyEnforceIf(b0);

If I know that the start hit this domain and it is 0 for example, I know it will expand 14 hours hence I know it will hit the next interval and so on. But for that I need to know where in the domain start landed. Because I already have the duration and the next intervals positions, just need to know the value of start. How can I know that before solving? Or at least indicate that in such a way that while it is solving it is calculating correctly? That's not so clear to me yet.

[lperron]

This is enforced by

b0 + b2 + b3 = 1. One must be true, so start must fall in one of the
domains.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 18:27, gustavo-barros [e-mail] a
écrit :

There is a smart way to know the value of start?

For example:

Literal b0 = model.NewBoolVar("b0");
model.AddLinearExpressionInDomain(
start,
Domain.FromValues(new long[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 })).OnlyEnforceIf(b0);
model.Add(duration == operation.Duration + SUM(intervalsDurations[1];intervalsDurations[1]) * 4).OnlyEnforceIf(b0);

If I know that the start hit this domain and it is 0 for example, I know
it will expand 14 hours hence I know it will hit the next interval and so
on. But for that I need to know where in the domain start landed. Because I
already have the duration and the next intervals positions, just need to
know the value of start. How can I know that before solving? Or at least
indicate that in such a way that while it is solving it is calculating
correctly? That's not so clear to me yet.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3KJVIJQ6DICKLBLWXDPWQPFPA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV4OPNY#issuecomment-494462903,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3K5NWPGMQ5NBF6QI43PWQPFPANCNFSM4HIZUSHA
.

[gustavo-barros]

Hey Laurent,

Wich one takes effect early, the new duration application or the minimizing by the solver? For example if I tell the solver to minimize the starts, it will first apply the duration based on where the start first lands an then minimize or it will minimize the start and then compute the duration?

[lperron]

It will make the correct thing. All constraints will be enforced.
That is it may fix the start, then deduce the duration, then check
everything is consistent.

Whatever it does, it always checks that all constraints are enforced.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 20:24, gustavo-barros [e-mail] a
écrit :

Hey Laurent,

Wich one takes effect early, the new duration application or the
minimizing by the solver? For example if I tell the solver to minimize the
starts, it will first apply the duration based on where the start first
lands an then minimize or it will minimize the start and then compute the
duration?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3NYN5MVGVCPP7Q4G4LPWQ46DA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV4YPRA#issuecomment-494503876,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3PTC4IHNCDHTVPWBLLPWQ46DANCNFSM4HIZUSHA
.

[gustavo-barros]

I see. I'm asking because I set the solver to MaxEquality on the starts, and then told it to minimize it:

It solved that problem with the blocks to the right side, or at least in most of the cases.
Then everything looks quite nice. But I had this weird result at the end (the weird result is in last image):

Then it make me think if the solver was expanding first and then minimizing the starts.

[lperron]

Not convinced :-)
Most likely a problem in the computed domains.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 20:35, gustavo-barros [e-mail] a
écrit :

I see. I'm asking because I set the solver to MaxEquality on the starts,
and then told it to minimize it:
[image: image]
https://user-images.githubusercontent.com/36746102/58121267-62f93980-7bdd-11e9-9dd9-e0f389e94a9e.png
It solved that problem with the blocks to the right side, or at least in
most of the cases.
Then everything looks quite nice. But I had this weird result at the end
(the weird result is in last image):
[image: image]
https://user-images.githubusercontent.com/36746102/58121305-7c01ea80-7bdd-11e9-9a10-72dd54b125e3.png

[image: image]
https://user-images.githubusercontent.com/36746102/58121322-891ed980-7bdd-11e9-8359-689eb341a96d.png

[image: image]
https://user-images.githubusercontent.com/36746102/58121401-bec3c280-7bdd-11e9-83e9-23657a83bad8.png

Then it make me think if the solver was expanding first and then
minimizing the starts.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3N7CTKFPZN54LZSKCDPWQ6GXA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV4ZNGY#issuecomment-494507675,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3MMGPHJXCD4AO3CPC3PWQ6GXANCNFSM4HIZUSHA
.

[gustavo-barros]

Yeah strange, I'll check this out. Was happening when using the ChooseFirst strategy. Now I'm using the ChooseLowestMin and seems really nice. I'll run more tests here, but seems now I just need to fit the math formula to predict the duration size and we're done. I hope.

ChooseLowestMin strategy is slower right? ChooseFirst gets the first computed, hence faster correct?

[lperron]

Yes, but unless you havr thousands of variables, it does not matter.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mar. 21 mai 2019 à 20:52, gustavo-barros [e-mail] a
écrit :

Yeah strange, I'll check this out. Was happening when using the
ChooseFirst strategy. Now I'm using the ChooseLowestMin and seems really
nice. I'll run more tests here, but seems now I just need to fit the math
formula to predict the duration size and we're done. I hope.

ChooseLowestMin strategy is slower right? ChooseFirst gets the first
computed, hence faster correct?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3JIEHYRMUFMFLTGVXDPWRAHVA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV424MA#issuecomment-494513712,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3I4IL7DH377I2SRCITPWRAHVANCNFSM4HIZUSHA
.

[gustavo-barros]

Hey Laurent,

I'm still trying to figure it out a math formula or algorith to calculate the duration prediction based on task start. Below is the way I defined the linear expression for the second type interval. This second type interval have expansion = 14 hours and the first type interval have expansion = 1 hour.

As you can see in the image above, the secondIntervalCrossingInterval domain contain many intervals. So when I set the linear expression I don't know where start will land when I run the solver. In wich one of these intervals it will fall? I need to know that to be able to calculate the prediction.

See the image below, those are the useful intervals (green) and the intervals to across (red). Here they have the composition [16, 1, 20, 56, 16, 1, 20 ....]. But in practice they can vary on size and be different of each other. Any Idea how can I use the solver to do that?

My other idea is to declare a linear expression for each interval instead declaring a domain like this:

Then it would be for example something like this for each one of the intervals, so I could know wich interval the start would fall, so I could calculate the duration properly

What you think?

[lperron]

Can you remind me the definition of useful intervals ?
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mer. 22 mai 2019 à 15:28, gustavo-barros [e-mail] a
écrit :

Hey Laurent,

I'm still trying to figure it out a math formula or algorith to calculate
the duration prediction based on task start. Below is the way I defined the
linear expression for the second type interval. This second type interval
have expansion = 14 hours and the first type interval have expansion = 1
hour.

[image: image]
https://user-images.githubusercontent.com/36746102/58177435-c2f1ed80-7c7a-11e9-925b-7f0f60e501d4.png

As you can see in the image above, the secondIntervalCrossingInterval
domain contain many intervals. So when I set the linear expression I don't
know where start will land when I run the solver. In wich one of these
intervals it will fall? I need to know that to be able to calculate the
prediction.

See the image below, those are the useful intervals (green) and the
intervals to across (red). Here they have the composition [16, 1, 20, 56,
16, 1, 20 ....]. But in practice they can vary on size and be different of
each other. Any Idea how can I use the solver to do that?
[image: image]
https://user-images.githubusercontent.com/36746102/58176759-60e4b880-7c79-11e9-9c55-a55988da4239.png

My other idea is to declare a linear expression for each interval instead
declaring a domain like this:
[image: image]
https://user-images.githubusercontent.com/36746102/58177909-99859180-7c7b-11e9-9463-336f48529f00.png

Then it would be for example something like this for each one of the
intervals, so I could know wich interval the start would fall, so I could
calculate the duration properly
[image: image]
https://user-images.githubusercontent.com/36746102/58178167-10bb2580-7c7c-11e9-9d90-898139d242f1.png

What you think?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3PEHHD2XRQDRLIYM4DPWVDBVA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV7BMIY#issuecomment-494802467,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KEVHY2RKTDB3UVEQ3PWVDBVANCNFSM4HIZUSHA
.

[gustavo-barros]

Useful intervals are the normal work shift. The intervals to across are the ones nobody is working.

For example one useful interval starts at 08:00 AM and goes to 12:00 AM then we have the lunch break at 12:00 AM to 13:00 PM and so on.

[lperron]

OK, but you are aware this is just an algorithmic question, not an
optimization one ? :-)
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mer. 22 mai 2019 à 15:33, gustavo-barros [e-mail] a
écrit :

Useful intervals are the normal work shift. The intervals to across are
the ones nobody is working.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3MMU2QQE3NOO2PGAJLPWVDSNA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV7B2KY#issuecomment-494804267,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3LS4EA4NNSB3FCCX73PWVDSNANCNFSM4HIZUSHA
.

[gustavo-barros]

I know, but maybe there is a way to figure it out the start using some "solver way". That's why I asked :)
But if don't. I'll have to use some artifice to solve it hehe

[lperron]

No, keep iterating from the start, if working day -> decrease duration by
1, in non working day, skip
stop when duration reach 0.

Brute force, does not use the interval information, but should work.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le mer. 22 mai 2019 à 15:44, gustavo-barros [e-mail] a
écrit :

I know, but maybe there is a way to figure it out the start using some
"solver way". That's why I asked :)
But if don't. I'll have to use some artifice to solve it hehe

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3K64SYOX6EAZCD33NTPWVE4TA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODV7C5OI#issuecomment-494808761,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KBPYSOI26OR4W6CUTPWVE4TANCNFSM4HIZUSHA
.

[gustavo-barros]

Hmmm, good idea. I'll see what I get

[gustavo-barros]

Hey Laurent,

Can I do something like this? Using start as value?

will it get the start value during the solver runtime?

[gustavo-barros]

Hey Laurent,

In wich order the solver does things? I mean, it sets all the starts and then minimize it, altering the initial starts values, and repeat the process until optimal. Or does it minimize first and then the starts assumes its values depending on the minimization?

I think this knowledge now is crucial for the implementation I'm doing here.

[lperron]

You cannot expect the solver to assign variables in a fixed order. And it
should never change the fixed point achieved after propagation.
There is no way this knowledge change the results of the mathematical
equations you are writing.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 24 mai 2019 à 15:49, gustavo-barros [e-mail] a
écrit :

Hey Laurent,

In wich order the solver does things? I mean, it sets all the starts
and then minimize it, altering the initial starts values, and repeat
the process until optimal. Or does it minimize first and then the starts
assumes its values depending on the minimization?

I think this knowledge now is crucial for the implementation I'm doing
here.

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3LKAT6Z45YQ4OYDUYTPW7W6VA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWFNDIY#issuecomment-495636899,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3LHLF5YY7M7PF3LDVTPW7W6VANCNFSM4HIZUSHA
.

[gustavo-barros]

I'm assuming starts can fall anywhere depending of the solver answer. I'm just curious and investigative because a result I had here.

Everything is working fine, but I have a few anomalous punctual situations. Like this one in the image above. When task 30003 start falls over the second expansion domain it should expand 56 units of time. But it is expanding only 4. If we see, there is a first expansion area that the task 30003 start can fall, in this case it would expand 4 units of time.

What bringed me doubt is. Maybe the solver could have set task 30003 start temporally into the first expansion domain. Triggering a expansion of 4 units of time. And later made some rearrangement in the tasks moving 30003 forward, letting it with the wrong duration.

Is that possible?

[lperron]

No. Modifications of the domain are monotonic (until the next failure and
backtrack). You cannot set the min to 10, then moving it to 8. You can only
increase the min and decrease the max during propagation.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 24 mai 2019 à 16:08, gustavo-barros [e-mail] a
écrit :

I'm assuming starts can fall anywhere depending of the solver answer.
I'm just curious and investigative because a result I had here.

[image: image]
https://user-images.githubusercontent.com/36746102/58333256-65dd6f80-7e13-11e9-82e8-765d54647bf8.png

Everything is working fine, but I have a few anomalous punctual
situations. Like this one in the image above. When task 30003 start
falls over the second expansion domain it should expand 56 units of time.
But it is expanding only 4. If we see, there is a first expansion area that
the task 30003 start can fall, in this case it would expand 4 units of
time.

What bringed me doubt is. Maybe the solver could have set task 30003
start temporally into the first expansion domain. Triggering a
expansion of 4 units of time. And later made some rearrangement in the
tasks moving 30003 forward, letting with the wrong duration.

Is that possible?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3IFTCF33OQUKNNRJSLPW7ZGPA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWFPF7Y#issuecomment-495645439,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KNLQ2KT4DPKRV4T4TPW7ZGPANCNFSM4HIZUSHA
.

[gustavo-barros]

Ok, if is not possible then the problem should be elsewhere. I'll investigate. Thank you

[gustavo-barros]

Hey Laurent,

How can I explain to the solver: "Minimize the distances between adjacents blocks, if you can"
To avoid results like this?

I set to minimize the solution by the tasks starts. But some times it gives me results like this. And if you see, there is nothing opposing to the 20002 green block being there. Seems the solver just arbitrary put it there.

[gustavo-barros]

Hey Laurent,

I was able to solve the multiple expansion for intervals of different sizes problem, works perfectly. But I still didn't figure it out the way the solver is calculating some things. I'll explain to you the problem.

The only way I found to solve the problem was this:

First I had to create all crossing domains for each task, depending on it size. For each usefull interval band in the schedule. Meaning if a task start fall in some of part of this domain it should expand accordingly with the unused intervals following and the position of start.

Then I defined start and end variables like this, availableDomain is the domain containing all usefull intervals

Then I had to pulverize the crossing domain into fine grain domains, and for each of these domains I had to set a boolean var. This way I can ensure that if that boolVar happens to be true, the start is inside the fine grain domain, meaning I know the value of start from outside the solver.

Knowing that value I can use my mathematical formulation to predict the final spread after several expansions of different sizes.

My mathematical formulation is below:

Here is a image of the successfull multi-expansions:

But depending on the schedule picture, some anomalous behaviour happens. As I told you before. See the image below:

By the image, there is no crossing interval between time units 156 and 160. Meaning that task 20002/3 of size eight could never expand if it started in this range. But if you see, the expansion value is correct if start had fallen into the crossing domain in green (161 to 167). That's very weird.

Is almost like the start falled into crossing domain, expanded the task, and the was moved to the left afterwards. That's the only problem left for me to solve this issue. Please help me understand what's happening.

[gustavo-barros]

I solved it! Finnally! Thank you

Here is a Image with all successfull multi-expansions:

Now I just have to discover why the solver does this:

[lperron]

short answer, because is does not need to.
Long answer, solve once with a makespan objective, record the objective,
resolve with a constraint 'makespane == objective_best' and minimize the
sum of start times.
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le jeu. 30 mai 2019 à 16:16, gustavo-barros [e-mail] a
écrit :

I solved it! Finnally!

Here is a Image with all successfull multi-expansions:
[image: image]
https://user-images.githubusercontent.com/36746102/58638767-e7c61080-82cb-11e9-9f14-e6ed12ab30f9.png

Now I just have to discover why the solver does this:
[image: image]
https://user-images.githubusercontent.com/36746102/58638905-3bd0f500-82cc-11e9-9185-26a756289448.png

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3OEAWYX2JGC3L4ZLM3PX7OUFA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWSOF7Y#issuecomment-497345279,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3IWDPOIE4LLDCZRRLLPX7OUFANCNFSM4HIZUSHA
.

[gustavo-barros]

Hey Laurent,

In some special cases there is still happening a anomaly. I made several tests here, seems something internal to the solver. I was doubtful about the internal workening. But strong evidences is showing whats happening under the hood.

Some tasks have its "start" falling into crossing areas, making the block to expand, and afterwards the block is being moved right, and sometimes left.

The image bellow shows a example, that it is impossible to block 20001/3 to expand 4 if its start had fallen where it is, instead it should had not be expanded at all. I double checked the crossing intervals and they are correct.

I runned several tests. My crossing areas are correct for each block. And the spread calculation is also right. The only conclusion I'm getting is something like that is happening. And I don't know how to deal with it. How can I avoid this block movement?

[gustavo-barros]

I'm not saying it is a problem with the solver. I just need to understand what is happening, so then I can fix using the solver. Otherwise, I don't know if the only solution is through post-processing?

[lperron]

Can you try reducing the problem ?
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 31 mai 2019 à 21:21, gustavo-barros [e-mail] a
écrit :

I'm not saying it is a problem with the solver. I just need to understand
what is happening, so then I can fix using the solver. Otherwise, I don't
know if the only solution is through post-processing?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3KYG3QBD7M5RGRDBJLPYF3CFA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWWEYHA#issuecomment-497830940,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3NNLWST3VSJSR42FLTPYF3CFANCNFSM4HIZUSHA
.

[gustavo-barros]

Sory I didn't get it. What you mean by reducing? The number of tasks?

[lperron]

Yes, a smaller model, 1 task, enumerate all solutions, check them. Then 2
tasks...
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 31 mai 2019 à 21:49, gustavo-barros [e-mail] a
écrit :

Sory I didn't get it. What you mean by reducing? The number of tasks?

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3K2TNR7ZG5E5M3NMSLPYF6MTA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWWGWOY#issuecomment-497838907,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3LYY2VBJI6UGDDXGE3PYF6MTANCNFSM4HIZUSHA
.

[gustavo-barros]

Ok I'll try it. How can I enumerate all the solutions?

I'm using:

if (solver.Solve(Model) == CpSolverStatus.Optimal)

then I access the solution like this:

  foreach (var var in modelIntervals.MachinesToStarts[machine])
  {
      starts[solver.Value(var)] = var.Name();
  }

 foreach (var p in starts)
            {

then each block solution is inside p, where p is a string containing something like this: T1J1M0D3 meaning task 1 of job 1 in machine 0 has duration 3

[gustavo-barros]

I had some improvements trying to control the "end" when it expanded one time. But for several expansion I'll need a tricker way to control the "end". It should be the same process. But when it shifts the block to the side the logic breaks

[lperron]

https://github.com/google/or-tools/blob/stable/ortools/sat/doc/solver.md#searching-for-all-solutions-in-a-satisfiability-model
Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le ven. 31 mai 2019 à 21:59, gustavo-barros [e-mail] a
écrit :

I have some improvements trying to control the "end" when it expanded. But
for several expansion I'll need a tricker way to control the "end"

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3IUZYJ6YJTH7KCVIRLPYF7TJA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODWWHMZY#issuecomment-497841767,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3IPR4WNFGPFBCZTAILPYF7TJANCNFSM4HIZUSHA
.

[gustavo-barros]

Hey Laurent,

I need help. I think the problem is in the domains I'm configuring. Not sure yet.
I have all intervals, mixedCrossingIntervals, for each block where if start fall it should expand. And for each time unit inside these intervals I create a single value domain, so if start is in this domain it should expand with a spread.

But with just 2 tasks the problem happen. The orange block should have 12 in size. I checked my formula and it is correct. Seems the size is assuming wrong values depending on the domains. Even so because I had a case in wich a task had duration zero and it appeared with size one. And in that particular case there were no spread being calculated. So the solver (by the domains) distorted the real size. But now I need to know why. And how to do it right.

My start and end variables are declared as follow, being the switch true in this example:

the availableIntervalsForEnds is defined based on these time marks

And the availableIntervalsForStarts like this:

The example with the red and orange block are using the defaultStartsShift and defaultEndsShift only

[lperron]

Here is what I would do

for each start position, compute the expanded duration if the start is
feasible

store that in a map of lists

map[expanded_duration].Add(start)

create a list of IntVar[] all_bool_vars;

then for each expanded_duration
create bool_var
model.AddLinearExpressionInDomain(start,
Domain.FromValues(map[duration]).OnlyEnforceIf(bool_var)
model.Add(duration_var == duration).OnlyEnforceIf(bool_var)
all_bool_vars.Add(bool_var)

Then

sum(all_bool_vars) == 1

No need for complement, Not()...

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

Le lun. 3 juin 2019 à 21:56, gustavo-barros [e-mail] a
écrit :

Hey Laurent,

I need help. I think the problem is in the domains I'm configuring. Not
sure yet.
I have all intervals, mixedCrossingIntervals, for each block where if
start fall it should expand. And for each time unit I create a domain, so
if start is in this domain it should expand with a spread.

[image: image]
https://user-images.githubusercontent.com/36746102/58830056-ccd30380-861f-11e9-943c-02bb289b86c5.png

But with just 2 tasks the problem happen. The orange block should have 12
in size. I checked my formula and it is correct. Seems the size is assuming
wrong values depending on the domains. Even so because I had a case in wich
a task had duration zero and it appeared with size one. And in that
particular case there were no spread being calculated. So the solver (by
the domains) distorted the real size. But now I need to know why. And how
to do it right.
[image: image]
https://user-images.githubusercontent.com/36746102/58830034-bf1d7e00-861f-11e9-8681-01c367c52791.png

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/1223?email_source=notifications&email_token=ACUPL3LVG6KO5ZEUBX6I5LDPYVZNNA5CNFSM4HIZUSHKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODW2QKPQ#issuecomment-498402622,
or mute the thread
https://github.com/notifications/unsubscribe-auth/ACUPL3KVVPXVZF3UHLELU7LPYVZNNANCNFSM4HIZUSHA
.

[gustavo-barros]

Tried what you said. No success yet. Anything I got wrong?

[gustavo-barros]

Removing this line:

Model.Add(allComputedBoolVars.Sum() == 1);

It gives a solution, but not the right one.

[gustavo-barros]

What you tink is the most probable cause that this line:

Model.Add(allComputedBoolVars.Sum() == 1);

Gives me a no solution answer?

[gustavo-barros]

I made a little modification to this:

then the answer was correct:

But if I reduce the size of task 10001/1. The task 10001/2 with size ZERO, shows up with size ONE:

All correct but 10001/2 task

[gustavo-barros]

Changed end to this:

And a few changes in the rest of the code:

The domains and these linear expression actually affect the areas the start falls, hence affect the results:

Seems all correct, but now adding lenght to the duration of 10002/2 until it expands...

Still seems right, now adding 1+ to duration...it jumps the whole interval

Probably something related to the domains, that makes the solver shift the block

[gustavo-barros]

Just to clarify the intervals: the purple ones are the inactive ones and the orange are the usefull intervals

in the above images I'm using just green lines to surround the purple ones, and the red vertical line to show where a new day first shift starts. In this way you understand better the above images.

and this start means the oranges intervals

[gustavo-barros]

Hey Laurent,

I discovered something mind troubling. Give it a look, running the solver normally, without any expansions and just with the normal domain configuration:

Looking at this image I thought,

"Hmmm let me try expand just the 10001/1 block if it's end fall into {49, 50, 51, 52}"

Then I did this piece of code:

Then for my surprise this happened:

And removing this line:

We have this result:

Meaning, the linear expression I added altered my "ends domain". Including these new values to the domain where end can fall, and the 20001/1 task simply followed it.

Now we have a problem, how can we fix it?

[gustavo-barros]

I was not able to solve this specific problem using the solver. I had to solve with post-processing using graph algorithms and graph theory with little overhead and had a gain on performance. Just recording for those who may attempt a similar solution.

I think you can close this issue now. Thank you Laurent.

[morphace]

Hi @gustavo-barros
I have the same problem - did you find a satisfactory solution?
Are you willing to disclose it?