How to design a good score function for business resource optimization

Drools Planner finds the best solution for any kind of business resource planning problem. But given 2 planning solutions, which one is better for your business? That depends on your business, so Planner needs to be told.

There are several techniques to define your score function. Each of these techniques can be combined with the others. Let's take a look at them:

Maximizing and minimizing constraints

Suppose you want your planning to maximize your apples harvest. In that case, the planning solution which harvests the most usable apples is the optimal solution. Each usable apple adds a score of +1 and the solution with the highest score wins:

Alternatively, suppose you have a vehicle routing problem and you want to minimize the fuel used to visit all of your customers. As shown in the second example, each fuel usages adds -1 to the score. Still the solution with the highest score wins.

In the examples above, there are only 3 solutions per problem. In reality, there are often more than 10^1000 solutions. Luckily, Planner doesn't evaluate all of them.

Score weighting

You can combine multiple constraints on the same problem. One technique is to weight them against each other. For example, in the vehicle routing problem below, every 1 unhappy driver is as bad for the business as 2 fuel usages:

The score for each solution is the sum of its weighted constraints. Again, the solution with the highest score wins.

Many business problems weight their constraints on its monetary value: they basically put a price tag on every expense and revenue and optimize the solution to maximize profit.

Score levels

Some constraints cannot be broken, because it makes the solution infeasible. Such constraints are often called hard constraints. For example in the vehicle routing problem, an overloaded truck's axle will break and the truck won't reach its destination. So, no amount of fuel usage is worth a broken axle:

The solution with the highest score on the first level wins. If that's the same, the solution with the highest score on the second level wins. Since score are naturally compared lexicographically, the solution with the highest score wins.

Most use cases use only 2 score levels: Hard constraints to respect the limits of physical reality or law. Soft constraints to maximize profit and/or employee well being. Planner supports any number of score levels.

Pareto optimization

This rare form of scoring has a intresting paradox.

Suppose you want to maximize your apples and oranges harvest. But you can't compare apples and oranges. You can't put a price tag on them or somehow define their relative worth to you. For a real world example, presume the oranges represent financial gain and the apples represent ecological gain.

Can we optimize such a planning problem? It might look like we can't, because we can't compare those apples and oranges, but in fact, we can optimize a great deal:

Since we can't compare apples and oranges, Planner can't decide if solution A or solution B should be used. Both solutions are shown to the user and depending on his preference either A or B is used.

But Planner can discard all the other solutions; because only an idiot would take the solution with 2 apples and 1 orange, regardless of his apples/oranges preference: solution A has more apples and not less oranges, so A dominates the solution with 2 apples and 1 orange. Even if the user prefers oranges it makes no sense to take a solution with less apples if there is no gain in oranges.

Conclusion

By combining these score techniques, we can craft a score function that accuratly and objectively represents the benefits to our business. That allows Drools Planner to generate a very efficient business resource planning for us, which is usually a financial and ecological win-win situation.