Oracle-Guided Road Network Planning Solution by nikaj

It was pretty obvious from the beginning that we would have to solve optimal MST-partitioning once we had collected enough information, so let’s explain how to tackle this subproblem first.

Inserting N-M shortest roads (ignoring cycle-forming ones, as in DSU) clearly leads to shortest length partitioning, but size distributions likely won’t match the target.

We can slightly alter those distributions by performing swaps (removing and adding roads). We can split a group of size A+B into sizes A and B, or do the opposite, affecting three of those values with some length extra penalty. If we keep doing swaps that gets us closer to the target, eventually we will get a match.

I’ve implemented it by always exploring from the best current state, based on minimizing pair (minimum difference, minimum length). Since sometimes we may have to get further away from the target distribution temporarily, it can’t be done using beam search; instead, we use a priority queue.

One thing that speeds up the process is to not perform all road swaps each time; instead, we consider intermediate states with N-M-1 roads. This means, in each “odd step” we consider removing each of existing O(N) roads and in each “even” step we consider adding each of existing unused roads. Since very long roads never need to be used, we limit use of roads to the O(N) shortest ones only. This method usually very quickly finds one possible solution and, given time, will keep slightly improving it.

With it out of the way, we are left to solve two other subproblems: generating queries and estimating each road length based on query answers. We will do both of those simultaneously in an online fashion.

What do we gather from query results? The road is in MST if and only if all the roads on the cycle it forms are better than it. That means we have only this kind of information: some roads are longer than other.

In order to do the estimation, we maintain the samples of city locations that agree with gathered information as much as possible.

We start with random valid configuration.

After each query, we will have to adjust the samples that have disagreement with the last query outcome (or unresolved ones from previous queries). This is done using hill climbing, with the scoring function defined as sum of MAX(A-B, 0) for each A<B constraint we have gathered from the queries. We move cities to random location if it doesn’t worsen the score. For different L, we will have a different number of constraints. The number of samples varies from 3 (L=15) to 128 (L=3).

Ideally, we would always move current city to uniform valid target (Gibbs sampling), but it can lead to a very slow convergence that we can’t afford.

Some workarounds (more likely to happen for larger L):

• Move the city closer to the current location instead of a random point inside its box.
• Focus on cities that are involved in constrain violation instead of random (or sequential) order.
• When the move is improving the score, consider moving in that direction again.

After all the queries are done, we spend some more time to obtain more samples with the similar HC. In the end, each road length is estimated as simple average over all samples observed during this extra sampling process.

Now we are left with only one subproblem: generating efficient queries, which in these kinds of problems usually means finding queries that gather as much information (based on entropy) as possible.

Since we have to generate \(400\) queries each affecting all the samples, we don’t have much time to properly search for the best ones.

For L=3, I simply explore random cities and two of the closest three cities, choosing highest entropy (based on which road of the three was the longest for each sample).

For L>3, we need some way to pick cities so that different samples have vastly different estimation from their MST. Evaluating the query efficiency isn’t the hardest part, although it can be time consuming.

We will calculate MST for each sample and calculate entropy based (A<B, A>B) constraint frequencies from each road pair. For large L there are too many constraints and instead we use fast but inaccurate method by calculating entropy of “number of samples with this road in MST” for each road.

How to generate sets of cities that discriminates samples? I’ve used greedy heuristics.

• Pick two random samples to distinguish between them.
• Start with a random city, then repeat process until L cities are collected.
• Pick next closest city for each sample (Prim MST step).
• If both samples picked the same city and they connect to the same previous node, we skip that city.
• If any of those two connect to different previous city in another sample we can add that one to the query.
• If they are different, consider what would happen if we added both. Check where the other city would connect to. If it happens that they would connect to the same previous node (just in reversed order) forming the same MST, then we skip, otherwise add.

In order to speed up Prim process, only roads from Delaunay triangulation are used for next shortest road computation (avoiding O(N) Prim step).

Once we generated these sets, we can make random changes in them to try to increase query evaluation (positive impact only for small L).