Solving an IP (minimization, objective = sum of binary variables), I noticed an anomaly in the node log.

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap
*     0+    0                           16.0000        0.0000           100.00%
      0     0       10.6250    26       16.0000       10.6250      106   33.59%
      0     0       11.0000    18       16.0000      Fract: 1      113   31.25%
      0     2       11.0000    18       16.0000       11.0000      113   31.25%
Elapsed time = 5.74 sec. (4755.21 ticks, tree = 0.01 MB, solutions = 2)
     22    22       11.4000    13       16.0000       11.0000      349   31.25%
     33    34       12.0000     4       16.0000       11.0000      457   31.25%
     47    46       13.1667     7       16.0000       11.0000      643   31.25%
     61    53       14.5000     3       16.0000       11.0000      671   31.25%
     70    71       13.5000     3       16.0000       11.0000      727   31.25%
*    83    68      integral     0       14.0000       11.0000      733   21.43%
     83    68       14.0000     0       14.0000       11.0000      733   21.43%
     90    68  -1.00000e+75     0       14.0000       11.0000      728   21.43%
     90    66       14.0000     0       14.0000       11.0000      728   21.43%
     98    71       11.5000     5       14.0000       11.0000     1763   21.43%

Does the apparently harmless -1.00000e+75 objective value around node 90 signal that the dual somehow became infeasible? Clearly the primal objective value cannot be less than zero. Or is CPLEX just testing me to see if I actually read the node log?

Paul

Originally posted by: EdKlotz

No, we don't have any code to occasionally print weird node logs to see if our users are reading them.   I have not seen this output before.   Note that both lines 83 and 90 of the log print out two log lines rather than one, which doesn't normally happen unless a node heuristic succeeds.   Also note that the two lines for node 90 indicate 0 integer infeasibilities, yet no new incumbent solution is found.

Can you upload a more detailed node log with a MIP interval of 1 and the info at the start of the optimization that indicates the number of threads in use?   Based on the log, it appears to be a multithreaded log.   Also, do you see the anomaly if you run with a single thread?

Ed,

Sorry. I tried, but I can't reproduce the phenomenon, which doesn't entirely surprise me. There's a random heuristic up front that generates not only an initial incumbent but also the initial set of constraints. Even though I seed the RNG, and even though it's pretty consistent about the objective value it achieves, it never seems to generate the same number of constraints twice. That's partly adventures in parallel threads (there's a single synchronized route all threads beat on), partly (I suspect) Java collection classes that maybe aren't deterministic, and maybe related to a third party library doing SVDs that may also not be entirely deterministic. On top of that, Xavier tells me that generic callbacks use some storage stuff that isn't fully deterministic.

Looking at the log I sent you, I also noticed that the entry with the goofy lower bound has a lower iteration count than the previous entry. So either it returned some simplex pivots (for a cash refund?) or there's a thread synchronization aspect to this.

Anyway, it seems harmless, and I've only seen it once in a decent number of runs of the code.

Paul

Originally posted by: EdKlotz

Paul,

          Regarding the lower iteration count, that is indeed a thread synchronization issue.  This is fundamental to performing deterministic synchronization; the bottom line is that you cannot have the threads communicate at any time other than a synch. point if you want deterministic behavior.  And unless you can come up with a metric that measures deterministic time in a way that guarantees that fewer simplex iterations since the last synch. point on one thread (since the last synch. point) is guaranteed to take less deterministic time than more iterations on another thread, this non monotonicity can happen.    Given the variability associated with basis factorizations and the associated solves, along with the differences in node processing in different threads, I am not optimistic such a metric exists.

You can avoid this node log behavior by switching to single threaded or opportunistic parallel mode, but in exchange for monotonic cumulative iteration counts you get either the slower performance of single threaded mode, or the possible lack of reproducibility with two consecutive runs on the same machine with the same configurations.

I too believe it's harmless, but if you can upload a SAV file of the model if you see it again, or just upload a SAV file that seems reasonably close, I can run it with different random seeds and see if anything shows up.   Also, did you get this log with interactive CPLEX or only with a program?   If the latter, you might as well try running with the datacheck parameter set to 1 just to see if it sheds any light on this.   Given that you vary the set of constraints used in the optimization, maybe there's one or two constraints in the program that have an infinite or really large right hand side that somehow comes into play here.

Ed

Ed,

I cannot upload a SAV file; the program uses a generic callback (lazy constraints) (plus I can't seem to reproduce the error). That also answers your question about the interactive optimizer. Regarding the datacheck parameter, all the constraints are set covering constraints (sum of binaries >= 1), so the RHS is not the culprit.

It was probably an artifact of a hack by Fuzzy Bear. At any rate, I'm going to blame them. Couldn't possibly be anything I did.

Paul