Is there efficient way to estimate the runtime when X variables changes in cpSolver

[YINXIONG CHEN]

Dear all, 

I created a cpmodel and cpsolver model to solve job scheduling problem. When the number of variables increase, it takes at least 30 mins for the solver to output a good enough solution (Let's assume score 10 is the optimal solution, good enough solution has score 7). 

I want to perform an experiment to evaluate what is the MAX limit of #variables that can get a score 9 solution from the solution. I have my own way to evaluate the score of the solution.

Below are the elements to determine the #variables in the model.

• Number of jobs
• Number of workers
• Number of the job locations

The most straightforward way is simply define range for every element, and iterate every combinations. But when the #variables increase, it will take 3-4 hours to have a score 9 solution in single run. It is very time consuming. 

Is there any efficient way to perform this exercise? Thanks. 

[Priidik Vilumaa]

Depending on your exact needs, wouldn't a valid question be " what is the MAX limit of #variables that can get a score 9 solution from the solution in a given time limit"? Set a reasonable time limit and run your experiment in a binary search style - instead of just iterating through the range, do a more intelligent increase/decrease in the number of jobs/workers/what-have-you. For example, if you successfully get your score 9 in some run, then next double the number of "jobs", if that fails, then go to the halfway point between last successful and last unsuccessful. Note that you can stop early if you continuously evaluate the solutions and find a 7+ even if it's more difficult to evaluate than just your objective function.

But I think the consensus is that it's not just the number of variables/constraints that make a model difficult to solver. It's also the tightness of the constraints and variable bounds and what not. Small details can affect the runtime to a large extent. 

Best,

Priidik