Decision Optimization

Hello,

Is it a scheduling problem?

If you deactivate the temporal relaxation, does the problem remain?

Which version of CP Optimizer is used? Can you send a piece of code to reproduce the problem? 

Hi,

yes it is a scheduling problem.

I provided the encoding and a small instance that generates a negative gap. 

How to disable the temporal relaxation?

Tolerances:

The cplex studio version is 22.1.2.

PS In my local machine I have the version  22.1.1.0 and could not replicate such behaviour.

Best,

Francesco

With the code you sent, on a Windows platform and with 22.1.2, there is no problem, we get:

 ! ----------------------------------------------------------------------------
 ! Search completed, 37 solutions found.
 ! Best objective         : 0; 8,937; 576 (optimal)
 ! Best bound             : 0; 8,937; 576
 ! ----------------------------------------------------------------------------

You did not get this output? Which platform do you use?

For deactivating the temporal relaxation in opl, you can add the following line in the "execute" part before the minimize:

      cp.param.TemporalRelaxation="Off";

Hello,

so, yes I get that same output if I disable the tolerance levels.

But, as I specified, I'm enabling both relative and absolute tolerance levels.

Tolerances:

In such a case, the full output is as follows (sorry, I forgot to upload it yesterday).
! --------------------------------------------------- CP Optimizer 22.1.2.0 --
 ! Minimization problem - 307 variables, 407 constraints
 ! TimeLimit            = 600
 ! LogVerbosity         = Terse
 ! OptimalityTolerance  = 5
 ! RelativeOptimalityTolerance = 0.1
 ! Initial process time : 0.01s (0.01s extraction + 0.00s propagation)
 !  . Log search space  : 1,025.7 (before), 1,025.7 (after)
 !  . Memory usage      : 1.7 MB (before), 1.7 MB (after)
 ! Using parallel search with 4 workers.
 ! ----------------------------------------------------------------------------
 !          Best Branches  Non-fixed    W       Branch decision
                        0        307                 -
 + New bound is 0; 8,937; 86
 *             1      595  0.05s        1      (gap is 84.81% @ crit. 3 of 3)
   New objective is 1; 9,906; 566
 *             0    1,836  0.05s        2      (gap is 12.92% @ crit. 2 of 3)
   New objective is 0; 10,263; 544
               0    8,605        129    2   F        -
 + New bound is 0; 9,605; 458 (gap is 15.81% @ crit. 3 of 3)
 *             0    9,194  0.28s        2      (gap is 15.81% @ crit. 3 of 3)
   New objective is 0; 10,089; 544
 *             0    8,369  0.32s        4      (gap is 19.79% @ crit. 3 of 3)
   New objective is 0; 9,220; 571
 *             0    9,529  0.34s        3      (gap is 19.79% @ crit. 3 of 3)
   New objective is 0; 9,216; 571
 *             0    9,700  0.36s        3      (gap is 19.51% @ crit. 3 of 3)
   New objective is 0; 9,154; 569
 *             0   10,041  0.38s        3      (gap is 19.37% @ crit. 3 of 3)
   New objective is 0; 9,102; 568
 *             0   11,482  0.42s        2      (gap is 19.08% @ crit. 3 of 3)
   New objective is 0; 9,043; 566
 *             0   11,055  0.43s        3      (gap is 19.37% @ crit. 3 of 3)
   New objective is 0; 8,998; 568
 ! ----------------------------------------------------------------------------
 ! Search completed, 9 solutions found.
 ! Best objective         : 0; 8,998; 568 (optimal)
 ! Best bound             : 0; 9,605; 458
 ! ----------------------------------------------------------------------------
 ! Number of branches     : 48,849
 ! Number of fails        : 16,137
 ! Total memory usage     : 13.1 MB (12.1 MB CP Optimizer + 1.0 MB Concert)
 ! Time spent in solve    : 0.44s (0.43s engine + 0.01s extraction)
 ! Search speed (br. / s) : 113,602.3
 ! ----------------------------------------------------------------------------

As expected, once it finds a solution within the tolerance level for the i-th goal then it starts optimizing the i+1-th goal. If a new solution is found that is not worsening any of the goals from 1 to i+1 then that's the new objective, as it should be.

But the thing is, the best bound is not updated anymore for the previous goals from 1 to i, since they have already been optimized and "closed" (according to tolerance).

So, is there any way to keep the best bounds updated?
PS I am running it via oplrun on linux.

Hello,

I was not able to reproduce the problem on windows with 20 random seeds and the specified tolerances (or some other tolerances). Now after a try on Linux, the problem cannot be reproduced either. Which exact Linux port are you using? Hopefully we will be able reproduce it. Can you confirm that even with the temporal relaxation off, the problem still happen?

I do not think the problem is directly related to the tolerances, nor that it is deep into the solver, rather this seems to be a display problem. Otherwise, the solver would not find solutions better than the bound after the too strong bound is found. 

You can print the bound after the solve, in the execute{} section:

(check next answer)

Hi,

I disabled the temporal relaxation, executed again via oplrun and still got the problem.

Moreover, yesterday I ran some experiments with no tolerances at all (but with the temporal relaxation enabled as default) expecting them to work fine but also in that case I noticed the same problem sometimes.
I just replicated them with and without temporal relaxation and in both case the best bound do not work.
The 2nd has a small negative gap while the 3rd has a gap>1000 while cpo claims optimality.
I guess that it is indeed optimal but bounds are not updated.
Check inside the no_tolerance.zip. The model is basically the same as the other, I just removed some useless attributes from the .dat and the .mod but nothing has changed in practice.

I also tried executing directly the .cpo file you sent me and again the problem remains (I also added the print of all the best bounds). Output is attached.

I can provide you more info or maybe we can have a meeting to show you the issue live and give you all the needed info.

OS: Ubuntu 24.04.2 LTS x86_64 
Version: trixie/sid 
Kernel: Linux 6.8.0-60-generic 
Kernel Version: #63-Ubuntu SMP PREEMPT_DYNAMIC Tue 

Thanks! We can reproduce the wrong bound problem with your last model.