Topic
  • 10 replies
  • Latest Post - ‏2012-11-20T14:23:59Z by UdoKrehler
UdoKrehler
UdoKrehler
19 Posts

Pinned topic How to start CP Optimizer with an initial solution?

‏2012-10-23T17:10:58Z |
Hello,

in April 2012, I posted the following question here in this forum:


I would like to start CP Optimizer with an initial solution that I've previously computed with some heuristics. I use the
following simplified code (where the variable position is of type IIntVar[]: position = cp.IntVarArray(numberOfJobs, 0, 100)):

ISolution startSolution = cp.Solution();
for (int i = 0; i < numberOfJobs; i++)
{
startSolution.SetValue(position[i], positionInitialSolution[i]);
}
cp.SetStartingPoint(startSolution);
cp.Solve();

The code runs perfectly, but apparently, CP Optimizer completely ignores my initial solution. The first solution CP Optimizer produces is the same regardless of adding the above code lines or leaving them out. Moreover, the first solution CP Optimizer produces is much, much worse than my initial solution (which is definitely feasible, by the way). I did NOT use the depth-first search, actually I did not manually change anything w.r.t. the
search strategy. Does anybody know why CP Optimizer ignores my initial solution? Did I forget something important?


Replying to this question, Dr. Olivier Lhomme (ol) wrote the following answer:
"...indeed, in CP Optimizer 12.3, it may happen that the starting point solution is ignored when you mix integer and interval variables. This problem has been fixed in the 12.4 version."

Since I actually used the 12.3 version, I had to wait until now. But now, I updated to CP Optimizer 12.4 and nothing has changed w.r.t. the question above. The problem is still the same: CP Optimizer simply ignores my (fully specified, feasible) initial solution. But why? Can you help me? As a hint, I indeed mix integer and interval variables. But this should not be a problem any more in the 12.4 version, should it?

Thank you very much for your help, Udo.
Updated on 2012-11-20T14:23:59Z at 2012-11-20T14:23:59Z by UdoKrehler
  • rdumeur
    rdumeur
    105 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-10-24T15:20:19Z  
    Hello,

    I'd like to reproduce your problem. To be precise, are you using 12.4 or 12.4.0.1 (the fix pack)?
    When you say that your solution is ignored, it means that the first solution provided by the solver doesn't contains the assignment s you have specified the solution passed to SetStartingPoint, isn't it?
    Given this, are you sure that positionInitialSolution actually describes a feasible solution in the constraint model used by solve()? How did you check this?
    Cheers,

    Renaud
  • rdumeur
    rdumeur
    105 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-10-25T12:29:58Z  
    Dear Udo,

    I've tested the use of cp.SetStartingPoint() with interval variables by modifying the SchedGoalProg.cs so that after the first optimization goal,
    a replay solution is created that contains present intervals with their start dates.

    ISolution replay = cp.Solution();
    for(int i = 0; i < nbJobs; ++i)
    for (int j = 0; j < nbMachines; ++j)
    {
    if (cp.IsPresent(machines[j][i]))
    {
    replay.SetPresent(machines[j][i]);
    replay.SetStart(machines[j][i], cp.GetStart(machines[j][i]));
    Console.WriteLine("machine <"," + i + "> starts at " + cp.GetStart(machines[j][i]));
    }
    }

    Console.WriteLine("REPLAYING SOLUTION");
    cp.SetStartingPoint(replay);
    cp.Solve();
    for (int i = 0; i < nbJobs; ++i)
    for (int j = 0; j < nbMachines; ++j)
    {
    if (cp.IsPresent(machines[j][i]))
    {
    Console.WriteLine("replayed machine <" + j + "," + i + "> starts at " + cp.GetStart(machines[j][i]));
    }
    }
    It works perfectly on both 12.4.0.1. Note that I set the presence of interval that might be optional.
    Do you have optional intervals in your model, if so you must not forget to set their presence in the solution you pass to SetStartingPoint.

    I hope this helps,

    Renaud
  • rdumeur
    rdumeur
    105 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-10-25T12:30:30Z  
    Dear Udo,

    I've tested the use of cp.SetStartingPoint() with interval variables by modifying the SchedGoalProg.cs so that after the first optimization goal,
    a replay solution is created that contains present intervals with their start dates.

    
    ISolution replay = cp.Solution(); 
    
    for(
    
    int i = 0; i < nbJobs; ++i) 
    
    for (
    
    int j = 0; j < nbMachines; ++j) 
    { 
    
    if (cp.IsPresent(machines[j][i])) 
    { replay.SetPresent(machines[j][i]); replay.SetStart(machines[j][i], cp.GetStart(machines[j][i])); Console.WriteLine(
    "machine <",
    " + i + "> starts at 
    " + cp.GetStart(machines[j][i])); 
    } 
    }   Console.WriteLine(
    "REPLAYING SOLUTION"); cp.SetStartingPoint(replay); cp.Solve(); 
    
    for (
    
    int i = 0; i < nbJobs; ++i) 
    
    for (
    
    int j = 0; j < nbMachines; ++j) 
    { 
    
    if (cp.IsPresent(machines[j][i])) 
    { Console.WriteLine(
    "replayed machine <" + j + 
    "," + i + 
    "> starts at " + cp.GetStart(machines[j][i])); 
    } 
    }
    

    It works perfectly on both 12.4.0.1. Note that I set the presence of interval that might be optional.
    Do you have optional intervals in your model, if so you must not forget to set their presence in the solution you pass to SetStartingPoint.

    I hope this helps,

    Renaud
  • rdumeur
    rdumeur
    105 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-10-25T12:40:49Z  
    • rdumeur
    • ‏2012-10-25T12:30:30Z
    Dear Udo,

    I've tested the use of cp.SetStartingPoint() with interval variables by modifying the SchedGoalProg.cs so that after the first optimization goal,
    a replay solution is created that contains present intervals with their start dates.

    <pre class="jive-pre"> ISolution replay = cp.Solution(); for( int i = 0; i < nbJobs; ++i) for ( int j = 0; j < nbMachines; ++j) { if (cp.IsPresent(machines[j][i])) { replay.SetPresent(machines[j][i]); replay.SetStart(machines[j][i], cp.GetStart(machines[j][i])); Console.WriteLine( "machine <", " + i + "> starts at " + cp.GetStart(machines[j][i])); } } Console.WriteLine( "REPLAYING SOLUTION"); cp.SetStartingPoint(replay); cp.Solve(); for ( int i = 0; i < nbJobs; ++i) for ( int j = 0; j < nbMachines; ++j) { if (cp.IsPresent(machines[j][i])) { Console.WriteLine( "replayed machine <" + j + "," + i + "> starts at " + cp.GetStart(machines[j][i])); } } </pre>
    It works perfectly on both 12.4.0.1. Note that I set the presence of interval that might be optional.
    Do you have optional intervals in your model, if so you must not forget to set their presence in the solution you pass to SetStartingPoint.

    I hope this helps,

    Renaud
    Dear Udo,

    For some reasons, in my previous mail, the first WriteLine call is totally wrong because of this forum's text processing abilities: it does strange things with (") and (<) chars, I suspect. In the source, of course the " are correctly balanced.. and "i" and "j" variable indices are correcly displayed. Sorry about that.

    Renaud
  • UdoKrehler
    UdoKrehler
    19 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-10-26T15:53:35Z  
    • rdumeur
    • ‏2012-10-25T12:40:49Z
    Dear Udo,

    For some reasons, in my previous mail, the first WriteLine call is totally wrong because of this forum's text processing abilities: it does strange things with (") and (<) chars, I suspect. In the source, of course the " are correctly balanced.. and "i" and "j" variable indices are correcly displayed. Sorry about that.

    Renaud
    Dear Renaud,

    first of all, thank you very much for your interest and help!

    To answer your questions:
    • I most likely use version 12.4, not the fixpack version (How can I see or test which version is used?)
    • "When you say that your solution is ignored, it means that the first solution provided by the solver doesn't contains the assignment s you have specified the solution passed to SetStartingPoint, isn't it?" --> yes

    Your remarks w.r.t. optional interval variables seem to be very interesting: I do not use optional interval variables or at least, that's what I thought. I only use commands like

    jobm[j] = cp.IntervalVar(dur[j][i]);

    but I never use the .SetOptional() command or anything else which might include optionality. Thus, I thought by default, all interval variables are always present if not explicitly marked as optional. If so, I do NOT use any optional interval variables. Nevertheless, I simply added your code line to explicitly set all interval variables in the solution to present. And this indeed seems to have a great impact because CP OPtimizer now most often starts with my solution (in some cases, it immediately starts with a better solution)!

    To sum up: Either interval variables can be optional by default or setting their presence to true seems to have an impact on the starting solution even if no optional variables are used!?! Maybe, this is still a bug? I hope, my explanation is clear enough...

    Again, thank you very much for your help, Udo.
  • UdoKrehler
    UdoKrehler
    19 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-10-31T10:28:34Z  
    Dear Renaud,

    first of all, thank you very much for your interest and help!

    To answer your questions:
    • I most likely use version 12.4, not the fixpack version (How can I see or test which version is used?)
    • "When you say that your solution is ignored, it means that the first solution provided by the solver doesn't contains the assignment s you have specified the solution passed to SetStartingPoint, isn't it?" --> yes

    Your remarks w.r.t. optional interval variables seem to be very interesting: I do not use optional interval variables or at least, that's what I thought. I only use commands like

    jobm[j] = cp.IntervalVar(dur[j][i]);

    but I never use the .SetOptional() command or anything else which might include optionality. Thus, I thought by default, all interval variables are always present if not explicitly marked as optional. If so, I do NOT use any optional interval variables. Nevertheless, I simply added your code line to explicitly set all interval variables in the solution to present. And this indeed seems to have a great impact because CP OPtimizer now most often starts with my solution (in some cases, it immediately starts with a better solution)!

    To sum up: Either interval variables can be optional by default or setting their presence to true seems to have an impact on the starting solution even if no optional variables are used!?! Maybe, this is still a bug? I hope, my explanation is clear enough...

    Again, thank you very much for your help, Udo.
    Hello, since I still wonder about this problem, let me ask explicitly:

    If I use interval variables cp.IntervalVar(length) in C# without any further modifications, what is the default setting w.r.t. optionality? Are they always present or optional by default?

    Thank you very much for your answer, Udo.
  • SystemAdmin
    SystemAdmin
    554 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-11-01T14:58:25Z  
    Hello, since I still wonder about this problem, let me ask explicitly:

    If I use interval variables cp.IntervalVar(length) in C# without any further modifications, what is the default setting w.r.t. optionality? Are they always present or optional by default?

    Thank you very much for your answer, Udo.
    Hello.

    I don't have C#, so I cannot verify your problem right now. But indeed it seems there is a bug.
    You can easily verify whether cp.IntervalVar creates optional interval variable using a model with only only one interval variable and a constraint PresenceOf(variable) == 0. This model should not have a solution, unless cp.IntervalVar creates optional interval variable.

    My guess though is that the problem is in the solution object: unless set as present in the solution, the interval may be remembered as absent in the solution by default (what would also be a bug).

    Best regards, Petr
  • UdoKrehler
    UdoKrehler
    19 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-11-05T08:51:49Z  
    Hello.

    I don't have C#, so I cannot verify your problem right now. But indeed it seems there is a bug.
    You can easily verify whether cp.IntervalVar creates optional interval variable using a model with only only one interval variable and a constraint PresenceOf(variable) == 0. This model should not have a solution, unless cp.IntervalVar creates optional interval variable.

    My guess though is that the problem is in the solution object: unless set as present in the solution, the interval may be remembered as absent in the solution by default (what would also be a bug).

    Best regards, Petr
    Dear Petr,
    you're right, this can easily be tested. According to my test, interval variables are never optional but must be present by default.

    --> Consequence: As you said, I also think that there is a bug in the solution object!

    I would be happy if you could further focus on this issue, Udo.
  • rdumeur
    rdumeur
    105 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-11-05T16:53:36Z  
    Dear Petr,
    you're right, this can easily be tested. According to my test, interval variables are never optional but must be present by default.

    --> Consequence: As you said, I also think that there is a bug in the solution object!

    I would be happy if you could further focus on this issue, Udo.
    Dear Udo,

    I've again tried to reproduce your problem. I reproduced a situation where a warm starting point can be ignored, but it can be explained and involves optional variables that you said you do not use. If you could provide a minimal model reproducing the problem, it would help us very much. Thank you in advance,

    Renaud
  • UdoKrehler
    UdoKrehler
    19 Posts

    Re: How to start CP Optimizer with an initial solution?

    ‏2012-11-20T14:23:59Z  
    • rdumeur
    • ‏2012-11-05T16:53:36Z
    Dear Udo,

    I've again tried to reproduce your problem. I reproduced a situation where a warm starting point can be ignored, but it can be explained and involves optional variables that you said you do not use. If you could provide a minimal model reproducing the problem, it would help us very much. Thank you in advance,

    Renaud
    Dear Renaud,
    sorry, but my original problem is very large and I'm too busy in the moment to shrink it down to a reasonable minimal model in the moment. Maybe I'll have time later, but not now, sorry...
    Udo.