Topic
  • 3 replies
  • Latest Post - ‏2012-11-14T14:10:54Z by GGR
SystemAdmin
SystemAdmin
554 Posts

Pinned topic Allowing backtracking only on certain variables

‏2012-11-09T14:17:01Z |
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 non-optimal) 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!
Updated on 2012-11-14T14:10:54Z at 2012-11-14T14:10:54Z by GGR
  • GGR
    GGR
    62 Posts

    Re: Allowing backtracking only on certain variables

    ‏2012-11-09T17:30:14Z  
    Hi

    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 no-good 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
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: Allowing backtracking only on certain variables

    ‏2012-11-09T21:12:47Z  
    • GGR
    • ‏2012-11-09T17:30:14Z
    Hi

    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 no-good 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
    Thanks GGR, that's an excellent answer.

    There are a couple things I don't quite understand: what do you mean by no-good 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!
  • GGR
    GGR
    62 Posts

    Re: Allowing backtracking only on certain variables

    ‏2012-11-14T14:10:54Z  
    Thanks GGR, that's an excellent answer.

    There are a couple things I don't quite understand: what do you mean by no-good 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!
    Hi

    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