Originally posted by: legraina

Dear Forum,

I'm coding a VRP with CPO using IloIntVar. I've an issue with the travel times constraints.

Let dep[i] be the departing time of node i, succ[i] the successors of i, and d[i][j] the travel time from i to j.

This is the travel time constraints:  IloElement(dep, succ[i]) - dep[i] - IloElement(d[i], succ[i]) >= 0;

The issue is with the size of the domain. dep has a very big domain and it's not possible to reduce it. It seems that cp is propagating these constraints many times, thus slowing extremely the resolution process: 45 branches in 10s ....  I have pasted the log below. I would like to modify the priority of these constraints to be checked the fewest times possible at each node. Would I be force to code my own constraint ?

Thank you very much,

Antoine

! ----------------------------------------------------------------------------
 ! Satisfiability problem - 19 variables, 8 constraints
 ! LogVerbosity         = Verbose
 ! LogPeriod            = 1
 ! Workers              = 4
 ! TimeLimit            = 10
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 128.4 (before), 128.4 (after)
 !  . Memory usage      : 546.4 kB (before), 546.4 kB (after)
 ! Using parallel search with 4 workers.
 ! ----------------------------------------------------------------------------
 ! ----------------------------------------------------------------------------
 ! Search terminated by limit, 1 solution found.
 ! Number of branches     : 45
 ! Number of fails        : 13
 ! Total memory usage     : 3.0 MB (3.0 MB CP Optimizer + 0.1 MB Concert)
 ! Time spent in solve    : 10.00s (10.00s engine + 0.00s extraction)
 ! Search speed (br. / s) : 4.5
 ! ----------------------------------------------------------------------------
Number of branches      : 45
Number of fails         : 13
Number of choice points : 41
Number of variables     : 25
Number of constraints   : 10
Total memory usage      : 3.0 MB (3.0 MB CP + 0.1 MB Concert)
Time in last solve      : 10.00s (10.00s engine + 0.00s extraction)
Total time spent in CP  : 10.00s

Originally posted by: ChrisBr

Hello Antoine,

Could you tell us which version of CP Optimizer you are using please?

Regards,

Chris.

Originally posted by: legraina

The latest, sorry (12.6.3)

Originally posted by: legraina

The problem is with the parallelization of CPO. With one worker, there is absolutely no issue.

! ----------------------------------------------------------------------------
 ! Satisfiability problem - 19 variables, 13 constraints
 ! LogVerbosity         = Verbose
 ! LogPeriod            = 1
 ! Workers              = 1
 ! TimeLimit            = 10
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 128.4 (before), 128.4 (after)
 !  . Memory usage      : 525.9 kB (before), 525.9 kB (after)
 ! Using sequential search.
 ! ----------------------------------------------------------------------------
 ! ----------------------------------------------------------------------------
 ! Search terminated normally, 1 solution found.
 ! Number of branches     : 5
 ! Number of fails        : 0
 ! Total memory usage     : 674.2 kB (622.0 kB CP Optimizer + 52.1 kB Concert)
 ! Time spent in solve    : 0.00s (0.00s engine + 0.00s extraction)
 ! Search speed (br. / s) : 500.0
 ! ----------------------------------------------------------------------------
Number of branches      : 5
Number of fails         : 0
Number of choice points : 7
Number of variables     : 25
Number of constraints   : 13
Total memory usage      : 674.2 kB (622.0 kB CP + 52.1 kB Concert)
Time in last solve      : 0.00s (0.00s engine + 0.00s extraction)
Total time spent in CP  : 0.00s

Originally posted by: legraina

Sorry, but the same problem remains on a bigger instance:

 ! ----------------------------------------------------------------------------
 ! Satisfiability problem - 486 variables, 417 constraints, 2 phases
 ! LogVerbosity         = Verbose
 ! LogPeriod            = 1
 ! Workers              = 1
 ! TimeLimit            = 30
 ! Initial process time : 0.01s (0.01s extraction + 0.00s propagation)
 !  . Log search space  : 6977.7 (before), 6977.6 (after)
 !  . Memory usage      : 6.8 MB (before), 6.8 MB (after)
 ! Using sequential search.
 ! ----------------------------------------------------------------------------
 ! ----------------------------------------------------------------------------
 ! Search terminated by limit, no solution found.
 ! Number of branches     : 122
 ! Number of fails        : 4
 ! Total memory usage     : 8.5 MB (7.7 MB CP Optimizer + 0.8 MB Concert)
 ! Time spent in solve    : 30.00s (29.98s engine + 0.01s extraction)
 ! Search speed (br. / s) : 4.1
 ! ----------------------------------------------------------------------------
Number of branches      : 122
Number of fails         : 4
Number of choice points : 120
Number of variables     : 944
Number of constraints   : 0
Total memory usage      : 8.5 MB (7.7 MB CP + 0.8 MB Concert)
Time in last solve      : 30.00s (29.98s engine + 0.01s extraction)
Total time spent in CP  : 30.00s

Originally posted by: legraina

I've finally found why this is happening.

These constraints should eliminate the sub-tours, but they are not efficient. Indeed, without sub-tours elimination constraints, the propagation cycles many times in these constraints to reach the infeasibility (especially with big domain).