At least one interval variable scheduled in a given period

[leonar...@gmail.com]

Hello everyone,

I'm seeking clarification on a specific aspect of CP-SAT related to interval variables. Specifically, I'm interested in understanding if there are constraints within CP-SAT that facilitate enforcing the scheduling of an interval variable within a defined time period.

Could someone shed light on whether CP-SAT provides mechanisms to restrict the scheduling of an interval variable to a particular time period or interval?

Any insights or examples illustrating how such constraints can be implemented within CP-SAT would be greatly appreciated.

Thank you in advance for your assistance!

[sascha...@gmail.com]

Your task is a bit unclear, especially since the questions reads very different from the title.

"facilitate enforcing the scheduling of an interval variable within a defined time period."

The domains of the interval-vars start- and end can be reduced to enforce it not being scheduled outside the defined time period.

"At least one interval variable scheduled in a given period"

Use https://developers.google.com/optimization/cp/channeling to introduce boolean auxiliary/helper-variables describing the status of some interval-var scheduling.

For example: bool_interval_start_greater_equal, bool_interval_end_less.

Then introduce a logical_and / conjunction to reason about some int-var being performed within you time-period, e.g. bool_interval_performed_in_period =  bool_interval_start_greater_equal  &&  bool_interval_end_less  && bool_interval_performed.

Then you can finally introduce a covering-constraint like: bool_interval_performed_in_period_A + bool_interval_performed_in_period_B + ... >= 1.

There are some details to be figured out like:

- do you need to reason about optionality

- do you have a single time-window for each interval-variable or multiple discontinuous ones -> one more logical_or / disjunction

Greetings,

Sascha

[leonar...@gmail.com]

Hi Sacha,

Thanks for your answer. Sorry for the confusion in the question definition.

I will try to reformulate my question: I have n optional interval variables (interval_1, ... , interval_n) and I want that at least one of then, have an intersection with the interval [period_greater_equal, period_less_than]. For example, if [period_greater_equal = 10, period_less_than = 15], then one solution could be to have interval_n.start = 13 and interval_n.end = 17. 

Thank you again!

[Laurent Perron]

So a clause with all the a_overlap_b like in https://github.com/google/or-tools/blob/stable/ortools/sat/docs/scheduling.md#detecting-if-two-intervals-overlap ?

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/729f4741-f315-4a95-accb-4f11f79bdfc7n%40googlegroups.com.