Is it possible (and if yes, how?) to only allow CP Optimizer to backtrack on certain variables once all variables are fixed?
I am working on a problem in which there are may be many feasible solutions, but I need to minimize a certain lateness variable. I know that once a feasible (but nonoptimal) solution is found, it doesn't make sense to explore certain "neighbouring" solutions because they can't lead to a better lateness, so I want to restrict the search to a known subset of variables until a better lateness is found.
Is this possible, or am I missing something and this could be expressed in a "normal" constraint or propagator function?
Thanks!
Topic
This topic has been locked.
3 replies
Latest Post
 20121114T14:10:54Z by GGR
ACCEPTED ANSWER
Pinned topic Allowing backtracking only on certain variables
20121109T14:17:01Z

Answered question
This question has been answered.
Unanswered question
This question has not been answered yet.
Updated on 20121114T14:10:54Z at 20121114T14:10:54Z by GGR

ACCEPTED ANSWER
Re: Allowing backtracking only on certain variables
20121109T17:30:14Z in response to SystemAdminHi
CP Optimizer is primary a model and automatic work solver. That means
1) you cannot apply your idea without reimplementing the search. That is possible in C++ but you will loose the advantages of the automatic search
2) What you propose looks like a dynamic dominance rule. Anyway, may be you can translate in constraint that breaks the symmetries, for example in your case nogood afffectations. It usually use constraint on constraint
3) It is quite very possible that in your case, the optimization procedure takes no advantage at all of your behavior for proving optimality. Note that, you speak of <<lateness>> which mean you have a temporal problem. May be a temporal model (using interval variables) as decision variable could help.
4) Did you try search phase of the dominant variables. That is the variables on which you want the backtrack happens (i.e. the decisions are taken). The search phase notion is a quite simple and versatile to control the decision. In C++, you can do more thing than in other languages.
5) You can also break the symmetry from outside. That is stop the search on an incumbent. Update the model with the breaking symmetry or <<not in neighborhood>> constraint and then relaunch the solve with the incumbent at starting point.
Hope that helps
ACCEPTED ANSWER
Re: Allowing backtracking only on certain variables
20121109T21:12:47Z in response to GGRThanks GGR, that's an excellent answer.
There are a couple things I don't quite understand: what do you mean by nogood affectations and "constraint on constraint"?
I'll try out the search phase functions, they look promising. I'll get back to you and mark the thread as solved once I have some results. Thanks again!
ACCEPTED ANSWER
Re: Allowing backtracking only on certain variables
20121114T14:10:54Z in response to SystemAdminHi
In CPO as well as many other constraint solver, you can regard constraint as Boolean expressions and used it to add conditions on theses expression. For example, in OPL suppose x and y is are integer variables, the constraints
lor(x < 5, x > 8); (x < 3) => (y < 8); (x < 2) + (y > 3) == 1;
told that in a solution
 Either x is less than 5, either x greater than 8
 if x greater than 3 then y less than 8
 at least one and at most of the two constraint (x < 2) and (y > 3) is verified in a solution (exclusive disjunction)
Constraint on constraint are also called meta constraint in CPO. Not all constraint are allowed to be used in meta constraint. For example global constraint like affDifferent and the constraint in scheduling cannot be used in in meta constraint. The documentation specifies it
Hope that helps Either x is less than 5, either x greater than 8
 if x greater than 3 then y less than 8
 at least one and at most of the two constraint (x < 2) and (y > 3) is verified in a solution (exclusive disjunction)
Constraint on constraint are also called meta constraint in CPO. Not all constraint are allowed to be used in meta constraint. For example global constraint like affDifferent and the constraint in scheduling cannot be used in in meta constraint. The documentation specifies it
Hope that helps

