What is Search space of a Planning Problem in Optaplanner

This is the third blog in a series of blogs explaining Optaplanner and its related terminologies. In the previous blogs, wediscussed what is Optaplanner and it's constraints. Today we will be discussing about search space of Optaplanner. The core  of Optaplanner is to make the combinations and then calculate the score of that combination. Basically, Optaplanner tries to improve the solution by comparing the solution score and helps to get the best solution in a given time.

A planning problem has a very large number of solutions.

For Example, The 3x3x3 Rubik's cube has 43,252,003,274,489,856,000 combinations or 43 quintillion which is nearly Square of Earth population.

There are some categories of solutions:

Any solution is a possible solution, it can break any number of constraints(Hard, Medium, Soft). Planning problems have an incredibly very large number of possible solutions to that problem. Many of those solutions are meaningless.

Feasible solutions:- A feasible solution to that problem can be those solutions which don't break any Hard(Negative) constraints. The feasible solutions can be related to the possible solution. Sometimes for a planning problem, there are no feasible solutions but every feasible solution is a possible solution.

Optimal solution:- An Optimal solution is a type of solution which has the highest score. A planning problem has very few optimal solutions but every planning problem have at least one optimal solution even there are no feasible solutions and feasible solution isn't the optimal solution.

Best Solution:- The Best solution is the solution of planning with the highest score in a specific time. The best solution is likely to be a feasible solution and given enough time, it's can be an optimal solution.

Counterintuitively, the number of possible solutions of planning is huge enough (if calculated correctly), even with a very small dataset. in most of the cases have a more possible solution.

For Example: If we have 10 computers and 80 processes to assign them, so the search space will be (10^80) which is nearly equal to the atoms of the universe. So as we know that there is no silver bullet to find the optimal solution of a planning problem in a given time, with the help of Optaplanner and its algorithms we try to find a subset of the best solution or find an optimal solution by luck.

OptaPlanner has several optimization algorithms which are helping to improve a large number of possible solutions. Depending on the problems, some optimization algorithms perform better than as compared to others, but it’s impossible to tell in advance. With OptaPlanner, it is very easy to change the optimization algorithm, by changing the configuration of solver in a few lines of XML or code.

Thanks