General advise for achieving best score

[mikepictor]

I have a solution engine in place which is reliably producing good solutions...but not great ones. Simple scenarios get close to perfect, but sometimes we throw complex scenarios at it, and while it becomes impossible for it to produce a perfect solution, I am still trying to get it to be "as good as possible".

When I look at the final product rendered in our UI, it is sometimes easy to spot some obvious gains. I can look at a given task, starting at let's say 14:30, and I can clearly see that there is no constraint preventing it from starting at 14:00, and if it did, it would get a better score. I can even see that it is taking a soft penalty for starting half an hour later than it needs to.

So I am left with thinking...why on earth is the solver accepting that penalty? The theoretical obvious answer is that some other constraint breaks if it goes earlier, such that the overall score gets worse, but I am as certain as I can be that in this example, there is simply no other contraint that would get in the way. I have purposefully created a scenario where other constraints around that time are open (inventing extra planning entities such that all other constraints should be relaxed). It's simply accepting a worse score than it needs to.

Now partly I am considering my termination constraints. What if I gave it more time? The thing is, it's not even using it's max time. I have a max termination of 60 seconds, and an unimproved score limit of 10 seconds. In my scenario, it spent 42 seconds before terminating (which I take to mean it reached "best" score at 32 seconds and spent 10 seconds unsuccessfully trying to improve it?). This means in those 10 seconds, it failed to figure out that if it moved the task from 14:30 to 14:00...the score would improve. Now maybe it just had so many other variables to consider that it spent 10 seconds playing around with other entities. It's not even one entity though, I can look over the solution and easily spot a few ways it could have achieved a better score.

I guess my real questions are...

• Am I using the termination limits in a logical way?
• Are there other config settings (termination or otherwise) I should be looking at?
• My environment-mode is REPRODUCIBLE, largely because I was uncertain of the impact of NON_REPRODUCIBLE, and the documentation only describes it as "slightly faster". I think I have worked out any outright bugs in my constraints, so maybe I should go with NON_REPRODUCIBLE? Maybe even it would be desirable, as it would allow for different directions of exploration.

My main thinking right now is just to up the termination limits...and see what happens. All I know is that I KNOW there are better solutions just by looking at it, and I want to think the solver can figure that out as well.

THis isn't a bug report...this is just me trying to get advice from a discussion forum. 😀

[mikepictor]

As an experiment, I increase the time limit to 2 minutes, and the unimproved time limit to 30 seconds, and suddenly it started taking all 120 seconds, suggesting to me that there were small improvements that took longer than 10 seconds to realize. The solution was indeed better, but it still wasn't perfect, and maybe perfect is something that is unreasonable to expect.

Still debating the impact of changing to NON_REPRODUCIBLE...maybe I will have to give it a try

[Christopher-Chianelli]

Without knowing all your constraints and model, it is hard to say. If I were to guess, it probably because of move selection not finding viable solutions.

Timefold Solver finds a near-optimal solution in reasonable time.
For large enough problems, it is impossible to find optimal solution in reasonable time, since that would involve
evaluating every possible solution, which is often an incomprehensibly large number.
For example, for course timetabling, with 434 lessons, 25 timeslots and 20 rooms, the search space is 10^1171, which is significantly larger than the estimated number of atoms in the observable universe.

Move selection determines how Timefold Solver navigate between solutions.
You can read about local search to get a better understanding of the algorithms used, and read how to configure
move selectors so better moves are picked.
By default, only change and swap moves are used in local search.

Additionally, there may be score traps in how you defined your constraints, which means it takes several moves to
change/improve the score.

As for your questions:

• Am I using the termination limits in a logical way?

  Yes

• Are there other config settings (termination or otherwise) I should be looking at?

  Move selection and local search

• My environment-mode is REPRODUCIBLE, largely because I was uncertain of the impact of NON_REPRODUCIBLE, and the documentation only describes it as "slightly faster". I think I have worked out any outright bugs in my constraints, so maybe I should go with NON_REPRODUCIBLE? Maybe even it would be desirable, as it would allow for different directions of exploration.

  There is extremely little performance benefit from NON_REPRODUCIBLE; I personally do not recommend it.