Topic
5 replies Latest Post - ‏2013-10-23T15:22:51Z by HWFN_Hossein_Hojabri
HWFN_Hossein_Hojabri
19 Posts
ACCEPTED ANSWER

Pinned topic limited Discrepancy Search

‏2013-08-19T17:20:35Z |

Hi everybody,

 

I need to use Limited Discrepancy Search in my work as in Shaw (1998). I was said that I can implement it through some functions already developed in CP Optimizer under the title of Slice-based search. I searched the User's manual, but came across with nothing. I'd appreciate if you could help me out with this.

 

Best,

Hossein 

  • Paul Shaw
    Paul Shaw
    6 Posts
    ACCEPTED ANSWER

    Re: limited Discrepancy Search

    ‏2013-08-21T16:23:34Z  in response to HWFN_Hossein_Hojabri

    Hello Hossein,

    There are no goal modifiers that allow you to do this in CP Optimizer, but it is quite easy to code Slice-based Search using the goal primitives in CP Optimizer.  I've enclosed a code which does this - you just need to edit it for your case where the comments tell you (variable and value selection).  What is important to decide is how a discrepancy is counted if your search tree has n-way branching rather than 2-way branching.  In the code below, the kth best decision (counting from 0) at a node counts as k discrepancies.  You might want to revise that.  Note also that this code assumes that the maximum number of discrepancies specified to MyLDSGoal will be small compared to the number possible from the domains of the variables (i.e. that needed to perform a complete search).  If this is not the case, depth-first search  would most likely be more efficient anyway.

     

    Regards,

     

    Paul

     

    #include <ilcp/cpext.h>

    ILOSTLBEGIN

    ILCGOAL2(MyGoalPhase, IlcInt, d, IlcIntVarArray, x) {
      // First choose a variable to instantiate.
      // USER INTERVENTION: Replace this with whatever you want.
      IlcInt i = IlcChooseMinSizeInt(x);

      // Goal succeeded?
      if (i < 0)
        return 0;

      // Now choose the best value.
      // USER INTERVENTION: Replace this with whatever you want.
      IlcInt j = x[i].getMin();

      IlcGoal left = IlcAnd(x[i] == j, this);
      if (d == 0) {
        return left;
      }
      else
        return IlcOr(left, IlcAnd(x[i] != j, MyGoalPhase(getCP(), d - 1, x)));
    }

    ILCGOAL3(MyGoalSBS, IlcInt, d, IlcInt, maxD, IlcIntVarArray, x) {
      IloCP cp = getCP();
      if (d > maxD)
        return IlcGoalFail(cp);
      return IlcOr(MyGoalPhase(cp, d, x), MyGoalSBS(cp, d + 1, maxD, x));
    }

    ILOCPGOALWRAPPER2(MyGoalSBS, cp, IloInt, maxD, IloIntVarArray, x) {
      return MyGoalSBS(cp, 0, maxD, cp.getIntVarArray(x));
    }

    int main() {
      IloEnv env;
      IloModel mdl(env);
      IloIntVarArray x(env, 20, 0, 1);
      mdl.add(x);
      IloCP cp(mdl);
      cp.setParameter(IloCP::LogVerbosity, IloCP::Quiet);
      cp.startNewSearch(MyGoalSBS(env, 3, x));
      while (cp.next()) {
        cp.out() << cp.domain(x) << endl;
      }
      env.end();
      return 0;
    }

     

    • HWFN_Hossein_Hojabri
      19 Posts
      ACCEPTED ANSWER

      Re: limited Discrepancy Search

      ‏2013-09-04T16:00:03Z  in response to Paul Shaw

      Dear Paul,

       

      Thank you so much for the complete reply.

       

      Regards,

      Hossein

    • HWFN_Hossein_Hojabri
      19 Posts
      ACCEPTED ANSWER

      Re: limited Discrepancy Search

      ‏2013-10-22T19:53:03Z  in response to Paul Shaw

      Hello again,

       

      I tried to implement LDS, but still have a few problems. So I think I'd better to make sure if my perception of LDS coupled with CP is correct in details. I'd appreciate if you could answer this questions:

       

      - What is the detailed task of CP in LDS? What I think is that once some visit is fixed through LDS, the task of CP is to evaluate the feasibility of that visit being inserted at a position, and to update the domains of all the other variables through propagation. If it is infeasible, then we backtrack trying to insert it at the 2nd best position, 3rd, etc. Is that correct? If so,

      - how could I have CP to only evaluate the feasibility of inserting v at p, without solving the rest of the problem while I get down the search tree from the root to leaves? Should I remove cp.solve()? I suppose that in LDS, the task of fixing visits is for LDS, and not CP. CP's task must be only propagation to prune infeasible, or costly branches which take the lower bound above the upper bound.

       

      Best,

      Hossein

      • Paul Shaw
        Paul Shaw
        6 Posts
        ACCEPTED ANSWER

        Re: limited Discrepancy Search

        ‏2013-10-23T11:33:44Z  in response to HWFN_Hossein_Hojabri

        Hello,

        Perhaps what you are missing is that an iteration of LNS is not the same as solving the whole problem.  When you do an iteration of LNS, you are constraining the problem according to some reference solution (incumbent).  It's hard to talk in generalities, so let's look at a specific example.  You seem to be solving a routing problem, so let's take a TSP.  One model of the TSP associates a "next" variable with each city which says what the next city to be visited will be after the current one.  Now, let's also assume that you have some representation R of the current solution (this can be an integer array in C++, Java or whatever) which holds the values that the "next" variables took in the initial solution found by the solver.

        Next you have to look at how to do an LNS iteration.  Let's assume that you wish to "remove and reinsert" a subset C of all the cities, then you will be solving a constrained version of the original problem.  What does this new problem look like?  Well, suppose that in the current solution R the next city of some city i is j.  In the problem we are about to solve, any subset of C can go in between i and j, so the domain of next[i] in our new sub-problem should be C union j.  In fact this will be the case for every "next" variable - their domains should not be the set of all cities, but a smaller set which is made of the union of set C and its current next city in the incumbent solution R.  With this model, you will probably want to have a better objective value that the solution in R, and so you should also add a constraint to say that you are looking for a better solution.

        Now that this more constrained problem is specified, you can explore its search space in any way you want.  Some sort of discrepancy-based search is one way to do this, and you can base it on the code I already posted.  However, you can also use depth-first search, probably with some randomization and some upper limit on, for example, the number of nodes to explore, or indeed the automatic search of CP Optimizer, probably again with some limit.

        If this search produces a new better solution, it needs to be copied into R for use in subsequence iterations.  Note that the constrainted model that you solve in each iteration is a completely new model, as typically C will be different at each iteration.

         

        I hope this clarifies things for you,

         

        Paul

        • HWFN_Hossein_Hojabri
          19 Posts
          ACCEPTED ANSWER

          Re: limited Discrepancy Search

          ‏2013-10-23T15:22:51Z  in response to Paul Shaw

          Hello,

           

          Thanks a lot for the response. Yes, I'm doing exactly the same in may LNS algorithm. I know how to update domains, the condition on objective to get a better solution, etc.

           

          In fact before adding LDS to my model, the algorithm was using a number of operators to partially destruct the current solution, and then CP to re-optimize it. I mean I hah no LDS, and it was CP's task to re-optimize the new constrained problem at each iteration of LNS.

          However, the problem was that it took so much time in every single iteration to re-fix the new constrained problem in iterations after 100. So I decided to add LDS to be able to have many more iterations in the same runtime, and so it could converge to optimal solution much faster. I posted new questions, because I hesitate about the fact that what are the tasks of LDS and CP at 1 single iteration. How are they distinguished.

           

          What I think is that, according to your paper and codes you posted, LDS does fix the visits (chosen by variable selection algorithm) one by one to the values (chosen by the value selection algorithm and discrepancies). CP's task is to make sure if it's feasible to fix a visit to a position through propagating constraints (time window, load constraints, etc), and reduce the domains accordingly. I hope I could express what I mean clearly. I'd appreciate if you could help me with this matter.

           

          Regards

          Hossein