Originally posted by: SatishKumarA

Hi All,

I am trying to find out how search space is being calculated by CP Optimizer. I got the following engine log for my CP problem

 ! ----------------------------------------------------------------------------
 ! Minimization problem - 497 variables, 1,250 constraints, 4 phases
 ! Presolve      : 108 extractables eliminated, 105 constraints generated
 ! Workers              = 1
 ! RelativeOptimalityTolerance = 0.5
 ! TimeLimit            = 100
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 795.8 (before), 795.8 (after)
 !  . Memory usage      : 2.9 MB (before), 2.9 MB (after)
 ! Using sequential search.
 ! ----------------------------------------------------------------------------

As per the engine log explanation in the documentation: "The value for  "Log search space" provides an estimate on the size of the depth-first search tree; this value is the log (base 2) of the products of the domains sizes of all the decision variables of the problem".

When I calculated the log search space for my problem it is coming to around 46.46 whereas CPO is showing it as 795.8(highlighted). I have six group of variables and following table lists the the domain and variables of my problem with the search space (domain*variables)

 Total Search Space =  9.74267E+13  and Log Search Space = 46.47

I would like to reduce this search space of my problem. Can anyone help me to understand the calculation of search space and how CPO came out with log search space as 795.8?

Originally posted by: Philippe_Refalo

Hi SatishKumarA

If you consider variables of type 2 you have a theoretical search space of 13 ^ 84 (13 to the power of 84) whose log base 2 is about 310. Summing up all these you can get to about 860. This is higher than what CPO reports but constraint propagation and presolve simplifications can have reduced the search space. 

Philippe

Originally posted by: SatishKumarA

Thanks for the reply Phillippe

Now I could understand how the search space is calculated.

I did the calculations for all the variables mentioned in the above table and log search space came to 870.  And when I ran the problem with presolve off setting, it came up with 5667.8 as the log search space.

! ----------------------------------------------------------------------------
 ! Minimization problem - 497 variables, 1,418 constraints, 4 phases
 ! Workers              = 2
 ! Presolve             = Off
 ! RelativeOptimalityTolerance = 0.1
 ! TimeLimit            = 100
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 5,667.8 (before), 795.8 (after)
 !  . Memory usage      : 3.4 MB (before), 3.9 MB (after)
 ! Using parallel search with 2 workers.
 ! ----------------------------------------------------------------------------

What could be the explanation for this ?
 

Originally posted by: Philippe_Refalo

It's difficult to say, we would need to see the model. In some circumstances we can create additional variables after extraction but they are not counted as they are auxiliary. A possibility is that you have more variables than you think in your model, variables without a domain have a domain ranging from -IloIntMax to IloIntMax. So if you have no clue, please send us the source creating the model or a .cpo file. 

Philippe

Originally posted by: SatishKumarA

Hi Philippe,

Can you please share your email-id ?

Thanks,

Satish

Originally posted by: Philippe_Refalo

My e-mail address is available in my profile now.

Philippe