Red Hat Training

A Red Hat training course is available for Red Hat Decision Manager

Chapter 2. What is a planning problem?

A planning problem has an optimal goal, based on limited resources and under specific constraints. Optimal goals can be any number of things, such as:

  • Maximized profits - the optimal goal results in the highest possible profit.
  • Minimized ecological footprint - the optimal goal has the least amount of environmental impact.
  • Maximized satisfaction for employees or customers - the optimal goal prioritizes the needs of employees or customers.

The ability to achieve these goals relies on the number of resources available. For example, the following resources might be limited:

  • The number of people
  • Amount of time
  • Budget
  • Physical assets, for example, machinery, vehicles, computers, buildings, and so on

You must also take into account the specific constraints related to these resources, such as the number of hours a person works, their ability to use certain machines, or compatibility between pieces of equipment.

The Business Optimizer helps Java programmers solve constraint satisfaction problems efficiently. It combines optimization heuristics and metaheuristics with efficient score calculation.

2.1. A planning problem has a huge search space

A planning problem has a number of solutions.

There are several categories of solutions:

Possible solution
A possible solution is any solution, whether or not it breaks any number of constraints. Planning problems often have an incredibly large number of possible solutions. Many of those solutions are worthless.
Feasible solution
A feasible solution is a solution that does not break any (negative) hard constraints. The number of feasible solutions tends to be relative to the number of possible solutions. Sometimes there are no feasible solutions. Every feasible solution is a possible solution.
Optimal solution
An optimal solution is a solution with the highest score. Planning problems usually have a few optimal solutions. They always have at least one optimal solution, even in the case that there are no feasible solutions and the optimal solution is not feasible.
Best solution found
The best solution found is the solution with the highest score found by an implementation in a given amount of time. The best solution found is likely to be feasible and, given enough time, it’s an optimal solution.

Counterintuitively, the number of possible solutions is huge (if calculated correctly), even with a small data set.

In the examples provided in the planner-engine distribution folder, most instances have a vast number of possible solutions. As there is no guaranteed way to find the optimal solution, any implementation is forced to evaluate at least a subset of all those possible solutions.

The Business Optimizer supports several optimization algorithms to efficiently wade through that incredibly large number of possible solutions.

Depending on the use case, some optimization algorithms perform better than others, but it is impossible to tell in advance. Using the Business Optimizer, you can switch the optimization algorithm by changing the solver configuration in a few lines of XML or code.

2.2. A planning problem has constraints

Usually, a planning problem has at least two levels of constraints:

  • A (negative) hard constraint must not be broken.

    For example, one teacher can not teach two different lessons at the same time.

  • A (negative) soft constraint should not be broken if it can be avoided.

    For example, Teacher A does not like to teach on Friday afternoons.

Some problems also have positive constraints:

  • A positive soft constraint (or reward) should be fulfilled if possible.

    For example, Teacher B likes to teach on Monday mornings.

Some basic problems only have hard constraints. Some problems have three or more levels of constraints, for example, hard, medium, and soft constraints.

These constraints define the score calculation (otherwise known as the fitness function) of a planning problem. Each solution of a planning problem can be graded with a score. With the Business Optimizer, score constraints are written in an object oriented language, such as Java code or Drools rules.

This type of code is flexible and scalable.