How to add piece-wise linear constraint in OR-Tools with CP-SAT solver?

Question

In a task allocation problem, suppose:

1. We need to allocate 2 tasks to a worker in the following 2 days.

2. There is only one worker and he can work at most 8 hours a day.

3. We want to minimize the total working time.

4. We can bundle tasks for efficiency and the number of hours needed is like:

0 task --> 0 hours

1 task --> 6 hours

2 task --> 8 hours

As a result, it is obvious that this worker could finish the two tasks in one day with exactly 8 hours needed.

# of Tasks V.S. # of Hours needed:

Blue dashed line: y = 6*n

Black line: Actual time = min(6*n, 6 + 2 * (n - 1))

Red line: Daily limit

This computation function (for the black line) can be defined in Python as

def compute_hours(n):
    return min(6*n, 6 + 2 * (n - 1))

In this example, I know we can create one additional bool indicator to force the total working time to be zero when no task is assigned to this worker. But is there a more graceful way to inplement this in OR-Tools with CP-SAT solver?

Answer 1

So you just need a function that does:

0 -> 0
1 -> 6
2 -> 8

  model.add_element(num_tasks, [0, 6, 8], num_hours)

A more general answer can be found by adapting the earliness tardiness sample.