Originally posted by: jeffti

Hi people,

after several months trying to solve my scenario using CPlex i decided change my view and try another modeling way. CP seems ideal for my problem, except when i have conflicts.

Currently in CPlex i have a huge quantity of binary variables to control resource usage making my problem impossible to be solved. Modeling in CP my problem became simple but still impossible.

Is there any other way to model this efficiently? Another technique or functions, both noOverlap and cumulFunctions seems to be expensive.

Problem header:

! ----------------------------------------------------------------------------
! Minimization problem - 135.668 variables, 134.822 constraints
! Presolve : 134.482 extractables eliminated
! Initial process time : 0,50s (0,00s extraction + 0,50s propagation)
! . Log search space : 2.121.523,6 (before), 2.121.523,6 (after)
! . Memory usage : 660,0 MB (before), 741,7 MB (after)
! . Variables fixed : 4
! Using parallel search with 8 workers.

Thanks in advance,

Jefferson Soares Biernastki

Originally posted by: PhilippeLaborie

Hello,

The problem is indeed very challenging because even finding a feasible solution is far from being trivial due to the hard synchronization constraints (startAtEnd) of the activities on each route and the fact the start time of each route is fixed. And the problem is not small (about 68000 activities).

I think your CP Optimizer model makes sense. You can improve it in a few ways:

1- You can directly use the notion of precedence constraint in the engine (startAtEnd(...)) instead of the equality constraints startOf(...)==endOf(...). This will not have much impact on the performances on this model because CP Optimizer is able to reformulate these constraints by itself but in general it is better to use precedence constraints.

2- For such a large problem and especially when a big part of the effort is spend at finding a feasible solution, you can use a single worker instead of the (default) fully parallel search. So setting cp.param.Workers=1.

3- On your model you can reduce the number of interval variables by using the notion of transition distance in the noOverlap constraint, this way you can get rid of the workCleanup interval variables and define a constant transition distance instead. It will reduce the number of variables by a factor 2 and should not impact the propagation strength very much.

4- Concerning propagation, given the hard synchronization constraints (startAtEnd) of the activities on each route, it may be interesting to try using a stronger inference than the default on the noOverlap constraints, for instance cp.param.NoOverlapInferenceLevel = "Extended". This will slow down the propagation at each search node but will results in less nodes being explored.

5- You could reformulate the objective function to have less terms in the sum and a faster and stronger pruning by using the end time of each route which is equal to the sum of the duration of the activities in the route.

I tried the 5 points above in the attached modified version of your model. CP Optimizer is able to find a feasible solution in about 15mn and then is able to improve it ... but given the size of the problem, it takes some time.

Hope it helps,

Philippe