Parallel search problem in CP-SAT solver

[gerry gan]

Hi,

I'm fairly new to or-tools, and trying to use it to solve some of our project problems these days. My question is as follows. I used CP-SAT solver (Python API) to solve a job scheduling problem with single thread. With some simple data as input, it takes roughly 18 seconds (wall time) to find the optimal solution. This experiment is repeated 10 times and the used wall time is quite stable, that is around 18 seconds in each run.

Then  I changed the solver parameter, set solver.parameters.num_search_workers = 4. This will enable 4 threads during a search according to my current understanding. With the same input data as above and running this experiement 10 times, however, gives me some unexpected performance results. The used wall time varies quite a bit in these 10 runs. The fastest run uses about 16 seconds and the slowest run uses roughly 21 seconds. This also means that some run with multi-thread enabled actually performs worse than single threaded case above.

According to the release notes of July 2018, it says: Parallel search: Use the SatParameters.num_search_workers option to enable multiple threads during a search. Each thread can have different parameters, and different random seeds. This maximizes diversity, and the probability that at least one thread will find solutions.

Thus, my question is whether multi-thread is just to maximize the probability for at least one thread to find solution to the problem. Could multi-thread speed-up the search procedure? In addition, I have only used or-tools for some weeks, so I'm not sure if the above setting of the parameter num_search_workers is the only thing I need to add to enable the full capability of multi-threading. Am I missing something?

Basically, I just used some simple data as input to the above job scheduling problem. The actual amount of input data is much larger. I tried to run it in single thread once and it can only find FEASIBLE solution after one hour. Then I come up with the idea to use parallel search in the hope that it could speed-up the search. But my current experiment seems not to be very promising. Could anybody please provide some insights about this issue? Thanks in advance!

Best regards,

Gerry    

[Laurent Perron]

Currently, parallel search is not deterministic. We will make it deterministic in the future, but it will degrade performance.

For best performance, I would use 8 threads. To have speedup, you do need 8 cores, otherwise other threads will slow down the lucky one that will find a good solution.

In parallelism, everything is possible, speedup, slowdown,... On our experiments, the standard behavior is a large performance gain. I guess you are unlucky.

If you could share the code, I can experiment on my side.

Thanks

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

--Laurent

[gerry gan]

Hi Laurent,

Thanks for your response. My code is enclosed as an attachment. Basically, it is just the flexible job shop sample code, nothing special. My machine only has 4 cores, so I only tested the case with 4 threads. With this script, it can only give me FEASIBLE solution after running about one hour on my local machine (we need OPTIMAL if possible). 

The main problem, according to my current study and guess, lies in the input data. In my case, the task duration is measured in seconds and it is usually several hundred seconds for one task. I find out that this affects the performance quite much since for example the start/end variable then could take many more possible values compared to the situation where tasks have relatively short duration. Based on this, actually, I'm not very sure now if multi-thread is a good candidate solution to this problem. If the task duration is short, like 4 or 5 seconds, actually, the performance is not a problem at all. Is there any methodology that can cope with this kind of large task duration problem? 

Thanks and best regards,

Xiang       

[Frederic Didier]

If you have such long duration, you should probably change your time measurement unit, and say measure everything in integer multiple of 10s or even 1min.

You loose a bit of precision, but if you can prove the optimal on this approximated version, there is a good chance you will get a really good solution when you keep the same order but use the exact timing.

--

[Laurent Perron]

I have added a little search heuristics

    # Search heuristics

    model.AddDecisionStrategy(

        task_starts, cp_model.CHOOSE_LOWEST_MIN, cp_model.SELECT_MIN_VALUE)

task_starts is the list of all task master start variables.

It finds the optimal solution is 0.1s with 1 thread now.

I will see if I can improve the model to prove optimality.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Laurent Perron]

I attach an updated version of the problem which does some energetic reasoning.

It solves the problem trivially in 0.1s

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[gerry gan]

Hi,

So after reading the updated code snippet, I guess the core idea is to provide an improved potential lower bound for the makespan. By this means, it dramatically reduces the search space since the improved lower bound is the best one could get according to the input data.

Thank you (especially to Laurent) for all the comments and code snippet provided to my problem. It is really beneficial for me to have questions discussed in this forum which makes me learn to solve problem from different points of view.

Best regards,

Gerry