Small difference in energy functions has big difference in performance

(O No1 Kraxtis) #1

I am mainly writing this for some insight or any tip if someone has one, as I can not really identify it as a problem.

In my MIDCP I have a linear energy of : minimize(pathLengths’*paths). Paths are a logical value 0 or 1 if a path is chosen. pathLengths is simply the number of edges of a path on my graph. For some test graphs I have, my program needed approximately 1 minute.

However, edges have actually a length (not unit) but positive and although the maximum length is not even twice as big as the minimum length, the program needs far more time to be solved (~15 minutes).

So for future reference: Do the actual values matter for an energy? I.e if all the length are between [0,0.3] would it make any difference to scale them to [0,30] for example? I did some experimentation and it didn’t seem the case. And secondly, does it help if lengths are integers (like in the first setup?).

Or is the above simply a normal expected behavior and nothing can be commented on it?