Decision Optimization

I observed the cp optimizer can get i feasible solution very faste(most time with high quality). However, it takes much more time to prove its optimality. For example, it tries to converge the best bound until it meets the current bound. Sometimes, it seems it keeps branching to prove optimality until meets time limits even though it actually got the optimal solution. Any tips to help improve this? Any parameter like failure-direct-search or search-phase can help? Thanks in advance!

I also observed the randomness on the solution. After get the current solution(actually optimal), sometimes it quickly prove it is optimal sometimes it takes very long time to prove(best bound = current bound)

Zhiwei,

If the random seed is identical, one should get the same result (assuming the number of workers is identical).

Would it be possible to share a model that illustrates the behavior that you are observing ?

Thanks,

Hi Hugues,
Attached are the cpo files and logs to describe what i mentioned above. The two cpo files are generated by the same code with two runs, they are actually the same(the order might be different). But the performance of the two are different. The cpo file with slow actually find the optimal solution in a very short time, but it stills used all the rest time to prove its optimality(ended with a large gap). 
Thanks for your patience. 

please ignore above attached. use the simplified files instead

Hi Zhiwei,

Thanks for sharing your models.
I can see some minor differences between the two CPO files.
I suppose these ".cpo" files are export of models created using the docplex python library.
In the ".cpo" files, the line numbers in the source python files are also provided. It would be interesting to understand the cause of these minor differences.
Unless there is an issue in docplex, the exported ".cpo" files should be identical.
However, in the model building script, if some python data structures are used that do not maintain order when iterating over them, this may explain these minor differences.
If decision variables or constraints are not declared in the same order, this may impact search (decision variables will not be explored in the same order, for instance) and may explain the difference in behavior.

I also did some experiments with your models using the "runseeds" command available in the cpoptimizer interactive tool. This tool executes the search several times using different random seeds and computes some statistics.

I set a maximum timelimit of 120 seconds (as solve could last much longer for some values of the random seed) and I did notice that CPO can spend a long time to prove optimality from time to time (about 1 out of 10 runs).
Both versions of your model behaved similarly. Here is the output of "runseeds" for one model:

CP-Optimizer> tools runseeds 10
Benchmarking current problem on 10 runs...
Run       Soln      Proof      Branches     Time (s)       Objective
--------------------------------------------------------------------
  1          1          1        147705         6.63           12398
  2          1          1        145786         3.04           12398
  3          1          0       5000098       122.61           12398
  4          1          1        130861         2.87           12398
  5          1          1        144804         3.31           12398
  6          1          1        153022         3.37           12398
  7          1          1        291866         6.67           12398
  8          1          1        315254        14.16           12398
  9          1          1        161426         8.85           12398
 10          1          1        269966        14.58           12398
--------------------------------------------------------------------
Statistics on runs with proof (9 out of 10):
Mean      1.00       1.00        195632         7.05           12398
Std dev                           73860         4.64               0
Geomean                          184718         5.99
Min                              130861         2.87           12398
Max                              315254        14.58           12398
--------------------------------------------------------------------
Statistics on runs stopped by limit (1 out of 10):
Mean      1.00       0.00       5000098       122.61           12398
Std dev                               0         0.00               0
Geomean                         5000098       122.61
Min                             5000098       122.61           12398
Max                             5000098       122.61           12398

It might be useful to investigate some parameter settings to mitigate this behavior. May be by selecting a specific SearchType... I haven't tested that.

Best regards,