Originally posted by: AlCPLEX

Hello,

After doing some models and trying to tune them, i was wondering what the best methodology was.

i already tried to use these concepts in my modelling:
- slicing
- minimizing number of variables and their domains
- using global constraints
- setting search phases
- changing some parameters in option files (propagation level,workers,...)

But it is often a trial and error procedure that has so many parameters that it can take some time.

In case where the profiler cannot help because most of the time is spent in categories "CP search" & CP "Improve Solution", what is the best way to proceed in order to improve the speed performances?

Thank you very much for your help.

Sincerely

Originally posted by: PhilippeLaborie

Hello Alexis,
The profiler (I suppose you mention the profiler in the OPL IDE) will help you to determine if most of the time is spent in the management of the OPL model (data manipulation, model creation) or inside the engine resolution. Most of the time, the bottleneck is in the resolution by the engine, and in this case, you should mostly look at the CP Optimizer search log to see what happens. It can take a long time (1) for extracting and pre-solving the model, (2) at initial propagation at the root node, (3) because propagation at each search node is slow, (4) because the search has difficulty finding an initial feasible solution, (5) because the search starts from a very bad solution and/or improves the objective function very slowly, (6) because you are expecting a proof of optimality and it takes very long before the search can provide it. Looking at the search log, you can identify the main bottlenecks among the ones listed above. And you should always start with improving the model itself (before thinking of propagation levels, search phases, etc.). Some general rules (but there are exceptions of course):

• Always prefer using global constraints when possible instead of composite constraints
• Quite often in CP models, the size of the model (number of variables, number of constraints) is linear with the size of the data. If this is not the case, think of alternative models (different choice of variables, better exploitation of global constraints, ...)
• Try to factorize elements of the model as much as possible (for instance, if the same variable appears twice in an expression or a constraint, it may be possible to better formulate the expression/constraint)
• In case you suspect the individual propagation of some constraints to be quite loose, consider adding more global redundant constraints
• Symmetries in the model are two-sided coins: on one side, removing symmetries usually improves optimality proofs (it reduces the size of the search space), on the other side it can make it more difficult to produce feasible solutions or improve solutions (it decreases connectivity of the search space)
• Sometimes, due to the expressivity of CP, one is inclined to add too much detail in the model. The designer of the model should always keep in mind that sources of complexity do not add up, they multiply. The model should stay focused on the variables, constraints and objectives that are the most important for the solution quality. Especially in complex problems, second-order details and decoration should be moved to a post-processing phase or a second stage of resolution.

Using a sequential search (Workers=1) with a small log period (typically LogPeriod=1) will display in the search log useful information about the search (in which order variables are fixed).

A very important thing to do is to always evaluate model improvements using different instances and/or different random seeds. If you consider a single instance / random seed, a particular change in the model may produce better/worse solution only by chance, leading to some over-tuning.

CP Optimizer will not always stop with optimality proofs in a reasonable amount of time, do not forget to add a time limit for the search!

After playing with the model, the next things to consider are :

• Propagation levels
• Search phases (when you suspects it makes sense to fix some decision variables before other ones)
• Exploiting starting points to solve the problem in different stages (example: a first model for finding an initial feasible solution in case of hard feasibility problems, followed by a second stage to optimize the most important objectives, followed by a last stage to polish the solution). Starting points and multi-stage resolution are often the key to solve complex problems.
• Use Multi-Point search instead of the default search type.

But indeed, there is no such a thing like a simple recipe that you could apply and will always work. Modeling combinatorial optimization problems is still an art ...

Originally posted by: AlCPLEX

Thank you very much of your exhaustive answer.

Ill try to dig in more into the search log to see if i can find some pattern/ the level where the most fails happend.

Maybe some automated information on it could be usefull? Like the number of fails on each decision variable assignement?

Thanks,

Sincerely.

Originally posted by: rakesh85

from docplex.cp.model import *
import numpy as np

mdl = CpoModel(name="Propagation testing")

# Variables of the model
x={}
x[1] = integer_var([1,2,3,4])
x[2] = integer_var([1,2,3,4,5])

#constraints

mdl.add(x[1]+x[2] >3)

mdl.add(x[1]>x[2])

msol= mdl.propagate(DefaultInferenceLevel='Extended', ElementInferenceLevel='Extended')

When I propagate this Model, then I get the domain of X[1]= {2,3,4} and domain of x[2] to be {1,2,3}. Howeever, the domain of X[1] should be only {3,4}. I don't understand why the domain reduction is not effective for this very simple problem.