1
$\begingroup$

I stumbled upon this video while using OR-Tools CP-SAT solver

https://www.youtube.com/watch?v=lmy1ddn4cyw

At around 12:10, the part of multithreaded solvers starts. I understand these solvers are distributed among the available cores (threads) of a CPU. At around 13:20, there is a slide of information shared among these workers / solvers.

It displays

• Propogate new variable bounds

  • Including fixed variables
  • Including literals
  • Including objective

Q: does this mean that, assuming 8 workers, when a worker, say the solver at thread 0, finds a new better solution, it informs threads 1-7, which subsequently use this as an upper bound for their new solutions' objective value?

In addition, what other examples of information are shared that make this parallel computing "work"? E.g. fixed variables?

$\endgroup$

1 Answer 1

2
$\begingroup$

If you enable logging (parameter log_search_progress:true), the solver displays these stats at the end of the log:

Solutions (2)         Num   Rank        
            'fixed':    1  [2,2]                   
  'fj_long_default':    1  [1,1]   

Objective bounds          Num                                                                          
       'initial_domain':    1                                                                          
  'objective_lb_search':    1                                                                          
                                                                                                       
Solution repositories    Added  Queried  Ignored  Synchro            
  'feasible solutions':     14      373        0       13            
        'lp solutions':      2       13        0        2            
                'pump':     24       12                                                                
                                                                                                       
Improving bounds shared    Num                                                                         
            'default_lp':    1                                                                         
                 'fixed':    9                                                                         
   'objective_lb_search':   80                                                                         
               'probing':   75                                                                         
         'quick_restart':  200                                                                         
   'quick_restart_no_lp':  155                                                                         
                                                                                                       
Clauses shared            Num                                                                          
           'default_lp':   15                                                                          
                'fixed':    9                                                                          
                'no_lp':    2                                                                          
  'objective_lb_search':   39                                                                          
              'probing':   31                                                                          
         'pseudo_costs':    4                                                                          
        'quick_restart':   12                                                                          
  'quick_restart_no_lp':    6                                                                          
        'reduced_costs':    2

Here is what it shows:

  • solutions : solutions found by workers. They are used by LNS workers, LS workers and the incumbent value is used by all workers.
  • objective bounds : an improving lower bound of the objective (when minimizing).
  • lp solutions and pump : These are LP values for each variables created either during search (when the simplex finds a optimal relaxed solution), and by the feasibility pump worker. Can are used by the RINS and RENS LNS workers.
  • improving bounds shared : These are shared among workers. They represent reduced domains, and fixed variables.
  • clauses shared : These are root node binary clauses learned by workers. They are shared among workers.

There are subtleties all around (LNS workers cannot prove anything beyond finding a new solution, so they can only import information). But this is the gist of it.

We also share the basic state of the global search like termination.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.