Algorithm Implementation

[vsrdharca]

Hello Rodolfo

Just another quick question - is your algorithm implementation Chained Lin Kernighan? (https://pdfs.semanticscholar.org/c4ed/86c06e92dab39db4414297c2055abcaf6590.pdf)

Thank you for your patience in answering my barrage of questions!

Best

Vikram

[vsrdharca]

osm_x_y.zip
Hi Rodolfo,

I ran the test with 50K records and got an out of memory exception on the heap. Understandably its a large data set. Is there anyway to tune this so it doesn't run out of heap space? Thoughts? I attached the tsp file

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at LinKernighan.initDistanceTable(LinKernighan.java:70)
at LinKernighan.(LinKernighan.java:35)
at Main.main(Main.java:34)
C:\Users\vikra\AppData\Local\NetBeans\Cache\8.2\executor-snippets\run.xml:53: Java returned: 1
BUILD FAILED (total time: 6 seconds)

[RodolfoPichardo]

Hi,

My apologies for not answering your previous question, I forgot to come back to it when I read it. Short answer for the first question: no.

You have nearly 50,000 nodes (buildings), we create a table with distances between all the nodes, the distances are of type double; so the memory size of this table is n*n*64 (a double is 64 bits in Java) = 20,000 MB, that's a really big number.

We could reduce the size of the table by half if we only use an upper triangular matrix, we could also cut the memory size further if we use float instead of double. This will keep the memory below 5,000 MB which you should be able to handle with 8GB of RAM (at least theoretically).

Another option, which is way more complex, would be to store the distances on disk and intelligently design the algorithm to retrieve the data every time we need it. This should give us a lot of flexibility and -with a SDD- not an unreasonably inefficient solution, however, it would mean a major overhaul of the program.

[vsrdharca]

Thank you for your reply @RodolfoPichardo

For #2 and #3 of your suggestions would you have any time to point me at a high level to where I should consider refactoring?

If its easier to talk over the phone or skype I am open to that option if you are.

[RodolfoPichardo]

Sure, you should be able to get away with a really small refactoring now that I think about it. Just go to the LinKernighan.java file, located in the src

• rewrite the method initDistanceTable to create the triangular matrix instead of the full matrix.
• modify all the instances where we retrieve the variable distanceTable (which happens only twice), to use the new triangular matrix.
• Change line 70 from double to float

Once you are done you are welcome to send a PR.

[vsrdharca]

Hi Rodolfo @RodolfoPichardo

Even if I created an upper triangular matrix by rewriting initDistanceTable by commenting out res[j][i] = res[i][j]; the memory allocation (double[][] res = new double[this.size][this.size];) is made anyway for the lower half even though it contains no values?

[RodolfoPichardo]

What I am proposing is to remove the double[][] res = new double[this.size][this.size]; and do the triangular matrix as a array of arrays of different sizes, something like:

double[][] res = new double[this.size][];
for(int i = 0; i < this.size; ++i) {
    res[i] = new double[this.size - i];
}

Note: this code has not been tested.

[vsrdharca]

@RodolfoPichardo Thanks Rodolfo. Makes sense.
I would also need to override getDistance to account for just the lower triangular matrix?

[vsrdharca]

@RodolfoPichardo

Hi Rodolfo - I finally got around to making an upper triangular matrix and testing the code. Would you like me to fold this into your master trunk?