Originally posted by: SystemAdmin

[ramy said:]

Hi,

I participated to your latest web seminar on CP Optimizer, and, as a beginner, i have a few questions for which I havent found answers yet :

- The "search phase" seems like a powerful tool, but I didn't quite understand how and when that works. What are the user's tasks to have it perform nicely?

- What is the difference between "automatic search" & "search phase"?

- are "restarts", "mulipoint" and "depth-first" options for search?

Thank you very much for your help...

ramy
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[shaw said:]

Hello,

Thank you for attending the webinar - I hope you found it useful.

The most common use of a search phase is to tell the search process
which variable to concentrate on when it comes to instantiating.  Very
often in modelling, quite a number of variables in the model are
so-called "auxiliary" or "helper" variables whose values are computed
(via constraints) from other more fundamental variables which capture
the structure of the problem.  If you have some domain knowledge
and have a good idea of these fundamental variables, you can indicate
them to the search in a phase.
  There are some more complex uses of phases, such as defining different
groups of decision variables, with their priorities, or even specifiying
preferred orders of instantiation of variables within a group, as well
as their preferred values.

The automatic search is the search process used by CP Optimizer to
find a solution to your problem.  The search phase is a "hint" or
information that you give to the automatic search process to help it
out.

Yes, "restarts", "depth-first" and "multipoint" are options for the
"search-type" parameter.  This is a parameter which controls the
search at a very high level and determines which of three very
different approaches are tried.  Each can use a search phase to influence
their behaviour.

I hope his information has been useful,


Paul
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[Philippe Refalo said:]

Hi Ramy,

Here are a few more information to complete Paul answer.

Ilog CP optimizer integrates an automatic search. This means that you can just
model the problem and call

    cp.solve()

to find solutions. Search phases provide a simple way to help this automatic
search by injecting some additional information.

For instance if, from your knowledge about the problem, you consider that some
variables (x) are more important (or more blocking) than others, you might want
to start by giving a value to x variables first. For this purpose, you can write
(in C++)

    cp.solve(IloSearchPhase(env, x));

You can also write

    IloSearchPhaseArray phaseArray(env);
    phaseArray.add(IloSearchPhase(env, x));
    phaseArray.add(IloSearchPhase(env, y));
    cp.solve(phaseArray);

to tell the automatic search to give a value to x variables first, then to y
variables and finaly to the remaining variables if any.

You can also specify the way the variables and the values are selected.
For instance the code

    cp.solve(IloSearchPhase(env, x, IloSelectSmallest(IloExplicitVarEval(env, x, cost)),
                                    IloSelectSmallest(IloValue(env))));

will instantiate the variables x before any other. It will also choose
first the variable with the smallest cost (cost values are given in the array
"cost") and it will give first the smallest possible value to the selected variable.

There is a set of predefined selectors that are available in CP Optimizer but
you can write you own selector in C++ if needed.

These phases are going to be used in certains steps of the automatic search. Restart
search (the default) restart the search from time to time with some extra information
learned from the previous runs. MultiPoint generates a set of solutions and combines
them to find better ones. Finaly DepthFirst is a regular depth-first search that is
mainly used for observing or debugging the search phases.

Regards
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[ramy said:]

Thank you very much for your quickk and helpful replies. It's much clearer now.

I still have two remaining question :

- If I did understood well, "Restarts" and "MultiPoint" are heuristics, while "Depth-first" is an exact method.
I can conclude that "depth-first" is more adapted for small problems. But, how to choose between "restarts" and "multipoint" in bigger problems?

- How do you ask search phase to concentrate on a known value of the decision variable ? For example, let's suppose that the decision variable is a matrix, where x[i,j] is a function of x[k,l]. If I have knowledge of one value in this matrix (-> constraint x[i,j]==constant), how do I direct search phase towards this knowledge??

Thank you very much for your help!
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[Philippe Refalo said:]

Ramy,

It is difficult to predict what will be the best method. It depends on the problem. Restart is closer
to depth-first search. It is more systematic (it can prove optimality). MultiPoint search concentrates
on finding good solutions. You need to try and see.

You can concentrate on a value for decision variables by using the IloExplicitValueEval evaluator.
Suppose that the domain of the variables is [1, ... 5]. If you want to select 3 first then 1 and
then the other values, you can setup priorities on values using the following evaluator:

IloExplicitValueEval e(env, IloIntArray(env, 5, 1, 2, 3, 4, 5), IloIntArray(env, 5, 1, 0, 2, 0, 0));

and add the following selector to the phase:

IloSelectLargest(e);

It will selected first the value 3 because it has the largest evaluation(2), then 1 if 3 is
not in the domain and so on.

If you want the priorities to change depending on each variable then you need to write
your own chooser by subclassing IloIntValueChooserI.

Regards,

#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[ramy said:]

Thank you very much for all the information!! I will try and see by myself now...

#CPOptimizer
#DecisionOptimization

Originally posted by: sds_rohit

Hi Philippe,

"If you want the priorities to change depending on each variable then you need to write
your own chooser by subclassing IloIntValueChooserI."

Actually, I have a situation like that where I have a Variable Array named "Player" and have following requirement :-

a) I want to give different priority to the Player[i] - which is a variable ordering.

b) I want to give different priority to the domain value for each of the Player[i].

Please help. I have been searching for examples of implementation of "IloIntValueChooserI" but couldnt find one.

I would be grateful if you could elaborate more or show/direct me to an example.
#CPOptimizer
#DecisionOptimization