Topic
3 replies Latest Post - ‏2013-05-23T08:32:49Z by PhilippeLaborie
JorisK
JorisK
18 Posts
ACCEPTED ANSWER

Pinned topic providing a starting point

‏2013-05-16T21:55:02Z |

Dear,

I would like to provide my cp model (cp optimizer 12.5.1+java interface) with a starting point using a heuristically obtained solution. I hope to achieve that:

-starting from a good solution improves the convergence speed of the cp optimizer

-cp optimizer might be able to perform some additional constraint propagation, thereby cutting off solutions which would lead to weaker solutions? 

 

However, it is not entirely clear how to produce such a starting point from my heuristic solution. So the basic start is to create a new IloSolution:

IloSolution initSol=cp.solution();

1. Next I should add some variables. Should I add all variables present in my model? In my problem I only have IloInterval variables, most of them being absent. Or should I only add those variables which are present in the heuristic solution?

2. In case I have to add all variables present in the model, should I iterate over *all* of them and set their values? E.g. set for each interval variable whether they are absent or present, and set their ranges? Or does it suffice to set the interval variables present in my heuristic solution?

3. How to set sequence variables? There does not seem to be a way to add a sequence variable to an IloSolution?

4. Some variables are implied by others. E.g. a==b+c. Does it suffice to set b and c, or should I also set a?

5. How can I see whether the provided initial solution is actually being recognized as a correct, feasible initial solution?

Updated on 2013-05-16T22:13:01Z at 2013-05-16T22:13:01Z by JorisK
  • PhilippeLaborie
    PhilippeLaborie
    28 Posts
    ACCEPTED ANSWER

    Re: providing a starting point

    ‏2013-05-21T08:58:07Z  in response to JorisK

    Hello,

    1. No you do not have to add all the decision variables in the starting point solution. When a solution is used as a starting point by CP Optimizer, the engine will apply this solution and propagate constraints. So all variables values that can be inferred from the values in the starting point solution will also be used as starting point. Typically, if you have say, an interval variable a with an alternative constraint on an array of interval variables b[i] (constraint: alternative(a,b)), then it is enough to add in the starting point solution the interval b[i] that is selected to be present in the solution. The status absent of the other intervals b and the start/end values of interval a will be inferred by propagation.

    2. If the absence status of an interval variable in your heuristic solution cannot be inferred by propagation from the present intervals (for instance, let's say you want to maximize the number of present intervals in an oversubscribed scheduling problem), then you would need to add those interval variables as absent in the starting point solution to ensure that the solution can be restored and completed at the root of the search.

    3. There is no direct way to specify value of sequence variables in a starting point. But if you add the intervals of the sequence and set their presence/absence value together with the start/end value of present intervals, then the value of the sequence variable will be restored by propagation

    4. It suffices to set b and c

    5. The simplest way to see if a starting point was restored at the beginning of the search is to set the number of workers to 1 (it is harder to see in parallel mode) and set the log period to 1 in order to display all decisions, If the starting point is correctly restored, you should see in the log that the first solution is found in the very first nodes.

    Philippe

    • JorisK
      JorisK
      18 Posts
      ACCEPTED ANSWER

      Re: providing a starting point

      ‏2013-05-22T15:47:40Z  in response to PhilippeLaborie

      Dear Philippe Laborie,

       

      Thank you for your answer! I think that it would be a very good idea to add your reply to the cp optimizer manual, i.e. section:

      IDE and OPL > OPL Interfaces > C++ interface reference manual > Concepts > Starting point in CP Optimizer

      With respect to your last reply:

      I've set both the number of workers and the log period to 1, using:

       

      cp.setParameter(IloCP.IntParam.Workers, 1);
      cp.setParameter(IloCP.IntParam.LogPeriod, 1);

      Next, I set a feasible solution which has an objective value of 1395. The resulting output is:

      =======================

       

      ! ----------------------------------------------------------------------------
       ! Maximization problem - 2391 variables, 3188 constraints
       ! Presolve      : 105 extractables eliminated
       ! Using starting point solution
       ! DefaultInferenceLevel = Extended
       ! LogPeriod            = 1
       ! Workers              = 1
       ! TimeMode             = ElapsedTime
       ! TimeLimit            = 100
      ...
       ! Using sequential search.
       ! ----------------------------------------------------------------------------
       !          Best Branches  Non-fixed            Branch decision
                              1       2391                 -
       *             0        1 3.91s                 on end_depot
                     0        2       2391                 -
                     0        3          6            on start_depot
                     0        4       2390            on c4(0)
                     0        5       2390            on c30
                     0        6       2390            on c13
                     0        7       2376            on c4(0)v0
                     0        8       2373            on c4(0)v0
                     0        9       2373            on c30(0)
                     0       10       2356            on c30(0)v5
                     0       11       2353            on c30(0)v5
                     0       12       2340            on c13(0)v4
                     0       13       2336            on c13(0)v4
                     0       14       2336            on c45
                     0       15       2336            on c45(0)

      .....

       

                    0      431          1            on c36(3)
                     0      432          0        F   on end_depot
                     0      433          1        F        -
       *          1395      433 5.14s                      -

       

      =======================

      To me this looks like he does not restore my starting point correctly at the beginning of the search, as the best column contains a large number of zeroes? Only after a large number of iterations, a solution with objective 1395 is discovered?

      • PhilippeLaborie
        PhilippeLaborie
        28 Posts
        ACCEPTED ANSWER

        Re: providing a starting point

        ‏2013-05-23T08:32:49Z  in response to JorisK

        Yes, your interpretation of the log is right. The engine initially finds a solution with "quality"=0 and then search for another one by taking decisions one by one starting from the root node where no variable is fixed (Non-fixed=2391). It behaves as if the starting point solution was empty or not instantiated.

        You can check the content of the IloSolution you are using as starting point by calling "cout << solution".

        You can also have a look at distributed example sched_goalprog.cpp in cpoptimizer/examples/src/cpp to see how the starting point solution is stored.

        By the way, just a side note, I see that you are using maximal inference level for all constraints (DefaultInferenceLevel = Extended). This may be a bit strong and result in some slowdown. I would rather suggest you do not change the default inference level and just increase the inference level of some of the constraints you are using in your model on a one by one basis in case it really pays off. For a VRP like problem, the main inference level that could really improve the performance is probably the NoOverlapInferenceLevel.

        Philippe

        Philippe