Hello,


I have found two cases for two MILPs (corresponding to two different instances of resource-constrained scheduling problems with continuous start times) for which cplex 20.1.0 outputs a wrong dual bound (attached mod_wrongDualBound.lp) of mistakenly reports the problem as infeasible (mod_inf.lp).

In both cases, this happens only with Presolve and the thread parameter set to 1. If I let the number of threads unbounded, the problem does not appear (it also seems to disappear if presolve is turned off).

For the wrong dual bound case, it reports optimality for the objective 77 while have have smaller integer solutions of 76.733 found by a heuristic (and also accepted as mip-start).

I tried to display the solution kappa and it gives me this :

Branch-and-cut subproblem optimization:
Max condition number: 2.4896e+09
Percentage (number) of stable bases: 98.52% (865)
Percentage (number) of suspicious bases: 1.48% (13)
Percentage (number) of unstable bases: 0.00% (0)
Percentage (number) of ill-posed bases: 0.00% (0)
Attention level: 0.000148
CPLEX encountered possible slight numerical difficulties while solving this model.

For the infeasible case, same issue, I  have feasible solutions when I let the number of threads unbounded.

Do these « numerical difficulties » explain the problem ? Is there a way to turn off the faulted Presolve component without turning off all preprocessing ?

------------------------------
Christian Artigues
------------------------------

#DecisionOptimization

I tried mod_inf.lp and confirmed that with the default thread settings CPLEX 20.1 gets an optimal solution and with one thread it is declared integer infeasible at the root. With a limit of two threads, CPLEX thinks it is feasible. I noticed that the probing reductions were different in each run, so I tried it with one thread and probing turned off:
CPXPARAM_Threads 1
CPXPARAM_MIP_Strategy_Probe -1
Solution time increased dramatically, but it made it out of the root node, eventually found a feasible solution (about four minutes in on my PC) and was making good progress when I interrupted the run.

Then I ran with four different threads settings (1 ... 4). In all four runs, the aggregator resulted in the same reduced dimensions. The number of things probing fixed/tightened was inversely related to the number of threads: 697 variables/729 bounds with one thread; 680/701 with two threads; 618/632 with three threads; 601/618 with four threads. I don't know why more threads would translate to fewer changes, unless the various threads get in each other's way. In any case, it appears that probing might be overly aggressive in your case (?).

Might this be a bug? Your maximum condition number is not what I would call horrible, and you have no adventures in scaling in the model (nonzero coefficients range from 1 to 10, nonzero right-hand sides from 1 to 93).

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------