||Good for you, I did not find anything that worked.
I found out that for edges not satisfying triangular equality like
0 1 1
1 2 2
2 3 3
3 4 4
4 0 20
the optimum is placing the vertices on the straight line, all smaller edges having the ratio equal to 1
and the value of optimum is then the ratio of the biggest edge (in this case 0.5)
So I computed the shortest distances between vertices and found out the theoretical optimum by taking the smallest ratio of all edges that are longer than shortest distance between its vertices. For seeds 100-599 the average of this theoretical optimum is 822168.84
That is when my jaw dropped as top guys practically have this.
But as I said, nothing I tried worked anywhere near that. I even coded the Multidimensional Scaling (using power iteration for first eigenpair, then Hotelling Deflation to find the second eigenpair also using power iteration) as I was certain that is the solution. Not ;)
I also tried springs simulations, Stochastic proximity embedding (stretching/expanding random edges to bring it closer to ratio 1), Stochastic proximity embedding interval (stretch/expand only if the ratio is not in desired interval which I choose to be theoretical optimum and 1), SA on moving vertices by random angle, and variations on those.
In the end I learned a lot (like Cayley-Menger coordinates) except not how to achieve a good score ;) So I do not take it as a failure.
||I have to say I really enjoyed the problem even though my solution was no where near the best solutions.
1) Create an initial greedy solution where I tried to place points that had the maximum degree and its adjacent vertices optimally.
2) Then use SA by picking one of the four vertices that belonged to the max ratio and min ratio edges, and try to place that vertex randomly on the grid so that it improves the solution and update the four vertices.
The thing that was the major bottleneck in the solution was computing the score after each state change. I tried to improve it by only traversing the vertices adjacent of the candidate vertex and got some improvement from that.
I also implemented SA for the first time it was performing better than hill climbing so I have to say it was a good learning experience. Another thing I noted that while using SA when I changed the candidate vertex to any of the surrounding points on the grid, then solution was much worse than picking random point on the grid.
Provisional Score : 369781.98
Provisional Rank : 66
||I also computed the theoretical optimum like you did (pretty early on during the contest) and was also amazed (at the time) that the top scores were indeed very close to it. On the tests that I used I can say that my scores (of the final solution) are ~45K away from optimum on average (with some tests reaching it almost perfectly and others being more than 100K away).
||Prev score: 776566.38, 17th place.
I tried to find out some sophisticated method, but none of them worked well.
Finilly I selected very simple elements and trust in speed. I have two stage:
2. randomization (with special manner)
1. Climbing: select the worst edge and try to make it better. The rate target was 0.87 to 1.13 first then narrowed when found better solutions. Note that worst edge selection is time consuming, it costs about 40 % of total time. (It could be possible to find a better way but I run out of my time.)
2. Randomization: select a random edge and make a large change. At the begining of randomizations stage the change was even larger then it is necessary to set optimal value. (eg. real length 100, target length 200 then I move both edge with about 95.) I take at least 2500 steps of randomization before starting to climb again.
I do not optimalize for small distances and other special cases. My program is still quite random. Selecting the best result from 5 run could result about 787000 points. (That meas that a speed up of 5 times could take at least 10 k more points.)
I am interested whether top players has any good idea, or just do faster program.
Note that I prefer problems where it is possible to utilize more idea and less speed optimalization.
||For worst edge selection I kept black-and-red tree (set in C++) with the worst edge sitting at the root. The nodes were integers pointing to entries of array holding edge specification. I would pop the worst edge, try to improve it, modify the array in relevant places (there were not that many) and pushed the node back on the tree. Actually it is hard to tell what the "worst" edge is. A perfect graph is not necessarily with each edge ratio equal to 1.0, it could be 0.8, 1.1 or any other number for that matter. So I kept two trees, one with ascending ratio and the other in descending.
||I also struggled with this task. I experimented with a few approaches, but I was used in the end is the following:
* I pick a scale s (between 0.8 and 1.0) and start with threshold x=0.6 that will be increased over the course of the algorithm.
* As long as there is an edge with ratio of current length to desired length smaller than x * s or greater than s / x, I pick a random such edge and a random its endpoint (call it v) and I perform one of the following two steps:
for each neighbour u of v if the edge uv does not obey the limit, I move the point u the smallest possible distance along the vector uv to make the edge happy,
Move 2: I pick two random neighbours u1 and u2 of v, I assume that u1 and u2 will not move and I need to move v. I calculate the crossing of two circles - one centered at u1 with radius being equal to the target distance of (u1,v), the second centered at u2 with radius equal to the target distance of (u2,v). This circle intersection gives two potential locations for v and I the random one.
On top of the above moves I have SA where the objective function is the number of unsatisfied edges. When there all the edges are happy with respect to the current threshold x, then I raise x by 0.06. The whole process is repeated a few times. Unfortunately adding more time to my approach did not help significantly, so it was clear to me that what I did was suboptimal.
||I had rather unusual situation. My time during this match was severely limited and most probably I would not participate if not for the grand-prix system that was introduced this year. This was my experience :)
That being said, I was very lucky with my first submission (~90 minutes, ~750K): I started with a simple SA (random initial placement, move a single vertex randomly as a transition/neighbor function) on the (more or less) final scoring function, which did not give any decent results (around 200K after some fine-tuning). I figured out that it's just very easy to get stuck in local maximum, so it would be best if I could start from original position. In order to find state that should be close to original position, it's enough to do SA on absolute differences between actual distances and given distances. So my solution does this first and then switches to original scoring function.
My third submit (~5h, ~786K) was almost the same, but I just optimized code, tweaked formulas, nothing really big.
After that, I decided that I won't be doing any big changes and I will only stick to introducing very small changes and running big number of tests on EC2 (2K tests on m4.16xlarge took 12 minutes). I tested every stupid thing that came to my mind and with the help of big number of runs (probably around 200 runs of 2K tests), I managed to move to ~792K.
On the last day, I noticed that increasing run time twice increases my score by about +900 (and +1600 for quadrupling it). I didn't try to optimize my code after the first day, so I figured out that this might be a good idea. I did a lot of crazy optimizations, and in the end my code run around 60-70% faster on my EC2 instance, but for some reason it was slower by 20-30% on TC's instance. And I still have no idea why.
The bottom line is, I feel a little bit as a cheater, since essentially I just threw bunch of $$$ at servers in order to have stable results and focused on ridiculously small changes. Especially since I feel that the core of my solution is very far from optimal (for example the first part could be done more effective with the use of algorithm similar to what mugurelionut did).
||I think the following approach may speed up search for the worst edge to process.
1. Order all edges
2. Pick a ratio threshold (s) to get you a number of edges you want to work with and place them in a smaller cache
3. Process edges from the cache which hopefully you can order and handle faster
4. Once you displace a vertex recalculate all affected edges, check against the threshold and either add them to the cache or throw away
5. When the cache is exhausted go back to step #1
||In fact I think about keeping just part of the edges in a faster structure, but in practice it didn't help.
During the SA process of my solution, edges in such situation keep changing too frequently, and in the end this kind of cache structure didn't have a high "hit ratio".
And whenever the new position in the list is close to the previous one, very few item (possibly none) need to be moved, which is already fast.
||I was very short on time and I didn't even try to submit, so only tested locally. My initial approach was basically to randomize initial positions then optimize using a gradient descent on a score function similar to the goal.
I also realized I got stuck easily on local minimum so I tried to improve randomization using genetic algorithms to no good. I blamed the algo but the I realized I didn't properly mapped the problem into the GA. Maybe I'll try to fix it later just to see if it works. As I got stuck, I also tried multidimensional scaling approaches. Force-directed, eigenvalues, etc. None worked.
But this is a fun problem. I'll see if I can get a decent local score using some of these ideas here.
I added then a "target" ratio of 0.9.
Reading that line made me feel really really dumb :) I did consider it in the beginning but I simply forgot about that.
Multiplying all of the given distances by 0.9 (single line of code) increases my score roughly by 5K. Which means that either my provisional score is inflated or my "stupid" solution is not that stupid after all :)
||I was also trying to split the solutions into two parts: restoring original point coordinates and improving towards score. Second part was just hill climbing since improving it didn't make much sense as long as first part was performing terrible.
I was trying many kinds of simulations to place points minimizing sum of abs(ratio-1) but later realized that it would never work for sparse graphs. I remember trying SA at some point but probably I had a bug somewhere and it didn't give me anything. Using SA as Psyho mentioned there instead gives me enough boost to place in top 15 after which many things can be improved.
Lesson learned: put more trust in SA instead of reading stupid papers