Adding multiple choice constraints to cp_model, ortools

Question

I'm following this tutorial https://developers.google.com/optimization/scheduling/job_shop of the Job Shop problem as I have a similar task, except I need an extra constraint which I can't figure out how to add. I want to add a constraint that (in the context of the Job Shop problem) means jobs cannot be processed on machines during their downtime. I have their downtime in intervals, for example , Machine 2 is down between 3 and 5 using the time units in the diagram.Example problem But I am unsure how to add it as a constraint.

ortools version 9.3.10497 python version 3.7.0

If I try:

if machine == 2:
    model.Add(all_tasks[job_id, task_id].start > 0)
    model.Add(all_tasks[job_id, task_id].end < 3)
    model.Add(all_tasks[job_id, task_id].start > 5)

then it obviously won't work as it's impossible to satisfy end < 3 and start > 5 simultaneously. How can I add these as a list of or constraints?For example:

if machine == 2:
    model.Add((all_tasks[job_id, task_id].start > 0 and all_tasks[job_id, task_id].end < 3) or all_tasks[job_id, task_id].start > 5)

I did try the above but it's expecting a bounded linear expression, and I couldn't find something for what I was looking for. I only started looking at this library today so apologies if I'm missing something obvious, but the docs aren't the best so thought I'd ask here.

Laurent Perron · Answer 1 · 2023-04-01T07:07:26.640

4

Python logical operators are silently wrong.

You can have a look at https://github.com/google/or-tools/blob/main/ortools/sat/docs/boolean_logic.md and https://github.com/google/or-tools/blob/main/ortools/sat/docs/channeling.md

But actually, there is a better way using domains. Assuming the end variable spawn between 0 and horizon, you can write:

if machine == 2:
    model.Add(all_tasks[job_id, task_id].start > 0)
    model.AddLinearExpressionInDomain(
        all_tasks[job_id, task_id].end,
        cp_model.Domain.FromIntervals([[0, 3], [5, horizon]])

edited Apr 01 '23 at 07:07

answered Mar 31 '23 at 18:52

Laurent Perron

8,594
1
8
22

Thank you, this has worked perfectly! I'm now trying to add something similar to AddAtMostOne, but doing it for more than 1. Do you happen to know which method is best for this? – data24 Apr 04 '23 at 14:18
sum(literals) <= 2 ? – Laurent Perron Apr 04 '23 at 14:44

score 0 · Answer 2 · answered Mar 31 '23 at 22:17

0

After digging a bit, I believe your problem is the same as the one in this thread

answered Mar 31 '23 at 22:17

PoneyUHC

287
1
11

Not great suggestions in the thread you mentioned (one on the original CP solver we developed, one on choco, and one on glpk, all of these are order of magnitude slower than CP-SAT) :-) – Laurent Perron Apr 01 '23 at 07:04

Adding multiple choice constraints to cp_model, ortools

2 Answers2

Linked