Chapter 9. Business constraints in OptaPlanner
Chapter 9. Business constraints in OptaPlanner Business constraints are used to limit conditions within a scenario. The conditions might be based on existing business contracts, resource availability, employee preferences, or business rules. To implement a business constraint in OptaPlanner, the business constraint must be formalized as a score constraint. The following score properties available in OptaPlanner provide flexible solutions: Score signum : make the constraint type positive or negative Score weight : put a cost or profit on a constraint type Score level (hard, soft, and so forth) : prioritize a group of constraint types Note Do not presume that your business knows all of its score constraints in advance. Expect score constraints to be added, changed, or removed after the first releases. 9.1. Negative and positive score constraints All score techniques are based on constraints. A constraint can be a simple pattern such as Maximize the apple harvest in the solution or a more complex pattern. A constraint is either negative or positive. A positive constraint is a constraint that you want to maximize. A negative constraint is a constraint that you want to minimize. This image illustrates that the optimal solution always has the highest score, regardless of whether the constraints are positive or negative. Most planning problems have only negative constraints and therefore have a negative score. In this case, the score is the sum of the weight of the negative constraints being broken, with a perfect score of 0. For example, in the N Queens problem, the score is the negative of the number of queen pairs which can attack each other. You can combine negative and positive constraints, even in the same score level. When a constraint activates on a certain planning entity set because the negative constraint is broken or the positive constraint is fulfilled, it is called a constraint match . 9.2. Score constraint weight Not all score constraints are equally important. If breaking one constraint once is equally as bad as breaking another constraint multiple times, then those two constraints have different weights even though they are in the same score level. Score weighting is easy in use cases where you can assign a cost to everything. In this case, the positive constraints maximize revenue and the negative constraints minimize expenses and together they maximize profit. Alternatively, score weighting is also often used to create social fairness. For example, a nurse who requests a free day pays a higher weight on New Years Eve than on a normal day. The weight of a constraint match can depend on the planning entities involved. For example, in the cloud balancing problem the weight of the soft constraint match for an active computer is the maintenance cost of that computer and this is different for each computer. Putting a good weight on a constraint is often a difficult analytical decision because it is about making choices and trade-offs against other constraints. Different stakeholders have different priorities. Do not waste time with constraint weight discussions at the start of an implementation. Instead, add a @constraintConfiguration annotation and allow users to change them through a UI. An inaccurate weight is less damaging than mediocre algorithms as shown in the following illustration: Most use cases use a score with int weights, such as HardSoftScore . 9.3. Score constraint level Sometimes a score constraint outranks another score constraint, no matter how many times the latter is broken. In this case, those score constraints are in different levels. For example, a nurse cannot work two shifts at the same time because of the constraints of physical reality, so this constraint outranks all nurse happiness constraints. Most use cases have only two score levels, hard and soft. The levels of two scores are compared in order. The first score level is compared first. If the two scores differ, the remaining score levels are ignored. For example, a score that breaks 0 hard constraints and 1000000 soft constraints is better than a score that breaks 1 hard constraint and 0 soft constraints. If there are two or more score levels, then a score is feasible if no hard constraints are broken. Note By default, OptaPlanner assigns all planning variables a planning value. If there is no feasible solution, this means that the best solution is infeasible. To leave some of the planning entities unassigned, apply overconstrained planning. For each constraint, you must pick a score level, a score weight, and a score signum. For example, -1soft has a score level of soft , a weight of 1 , and a negative signum. Do not use a large constraint weight when your business actually wants different score levels. That workaround, known as score folding , is broken: Note Your business might tell you that your hard constraints all have the same weight because they cannot be broken and therefore the weight does not matter. This is not true. If no feasible solution exists for a specific data set, the business can use the least infeasible solution to estimate how many business resources they are lacking. For example, in the cloud balancing problem, the least infeasible solution can reveal how many new computers are needed. Furthermore, if all of your hard constraints have the same weight, you will likely create a score trap. For example, in the cloud balancing problem if a computer has seven too few CPUs for its processes, then it must be weighted seven times as much as if it had only one CPU too few. OptaPlanner supports three or more score levels as well. For example, a company might decide that profit outranks employee satisfaction, or vice versa, while both constraints are outranked by the constraints of physical reality. Note To model fairness or load balancing, you do not need to use lots of score levels even though OptaPlanner can handle many score levels. Most use cases use a score with two or three weights, such as HardSoftScore and HardMediumSoftScore . You can combine all of these techniques seemlessly: