Originally posted by: Petr Vilím
Hello,
the first few solutions CP Optimizer finds are quite far from the optimum. CP Optimizer uses Large Neighborhood Search (LNS) to improve those solutions. As they are far from optimum it takes some time. The problem is large and so every iteration of LNS also takes some time.
You can force CP Optimizer to look directly for optimal solution by forcing the objective to be zero (as a constraint in the model). Then optimal solution is found quite quickly (in 16s on my laptop). It works well on this particular instance but may not work on other instances (where optimal value is not zero). Note that for problems of this size finding optimal solution is not usual. Your problem is an exception since once the solution is found proving its optimality is trivial. When optimal value is not zero then the optimality proof is much harder, especially considering the problem size.
Another possibility is to force CP Optimizer to cut the objective more aggressively. In particular there is parameter RelativeOptimalityTolerance. Increasing its value to e.g. 0.5 also improves the speed (however you may get sub-optimal solution in the end however unlikely in the case when optimal value is 0).
Yet another strategy would be to start with an aggressive objective cut added as a constraint into the model. Try to solve this model with a small time limit. If a solution is not found then relax this cut, otherwise get the solution and restart the solve with the solution as starting point (this way CP Optimizer does not have to find the solution again). There are many variants of this approach.
Note that before sticking to any of this strategy, test it on multiple instances. Because this particular instance seems to be exceptional (but I can be wrong).
Best regards, Petr
#CPOptimizer#DecisionOptimization