Integer Overflow Issue in cons_cumulative

[jakobwitzig]

Hi SCIP team,

SCIP returns the wrong result on the attached cip.

This leads to a wrong result because now all jobs are scheduled to start at point 0, which exceeds the capacity of the cumulative constraints. See the attached log file.

Moreover, the model should be infeasible instead because all starting points should be fixed to zero.

Best,
Jakob

PS: The issue can be reproduced with the latest Windows installer.

bug.zip

[alexhoen]

Hi Jakob,

I could reproduce it and took an initial look into it.
From what I can tell, the problem lies with the cumulative constraint handler, which appears to struggle when dealing with infinite or even very large bounds. For instance, in the function removeIrrelevantJobs, both the earliest completion time (ECT) and the latest start time (LST) are stored as integers. If an infinite upper bound is converted to an integer, it results in a negative value—leading to a negative LST. Consequently, the variable is excluded from the constraint, leaving the cumulative constraint empty since this can be performed for each variable.

As a workaround, defining smaller upper bounds - that not exceed the capacity of integer variables- resolves the issue. For example:

  [integer] <Start_Job_0>: obj=0, original bounds=[0,100000]
  [integer] <Start_Job_1>: obj=0, original bounds=[0,100000]
  [integer] <Start_Job_2>: obj=0, original bounds=[0,+100000]
  [integer] <Start_Job_3>: obj=0, original bounds=[0,+100000]
  [integer] <Start_Job_4>: obj=0, original bounds=[0,+100000]
  [integer] <Start_Job_5>: obj=0, original bounds=[0,+100000]
  [integer] <Start_Job_6>: obj=0, original bounds=[0,+100000]
  [integer] <Start_Job_7>: obj=0, original bounds=[0,+100000]
  [integer] <Start_Job_8>: obj=0, original bounds=[0,+100000]
  [integer] <Start_Job_9>: obj=0, original bounds=[0,+100000]

With these bounds in place, I was able to obtain a plausible solution:

primal solution (original space):
=================================

objective value:                                 2770
Start_Job_1                                       136 	(obj:0)
Start_Job_2                                        92 	(obj:0)
Start_Job_3                                        47 	(obj:0)
Start_Job_4                                       217 	(obj:0)
Start_Job_5                                       235 	(obj:0)
Start_Job_6                                       203 	(obj:0)
Start_Job_7                                       252 	(obj:0)
Start_Job_8                                       175 	(obj:0)
Start_Job_9                                       193 	(obj:0)
Dummy_Sn                                          277 	(obj:10)

Unfortunately, there are several places of such conversion issues and it will take a bit of time to get rid of them entirely.

Please let me know if this helps you.

Best,
Alex

[jakobwitzig]

Hi Alex,

Thanks for your feedback and for taking the time to look.

Yes, we found the same workaround.

Best,
Jakob

[alexhoen]

We will ping if we have working fix for it.