I'm implementing a similar solution for the Job-Shop problem with one difference: I don't know the machine that has to perform each task. Solving that is a part of the problem too. We can say, in fact, that I'm trying to solve a combination of the Nurse Problem and the Job-Shop Problem. More concretely, I have some tasks T with duration D that have to be performed by some specific employees E due to their nature N (let's say fron-end tasks, back-end, and so on) in a specific order O. I have: An array of T int vars that can acquire a value in the range of E (employee that's going to perform a task). An array of fixed duration interval vars (to scheduling them knowing it's duration D). E sequence vars which should be the sequence of tasks (interval vars) that an employee is going to perform. Some constraints for the relation N between tasks and employees. Some other constraints for the order O. A way to solve this is: first solve the assignment problem, then schedule the tasks. I have achieved this. However I want to implement it as an unique solution. I am stuck at this: How to create a disjunctive constraint that depends on the int vars I created before? To those who need to see code: for i in range(number_employees): disj = solver.DisjunctiveConstraint([interval_var[task_id] if int_var[task_id] == i] ,'i_name') [...] Of course, that doesn't work. I would really appreciate any suggestion.

Reputation: 61

Apply a constraint if condition with OR-Tools CP Solver

I'm implementing a similar solution for the Job-Shop problem with one difference: I don't know the machine that has to perform each task. Solving that is a part of the problem too. We can say, in fact, that I'm trying to solve a combination of the Nurse Problem and the Job-Shop Problem.

More concretely, I have some tasks T with duration D that have to be performed by some specific employees E due to their nature N (let's say fron-end tasks, back-end, and so on) in a specific order O.

I have:

An array of T int vars that can acquire a value in the range of E (employee that's going to perform a task).
An array of fixed duration interval vars (to scheduling them knowing it's duration D).
E sequence vars which should be the sequence of tasks (interval vars) that an employee is going to perform.
Some constraints for the relation N between tasks and employees.
Some other constraints for the order O.

A way to solve this is: first solve the assignment problem, then schedule the tasks. I have achieved this.

However I want to implement it as an unique solution.

I am stuck at this: How to create a disjunctive constraint that depends on the int vars I created before?

To those who need to see code:

for i in range(number_employees):
    disj = solver.DisjunctiveConstraint([interval_var[task_id] if int_var[task_id] == i] ,'i_name')
   [...]

Of course, that doesn't work.

I would really appreciate any suggestion.

Upvotes: 6

Answers (2)

Chatree Srichart

Reputation: 1

Laurent Perron, I modified no_overlap_sample_sat.py to follow your suggestion but it doesn't work. What I modified is:

# No Overlap constraint.
boolvar = model.NewBoolVar('boolvar')
i = model.NewIntVar(0, 10, 'i')
x = model.NewIntVar(0, 10, 'x')
model.Add(i - x == 0)
model.AddNoOverlap(
    [task_0, task_1, task_2, weekend_0, weekend_1, weekend_2]).OnlyEnforceIf(boolvar)
model.Add(x == i).OnlyEnforceIf(boolvar)
model.Add(x != i).OnlyEnforceIf(boolvar.Not())

The out put is:

Solver exited with nonoptimal status: 1

Do you have any more suggestion?

Upvotes: 0

Laurent Perron

Reputation: 11064

Should should have a look at the CP-SAT solver. It supports half-reified constraints.

That is, (in python):

model.AddNoOverlap([list of intervals]).OnlyEnforceIf(boolvar)

model.Add(x == i).OnlyEnforceIf(boolvar)

model.Add(x != i).OnlyEnforceIf(boolvar.Not())

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

Upvotes: 4

Apply a constraint if condition with OR-Tools CP Solver

Answers (2)

Related Questions