By 1% of optimal, I was giving an example percentage to clarify there are solutions that exists, that are almost as good as optimal, that can be found in reasonable amount of time.
There cannot be a guarantee to find a solution to a given percentage worse than optimal for a fully general problem, since you would need to know optimal to give such a guarantee (and since the problem fully general, you cannot use the structure of the problem to reduce it).
Most constraint problems have many feasible solutions, and have a way to judge how much worse or better one solution is to another.
There are good and bad way to write constraints.
One bad way to write constraints is score traps, where between one clearly better solution has the same score as a clearly worse solution.
For example, for shift scheduling, a solution with only 1 overlapping shift with the same employee is better than a solution with 2 overlapping shifts with the same employee.
A bad score function would penalize both solutions by 1, meaning a solver have no idea which of the two solutions are better.
A good score function would penalize the schedule with 1 overlapping shift with the same employee by 1, and the schedule with 2 overlapping shifts with the same employee by 2.
The class of problems I am talking about is the class of problems where you can assign a score to a possible solution, with limited score traps.
Timefold has no guarantees about finding a solution in reasonable time (but unless you done something terribly wrong or have a truly massive dataset, it finds a good solution really quickly 99.99% of the time). Instead, you set the termination condition of the solver; it could be time-based (say 60 minutes), unimproved time spent (solve until no new better solutions are found after 60 minutes), or the first feasible solution (there are other termination conditions that can be set).