Optional tasks forced to be scheduled, otherwise the solver doesn't finish

[dreinon]

First of all, saying that I set the max_time of the solver to 1 hour (3600 sec) so it doesn't stop without finding a solution.

All my tasks are optional, but they all appear to be being forced to get scheduled, otherwise the solver doesn't find a solution. I have tried multiple times, and if the number of tasks fits the number of slots available from the resource, then it finished, otherwise, it doesn't.

Might it be because of the task constraints? I understood when I read the doc that the constraints where applied only if the task was sheduled.

For each task, these constraints are being applied:

students_tasks = []
for stud_id in students:
    num_practices = students[stud_id]['num_practices']
    unavailability = students[stud_id]['unavailability']
    for i in range(num_practices):
        students_tasks.append(ps.FixedDurationTask(f'{stud_id}__{i+1}', duration=PRACTICE_LENGTH, priority = round((21 - i)/num_practices), optional = True))
        students_tasks[-1].add_required_resource(Car)
        task_constraints = []
        task_constraints.append(ps.or_([ps.TaskStartAt(students_tasks[-1],t) for t in car_1['schedule']]))
        for j in unavailability:
            task_constraints.append(ps.not_(ps.and_([ps.TaskStartAfterLax(students_tasks[-1], j[0]), ps.TaskEndBeforeLax(students_tasks[-1], j[1])])))
        constraints.append(ps.and_(task_constraints))

Thank you in advance!

[tpaviot]

You're right, the optional task comes with its related constraints, they are added to the solver if and only if the task is scheduled. This is the way I implemented optional task: an optional task is either scheduled or not scheduled. I'm not surprised that the solver does not find a solution to your problem in a reasonable time. Indeed, the combinatorics explodes. Let's say 0 is "not scheduled" for the optional task, and 1 is scheduled, then if you have 1 optional task, these leads to two different possible states, 2 tasks = 4 possible states (00, 01, 10, 11), you see it is a binary representation. So with n optional tasks, the solver has different states to study! How many tasks do you define? This exponential complexity is the signature of an NP problem, but I'm not sure whether my representation is NP, or if the problem in itself (n optional tasks) is NP. Moreover, I can't imagine what really is a plan where all tasks are optional. No scheduled tasks could be a solution ?

[dreinon]

Right, I'll explain a bit how I planned the problem.

I want to schedule as many tasks as possible, but since I want a "waiting list", I want that the scheduler finishes anyway even though some tasks haven't been able to get scheduled, and those that haven't been sheduled would be my "waiting list".

Yesterday I found out that in a case where the tasks with their duration where more than the slots available, after about 8 minuts, the scheduler finished with no solution, which I don't quite understand. Since all my tasks are optional, how I imagine the solver to act is to shedule as many as it can and to return a solution where it scheduled only the ones it could schedule, and the ones the solver coudn't schedule would be my waiting list.

So my approach in one side is to determine how many tasks as maximum can be scheduled, and how many can't, and in the other side, what would be the scheduling of the ones that have been scheduled.

I'm probably missing something about how the solver works, right??

Thank you for answering, Thomas!

Edit: I have tried with the number of tasks duration = number of slots available = 66, and the solver solves it in a couple seconds, but when the number of tasks duration = 67 > 66 = number of slots available, the solver can't find any solution, and even though the computational cost is exponential, it shouldn't be that much more of a cumputational cost for the solver not to find any solutions, right?

[dreinon]

Closing issue since it was a problem of my problem contraints design.