optapy / optapy-quickstarts

OptaPy quick starts for AI optimization: showcases many different use cases.
Apache License 2.0
21 stars 14 forks source link

Documentation of the employee scheduling #11

Open dietmarwo opened 2 years ago

dietmarwo commented 2 years ago

Thanks for this great python examples. Regarding the employee scheduling I have a few questions:

I am asking because I am writing a python employee scheduling tutorial using a different approach and would like to compare to optapy. My own approach solves the problem in less than a second fulfilling all "DESIRED" requests, so a bigger problem instance would be nice. I will include a section how to solve multi-objective variants of the problem generating a pareto-front.

Christopher-Chianelli commented 2 years ago
dietmarwo commented 2 years ago

Thks a lot for the detailed explanations. In fact my own scheduling approach involves switching from Python to another language (C++), fortunately this works much smoother, there is almost no overhead. Will post a link to my tutorial when it is finished, so that you can compare the approaches. But I see that a performance comparison makes not much sense now. The whole idea of multi-objective optimization is that you avoid priorization but generate a set of non-dominated choices as result. I know this is unusual for scheduling optimizers.

dietmarwo commented 2 years ago

Here https://github.com/dietmarwo/fast-cma-es/blob/master/tutorials/Employee.adoc is the first draft of my employee scheduling tutorial. It uses a (hopefully) suprizing approach utilizing parallelized continous single- and multi-objective optimizers and numba to speed up the computation of the fitness function. These optimizers can do suprizing things when they can evaluate the fitness up to a million times / second. Of course this shouldn't be compared to the current state of OptaPy, but to the future one utilizing Java bytecode. Getting things fast in Python is not easy, I am working quite a while on this issue.

Christopher-Chianelli commented 2 years ago

I wonder if using the fitness function in your post with @easy_score_calculator will be faster. Unlike the constraint stream API (@constraint_provider), @easy_score_calculator (and @incremental_score_calculator) only calls the function once per score calculation (instead of 100+ times per score calculation), so the overhead cost of calling the Python code should almost gone.

OptaPlanner (and thus OptaPy) currently do not support Pareto scoring (https://www.optaplanner.org/docs/optaplanner/latest/score-calculation/score-calculation.html#paretoScoring).

dietmarwo commented 2 years ago

Not sure how to replace @constraint_provider by @easy_score_calculator, these implement different interfaces.

My questions regarding optapy are:

The reason you may want to apply a multi-objective optimizer is not only that you get a pareto-front, but that it helps to optimize an additional second objective - for instance the standard deviation of the shifts assigned to the employees.

My multi-objective optimizer found a solution with a nearly equal shift distribution.

desired shift days 4 shifts per employee [7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 7, 7, 9] min shifts per employee 7 mean shifts per employee 7.875 std shifts per employee 0.4841229182759271

Compare this to the OctaPy result:

desired shift days 0 shifts per employee [11, 13, 13, 13, 12, 14, 11, 12, 7, 4, 8, 5, 1, 0, 0, 2] min shifts per employee 0 mean shifts per employee 7.875 std shifts per employee 4.998437255783052

Is it possible to define the standard deviation of the shifts assigned to the employees as soft constraint in OctaPy?

I did the following modifications to https://github.com/optapy/optapy-quickstarts/blob/stable/employee-scheduling/services.py to create a more challanging task:

OPTIONAL_SKILLS = ["Anaesthetics", "Surgery", "Radiology"]
...
    INITIAL_ROSTER_LENGTH_IN_DAYS = 28
...
    for i in range(20):
        skills = pick_subset(OPTIONAL_SKILLS, random, 1, 4, 4)

I tested with several OptaPy time limits and got:

time spent (100056), best score (-1hard/-480soft), score calculation speed (84/sec) step total (280).
time spent (200053), best score (-1hard/-480soft), score calculation speed (61/sec) step total (609).
time spent (300029), best score (-1hard/-480soft), score calculation speed (46/sec) step total (755).
time spent (400011), best score (-1hard/-480soft), score calculation speed (52/sec) step total (1436).
time spent (600030), best score (-1hard/0soft), score calculation speed (55/sec) step total (2631).
time spent (800051), best score (-1hard/0soft), score calculation speed (35/sec) step total (2111).
time spent (1200084), best score (-1hard/0soft), score calculation speed (31/sec) step total (3068).
time spent (1600059), best score (-1hard/0soft), score calculation speed (47/sec) step total (6529).
time spent (2400029), best score (0hard/-2880soft), score calculation speed (38/sec) step total (8148).
time spent (3200127), best score (0hard/-1440soft), score calculation speed (37/sec) step total (10865).
time spent (4800145), best score (0hard/-480soft), score calculation speed (45/sec) step total (19716).
time spent (20000064), best score (0hard/0soft), score calculation speed (21/sec) step total (72491).

A valid solution needs several hours.

My own solver needs only about 70 seconds, may be the difference is because of the Python / Java overhead? How long would the Java optimizer need for this task?

See https://github.com/dietmarwo/fast-cma-es/blob/master/tutorials/Employee.adoc for a summary of my experiments and a description of my alternative "stochastic solver".

Christopher-Chianelli commented 2 years ago

def get_number_of_employees_stream(constraint_factory): return constraint_factory.for_each(Employee) \ .group_by(ConstraintCollectors.count())

def minimize_standard_deviation_of_assigned_shifts_per_employee(constraint_factory): return constraint_factory.for_each(Shift) \ .group_by(lambda shift: shift.employee, ConstraintCollectors.count()) \ .join(get_average_number_of_shifts_stream(constraint_factory)) \ .group_by(ConstraintCollectors.sum(lambda employee, assigned_shifts, mean_assigned_shifts: 100 * ((assigned_shifts - mean_assigned_shifts)**2))) \ .join(get_number_of_employees_stream(constraint_factory)) \ .penalize('minimize standard diviation', HardSoftScore.ONE_SOFT, lambda variance_sum, number_of_employees: math.ceil(variance_sum / number_of_employees))

This minimizes the variance (up to 2 decimal digits; if you want more precision, change the 100 to something larger), which also minimize the standard variation (you could add a sqrt to get standard variation if needed) (the 100 is used in the sum since it the value is changed to int to avoid problems caused by floating point math (in particular, it cannot be guaranteed that (x + y + z - y - z) == x in floating point math, which will cause score corruption).

The difference is almost certainly due to Python / Java overhead; look at the score calculation speed: 21/sec. That is extremely low and is mostly from transferring between java and python contexts a lot. For the equivalent OptaPlanner quickstart (https://github.com/kiegroup/optaplanner-quickstarts/tree/stable/use-cases/employee-scheduling), the score calculation speed for a larger problem on my computer is `63069/sec`; for optapy, it is around `84/sec` on a smaller problem (in short, at least a 700 times speed increase).  The Java Optimizer would probably find a solution in under 10 second, but it hard to say for certain without knowing your computer specs.

To implement an `@easy_score_calculator`, all you need is a  function to calculate the score for a given (possibly invalid) solution. From your `Employee.adoc`, it would look like this:
```python
@easy_score_calculator
def fitness(solution):
        score = solution.fitness(solution.shift_list)  # unsure what x is; look like planning variables (employee the shift is assigned to)
        return SimpleScore.of(-score)
Christopher-Chianelli commented 2 years ago

(A side note: you should really use a HardSoftScore for this; right now, using the fitness function in your post, satisfying 10 DESIRED shifts would allow 2 shifts to overlap, which is almost certainly not a desired result)

dietmarwo commented 2 years ago

Thanks for your explanations.

1) Tried

solver_config = solver_config_create_from_xml_file(pathlib.Path('solverConfig.xml'))
solver_config\
    .withSolutionClass(EmployeeSchedule)\
    .withEntityClasses(Shift)\
    .withConstraintProviderClass(employee_scheduling_constraints)\
    .withTerminationSpentLimit(Duration.ofSeconds(100)

solverConfig.xml:

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <environmentMode>FAST_ASSERT</environmentMode>
</solver>

and still always get the same result:

desired shift days 0
shifts per employee [11, 13, 13, 13, 12, 14, 11, 12, 7, 4, 8, 5, 1, 0, 0, 2]
min shifts per employee 0
mean shifts per employee 7.875
std shifts per employee 4.998437255783052

2) algorithm config also go into 'solverConfig.xml' ? No solver_config.withStrategy(... ?

3) tried

        .reward('Desired day for employee', HardSoftScore.ONE_SOFT,
                  lambda shift, availability: get_shift_duration_in_minutes(shift))

and got

desired shift days 5 shifts per employee [11, 13, 13, 13, 12, 14, 12, 12, 7, 4, 8, 5, 1, 0, 0, 1] min shifts per employee 0 mean shifts per employee 7.875 std shifts per employee 5.12195031213697

so this works.

4) tried your minimize_standard_deviation_of_assigned_shifts_per_employee code and got:

File "/home/xxx/ana39/lib/python3.9/site-packages/optapy/optaplanner_api_wrappers.py", line 28, in init self.delegate = SolverManager.create(solver_config) TypeError: No matching overloads found for org.optaplanner.constraint.streams.drools.bi.DroolsAbstractBiConstraintStream.join(PythonUniConstraintStream,org.optaplanner.core.api.score.stream.tri.TriJoiner[]), options are: public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.constraint.streams.bi.InnerBiConstraintStream.join(java.lang.Class,org.optaplanner.core.api.score.stream.tri.TriJoiner[]) public final org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.constraint.streams.drools.bi.DroolsAbstractBiConstraintStream.join(org.optaplanner.core.api.score.stream.uni.UniConstraintStream,org.optaplanner.core.api.score.stream.tri.TriJoiner[]) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(org.optaplanner.core.api.score.stream.uni.UniConstraintStream,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(org.optaplanner.core.api.score.stream.uni.UniConstraintStream,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(org.optaplanner.core.api.score.stream.uni.UniConstraintStream,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(org.optaplanner.core.api.score.stream.uni.UniConstraintStream,org.optaplanner.core.api.score.stream.tri.TriJoiner) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(org.optaplanner.core.api.score.stream.uni.UniConstraintStream) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(java.lang.Class,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(java.lang.Class,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(java.lang.Class,org.optaplanner.core.api.score.stream.tri.TriJoiner,org.optaplanner.core.api.score.stream.tri.TriJoiner) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(java.lang.Class,org.optaplanner.core.api.score.stream.tri.TriJoiner) public default org.optaplanner.core.api.score.stream.tri.TriConstraintStream org.optaplanner.core.api.score.stream.bi.BiConstraintStream.join(java.lang.Class)

5) regarding performance: will try the java version after my vacation (in 2 weeks from now)

Christopher-Chianelli commented 2 years ago
  1. Should be set to NON_REPRODUCIBLE, with an optional random seed:

    <solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
    <environmentMode>NON_REPRODUCIBLE</environmentMode>
    <randomSeed>RANDOM_SEED</randomSeed>
    </solver>
  2. Algorithm can be configured with both XML and Python; the relevant config classes are in optapy.config, you use withPhases to set the phases/algorithm OptaPy will run

  3. Look like a bug; I'll fix it

dietmarwo commented 2 years ago

1: Tried "NON_REPRODUCIBLE", still get always the same result. I think NON_REPRODUCIBLE is more targeted to avoid spending additional effort in generating reproducible runs. It is not targeted for diversity of results. So it seems this is a disadvantage of optaplanner compared to a standard continous optimizer https://github.com/dietmarwo/fast-cma-es/blob/master/tutorials/Employee.adoc#single-objective-optimization .

  1. Here is a list of documantation issues I observed trying optapy:

This means you have almost no chance to figure out how to use optapy without checking the java doc https://www.optaplanner.org/docs/optaplanner/latest/, and then you cannot be sure what exactly works in Python and what is not implemented yet.

  1. Progress regarding your minimize_standard_deviation_of_assigned_shifts_per_employee after updating to optapy-8.23.0a0. Now I get:
java.util.concurrent.ExecutionException: java.util.concurrent.ExecutionException: java.lang.IllegalStateException: Solving failed for problemId (1).
NOT_SOLVING
Traceback (most recent call last):
  File "DefaultScoreManager.java", line 54, in org.optaplanner.core.impl.score.DefaultScoreManager.updateScore
  File "DroolsConstraintStreamScoreDirector.java", line 86, in org.optaplanner.constraint.streams.drools.DroolsConstraintStreamScoreDirector.calculateScore
  File "StatefulKnowledgeSessionImpl.java", line 1073, in org.drools.kiesession.session.StatefulKnowledgeSessionImpl.fireAllRules
  File "StatefulKnowledgeSessionImpl.java", line 1081, in org.drools.kiesession.session.StatefulKnowledgeSessionImpl.fireAllRules
  File "StatefulKnowledgeSessionImpl.java", line 1090, in org.drools.kiesession.session.StatefulKnowledgeSessionImpl.internalFireAllRules
  File "DefaultAgenda.java", line 687, in org.drools.kiesession.agenda.DefaultAgenda.fireAllRules
  File "DefaultAgenda.java", line 695, in org.drools.kiesession.agenda.DefaultAgenda.internalFireAllRules
  File "DefaultAgenda.java", line 748, in org.drools.kiesession.agenda.DefaultAgenda.fireLoop
  File "SequentialRuleEvaluator.java", line 43, in org.drools.core.concurrent.SequentialRuleEvaluator.evaluateAndFire
  File "AbstractRuleEvaluator.java", line 33, in org.drools.core.concurrent.AbstractRuleEvaluator.internalEvaluateAndFire
  File "RuleExecutor.java", line 101, in org.drools.core.phreak.RuleExecutor.evaluateNetworkAndFire
  File "RuleExecutor.java", line 454, in org.drools.core.phreak.RuleExecutor.innerFireActivation
  File "LambdaConsequence.java", line 74, in org.drools.modelcompiler.consequence.LambdaConsequence.evaluate
  File "Block4.java", line 40, in org.drools.model.functions.Block4$Impl.execute
  File "BiRuleContext.java", line 46, in org.optaplanner.constraint.streams.drools.common.BiRuleContext.lambda$newRuleBuilder$2e50f6b5$1
  File "com.sun.proxy.$Proxy41.java", line -1, in com.sun.proxy.$Proxy41.applyAsInt
  File "org.jpype.proxy.JPypeProxy.java", line -1, in org.jpype.proxy.JPypeProxy.invoke
  File "org.jpype.proxy.JPypeProxy.java", line -2, in org.jpype.proxy.JPypeProxy.hostInvoke
  File "org.jpype.JPypeContext.java", line -1, in org.jpype.JPypeContext.createException
org.jpype.PyExceptionProxy: org.jpype.PyExceptionProxy

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "DefaultScoreManager.java", line 54, in org.optaplanner.core.impl.score.DefaultScoreManager.updateScore
  File "DroolsConstraintStreamScoreDirector.java", line 86, in org.optaplanner.constraint.streams.drools.DroolsConstraintStreamScoreDirector.calculateScore
  File "StatefulKnowledgeSessionImpl.java", line 1073, in org.drools.kiesession.session.StatefulKnowledgeSessionImpl.fireAllRules
  File "StatefulKnowledgeSessionImpl.java", line 1081, in org.drools.kiesession.session.StatefulKnowledgeSessionImpl.fireAllRules
  File "StatefulKnowledgeSessionImpl.java", line 1090, in org.drools.kiesession.session.StatefulKnowledgeSessionImpl.internalFireAllRules
  File "DefaultAgenda.java", line 687, in org.drools.kiesession.agenda.DefaultAgenda.fireAllRules
  File "DefaultAgenda.java", line 695, in org.drools.kiesession.agenda.DefaultAgenda.internalFireAllRules
  File "DefaultAgenda.java", line 748, in org.drools.kiesession.agenda.DefaultAgenda.fireLoop
  File "SequentialRuleEvaluator.java", line 43, in org.drools.core.concurrent.SequentialRuleEvaluator.evaluateAndFire
  File "AbstractRuleEvaluator.java", line 33, in org.drools.core.concurrent.AbstractRuleEvaluator.internalEvaluateAndFire
  File "RuleExecutor.java", line 101, in org.drools.core.phreak.RuleExecutor.evaluateNetworkAndFire
  File "RuleExecutor.java", line 460, in org.drools.core.phreak.RuleExecutor.innerFireActivation
  File "DefaultAgenda.java", line 935, in org.drools.kiesession.agenda.DefaultAgenda.handleException
  File "DefaultConsequenceExceptionHandler.java", line 39, in org.drools.core.runtime.rule.impl.DefaultConsequenceExceptionHandler.handleException
Exception: Java Exception

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "/home/xxx/ana39/lib/python3.9/site-packages/optapy/optaplanner_api_wrappers.py", line 170, in _wrap_call
    return function(wrapped_problem)
  File "/home/xxx/ana39/lib/python3.9/site-packages/optapy/optaplanner_api_wrappers.py", line 183, in <lambda>
    score = self._wrap_call(lambda wrapped_solution: self._java_updateScore(wrapped_solution), solution)
org.kie.api.runtime.rule.ConsequenceException: Exception executing consequence for rule "minimize standard diviation" in org.optaplanner.optapy.generated.class3.domain.EmployeeSchedule: org.jpype.PyExceptionProxy

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "/home/xxx/stock/optapy-quickstart/employee-scheduling/services.py", line 607, in <module>
    save_solution()
  File "/home/xxx/stock/optapy-quickstart/employee-scheduling/services.py", line 347, in save_solution
    score = score_manager.updateScore(solution)
  File "/home/xxx/ana39/lib/python3.9/site-packages/optapy/optaplanner_api_wrappers.py", line 183, in updateScore
    score = self._wrap_call(lambda wrapped_solution: self._java_updateScore(wrapped_solution), solution)
  File "/home/xxx/ana39/lib/python3.9/site-packages/optapy/optaplanner_api_wrappers.py", line 177, in _wrap_call
    raise RuntimeError(error_message) from e
RuntimeError: An error occurred when getting the score. This can occur when functions take the wrong number of parameters (ex: a setter that does not take exactly one parameter) or by a function returning an incompatible return type (ex: returning a str in a filter, which expects a bool). This can also occur when an exception is raised when evaluating constraints/getters/setters.
Christopher-Chianelli commented 2 years ago

Regarding minimize_standard_deviation_of_assigned_shifts_per_employee, I think the issue is a type error (hard to see because JPype hide the exception; with the translator work, provided the code can be translated (i.e. not implemented in C), the actual exception should show up, and I can put warnings when the code is being compiled (ex: attribute 'missing_attribute' does not exist). I will post a corrected version once I actually test on my end.

Christopher-Chianelli commented 2 years ago

Documentation search issue is now fixed; look like antora-lunr did a backward incompatible change, and the GitHub action to generate docs is set to use the latest version of antora and antora-lunr, which in turns broke the search function.

dietmarwo commented 2 years ago

Thks for the fix. And thks for the hint regarding PyCharm. Used Eclipse before, with Pycharm code completion works. Waiting for the corrected version of minimize_standard_deviation_of_assigned_shifts_per_employee since I would like to see how far the standard deviation can be lowered.

Christopher-Chianelli commented 2 years ago

Sorry for the (very late) reply; been working on the bytecode translator and forgot about this convo; Adapting from https://stackoverflow.com/a/74018711/9698517 , the corrected version of minimize_standard_deviation_of_assigned_shifts_per_employee is:

def get_employee_number_of_shift_pairs(constraint_factory):
    return (
        constraint_factory.for_each(Shift)
            .group_by(lambda shift: shift.employee, ConstraintCollectors.count())
    )

def get_average_number_of_shifts_stream(constraint_factory):
    return (
        get_employee_number_of_shift_pairs(constraint_factory)
            .group_by(ConstraintCollectors.average(lambda employee, count: count))
    )

def minimize_standard_deviation_of_assigned_shifts_per_employee(constraint_factory: ConstraintFactory):
    return (
        get_employee_number_of_shift_pairs(constraint_factory)
            .join(get_average_number_of_shifts_stream(constraint_factory))
            .group_by(ConstraintCollectors.compose(
                          ConstraintCollectors.sum(lambda user, load, avg: (load - avg)**2),
                          ConstraintCollectors.count_tri(),
                          lambda diff_sum, count: int(((diff_sum / max(1, count)) * 100))
            ))
            .penalize('Minimize variance', HardSoftScore.ONE_SOFT,
                           lambda variance: variance)
    )