Topic
  • 2 replies
  • Latest Post - ‏2013-10-25T14:56:51Z by Petr Vilím
JorisK
JorisK
37 Posts

Pinned topic CP doesn't find optimal solution

‏2013-10-22T16:04:46Z |
Dear,
 
I'm having some trouble with a CP model programmed using the Java interface (CP optimizer version 12.5). Whenever I run this model on system A, I get a solution with objective 11. However, when I run the exact same code on system B, it returns a worse solution with objective 9. This shouldn't be possible as the CP model is solved to optimality, i.e there is NO time limit or solution limit. Whenever I modify the code such that the variable domains are fixed to the solution found on machine A, and re-run the code, both machines indeed find the same solution with objective 11. So the question is, how is it possible that the exact same code produces different outcomes on different machines? I noticed that when I remove this line from my code:
cp.setParameter(IloCP.IntParam.DefaultInferenceLevel, IloCP.ParameterValues.Extended);
both machine A and B find the suboptimal solution with objective 9. 

Whenever I provide a warm-start, the solution on machine A changes from 11 to 12. So it seems that CP terminates for some reason, but it seems that it did not complete the search process as there apparently exist better solutions? The search always terminates very fast, i.e. after 1 or 2 seconds.

 
a. Is there a way to check whether the CP solution is indeed optimal, i.e. that the optimizer did not terminate the search due to another reason? In cplex, you can do: cplex.getStatus()==IloCplex.Status.Optimal Is there something equivalent for CP?
b. Is there a way to export the CP model to a file and read it again? This would make debugging substantially easier.
c. Any suggestions how to troubleshoot this issue? It is very strange that you get different optimal solutions on different machines, or that the outcome is affected by the Inference Level?
 
I have added the class that is causing issues. As this class is part of a much larger project, it is unfortunately not possible to run the class. Nevertheless, you can see the CP model.

 

Below is the output of machine A:

Output with cp.setParameter(IloCP.IntParam.DefaultInferenceLevel, IloCP.ParameterValues.Extended):

 ! Maximization problem - 43 variables, 84 constraints
 ! Presolve      : 20 extractables eliminated
 ! DefaultInferenceLevel = Extended
 ! Initial process time : 0.01s (0.01s extraction + 0.00s propagation)
 !  . Log search space  : 205.7 (before), 205.7 (after)
 !  . Memory usage      : 883.0 kB (before), 883.0 kB (after)
 ! Using parallel search with 8 workers.
 ! ----------------------------------------------------------------------------
 !          Best Branches  Non-fixed    W       Branch decision
 *            11      126 0.44s         7            -
 ! ----------------------------------------------------------------------------
 ! Search terminated normally, 1 solution found.
 ! Best objective         : 11 (optimal - effective tol. is 0)
 ! Number of branches     : 4098
 ! Number of fails        : 1681
 ! Total memory usage     : 8.9 MB (8.8 MB CP Optimizer + 0.1 MB Concert)
 ! Time spent in solve    : 0.44s (0.42s engine + 0.02s extraction)
 ! Search speed (br. / s) : 9530.2

 

Output with default inference:

 ! Maximization problem - 43 variables, 84 constraints
 ! Presolve      : 20 extractables eliminated
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 215.9 (before), 215.9 (after)
 !  . Memory usage      : 892.7 kB (before), 966.5 kB (after)
 ! Using parallel search with 8 workers.
 ! ----------------------------------------------------------------------------
 !          Best Branches  Non-fixed    W       Branch decision
 *             9       27 0.37s         1            -
 ! ----------------------------------------------------------------------------
 ! Search terminated normally, 1 solution found.
 ! Best objective         : 9 (optimal - effective tol. is 0)
 ! Number of branches     : 4095
 ! Number of fails        : 1685
 ! Total memory usage     : 8.5 MB (8.4 MB CP Optimizer + 0.1 MB Concert)
 ! Time spent in solve    : 0.37s (0.37s engine + 0.00s extraction)
 ! Search speed (br. / s) : 10776.3

Output with default inference and a warm start with objective 11:

! Maximization problem - 43 variables, 84 constraints
 ! Presolve      : 20 extractables eliminated
 ! Using starting point solution
 ! Initial process time : 0.01s (0.01s extraction + 0.00s propagation)
 !  . Log search space  : 215.9 (before), 215.9 (after)
 !  . Memory usage      : 892.7 kB (before), 998.5 kB (after)
 ! Using parallel search with 8 workers.
 ! ----------------------------------------------------------------------------
 !          Best Branches  Non-fixed    W       Branch decision
                     1000          1    4       on c2(0)
                     1000          1    7       on c13(0)
                     1000          1    2       on c13(0)
                     1000          5    1       on c13(1)
                     1000          5    8       on c14(0)
                     1001          1    5       on c6(0)
                     1002          5    3       on c12(0)
                     1002          5    6       on c12(0)
 *            12      599 0.67s         1            -
              12     2000          5    2       on c6(0)
              12     2001          5    6       on c14(0)
              12     2001          5    5       on c14(0)
              12     2002          5    8       on c13(0)
              12     2003          5    1       on c5(0)
              12     2000          5    3       on c14(0)
              12     2001          6    7       on c7(0)
              12     2001          7    4       on c17(0)
 ! ----------------------------------------------------------------------------
 ! Search terminated normally, 1 solution found.
 ! Best objective         : 12 (optimal - effective tol. is 0)
 ! Number of branches     : 18304
 ! Number of fails        : 8120
 ! Total memory usage     : 8.8 MB (8.7 MB CP Optimizer + 0.1 MB Concert)
 ! Time spent in solve    : 1.35s (1.34s engine + 0.01s extraction)
 ! Search speed (br. / s) : 13659.7

The only difference is the inference level and/or a warm start. Yet, 3 different objectives are returned, and all are claimed to be optimal?

Attachments

Updated on 2013-10-22T18:02:35Z at 2013-10-22T18:02:35Z by JorisK
  • JorisK
    JorisK
    37 Posts

    Re: CP doesn't find optimal solution

    ‏2013-10-23T21:35:53Z  

    Update: I've tried switching back to CP Optimizer version 12.4. Using this version, I don't get the above behavior; solutions seem to be consistent. Could this be a bug in CP Optimizer 12.5? Any help would be highly appreciated.

  • Petr Vilím
    Petr Vilím
    61 Posts

    Re: CP doesn't find optimal solution

    ‏2013-10-25T14:56:51Z  
    • JorisK
    • ‏2013-10-23T21:35:53Z

    Update: I've tried switching back to CP Optimizer version 12.4. Using this version, I don't get the above behavior; solutions seem to be consistent. Could this be a bug in CP Optimizer 12.5? Any help would be highly appreciated.

    Hello Joris,

    it seems that you're encountering a bug in CP Optimizer. There are ways to analyze the situation using undocumented features. Unfortunatelly, I cannot describe them on the forum. Could you contact me please on petr_vilim@cz.ibm.com?

    Thanks, Petr