CODEWITHSUNDEEP
or-toolscp-sat
John
John

Reputation: 1828

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

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:

enter image description here

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?

Upvotes: 0

Views: 50

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11064

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.

Upvotes: 1

Related Questions