Multi-objective optimization

[dreinon]

I have been noticing the solver doesn't deal with multi-objective optimization well, and it would be an interesting feature to work at.

Thanks :)

[tpaviot]

Multi-objective optimization is possible, by default. By "doesn't deal well", I agree, there are some things to know. The z3 solver has different strategies to solve a multi-objective optimization problem. The default behavior is called the "lexicon priority": the first objective is maximized/minimized, then the second, the third etc. Let's take the following example:

import processscheduler as ps
problem = ps.SchedulingProblem('SolvePriorities', horizon=10)
task_1 = ps.FixedDurationTask('task1', duration=2, priority=1, optional=True)
task_2 = ps.FixedDurationTask('task2', duration=2, priority=10, optional=True)
task_3 = ps.FixedDurationTask('task3', duration=2, priority=100, optional=True)

worker = ps.Worker('AWorker')
task_1.add_required_resource(worker)
task_2.add_required_resource(worker)
task_3.add_required_resource(worker)

problem.add_objective_priorities()
problem.add_objective_resource_utilization(worker)

solver = ps.SchedulingSolver(problem, verbosity=True)
#solver._solver.set(priority='pareto')
solution = solver.solve()

print(solution)

Solving this problem gives the following solution:

{
    "horizon": 10,
    "indicators": {
        "PriorityTotal": 0,
        "Utilization (AWorker)": 0
        "task1": {
            "scheduled": false,
        },
        "task2": {
            "scheduled": false,
        },
        "task3": {
            "scheduled": false,
}

That means no task is scheduled. The first objective is the priority: because the solver looks for the lowest sum for priorities, it decides to not schedule any optional task. Then, because, no task is scheduled, the utilization is optimized to 0 (there's obviously no other solution). If I switch the objectives:

problem.add_objective_priorities()
problem.add_objective_resource_utilization(worker)

Then the result is a bit different:

{
    "horizon": 10,
    "indicators": {
        "PriorityTotal": 246,
        "Utilization (AWorker)": 60
    },
       "task1": {
            "end": 6,
            "scheduled": true,
            "start": 4,
        },
        "task2": {
            "end": 4,
            "scheduled": true,
            "start": 2,
        },
        "task3": {
            "end": 2,
            "scheduled": true,
            "start": 0,
            "type": "FixedDurationTask"
        }
}

In this second case, the first objective being maximized is resource utilization: the three tasks are scheduled. Then the second objective is minimized (priorities), resulting in the correct order for tasks (task3 with the highest priority, then task2, and finally task1).

This default behavior can be changed to "box" or "pareto" optimizer (see section 8.1 of the following link https://theory.stanford.edu/~nikolaj/programmingz3.html). I did not implement yet those 3 kinds of multi-objective optimization in ProcessScheduler. "box" is efficient if objectives are independent, "pareto" returns all the solutions. For instance, you can turn the priority to "pareto" with the following line:

solver = ps.SchedulingSolver(problem, verbosity=True)
solver._solver.set(priority='pareto')
solution = solver.solve()

and check the output.

[dreinon]

Hi Thomas, just tried it and got:

'SchedulingProblem' object has no attribute 'add_objective_resource_utilization'

Should I uninstall pypi module and git clone master?

[tpaviot]

This issue can be closed, fixed by PR #25