Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
3 replies Latest Post - ‏2012-11-14T14:10:54Z by GGR
SystemAdmin
SystemAdmin
554 Posts
ACCEPTED ANSWER

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
    56 Posts
    ACCEPTED ANSWER

    Re: Allowing backtracking only on certain variables

    ‏2012-11-09T17:30:14Z  in response to SystemAdmin
    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
      ACCEPTED ANSWER

      Re: Allowing backtracking only on certain variables

      ‏2012-11-09T21:12:47Z  in response to GGR
      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
        56 Posts
        ACCEPTED ANSWER

        Re: Allowing backtracking only on certain variables

        ‏2012-11-14T14:10:54Z  in response to SystemAdmin
        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