Tag Info

1

I don't think I can answer from a proper OR perspective, but I had to solve approximately the same problem (have had to multiple times, actually) and got an algorithmic answer that left me saying "well... duh!" in its simplicity. Hopefully you can see the "well duh" answer to translate it mathematically / (im)prove it as appropriate. It's ...

5

So, it turns out that this problem admits a linear-time exact algorithm! The intuition is to add to the extremes (first and last position) two items with the same base $b^*$, which must be the base with the most items ($b^* = \text{argmax} \{\alpha_b\}$). Then one can reduce by 2 the number of items in this base ($\alpha_{b^*} \gets \alpha_{b^*} - 2$), cut ...

4

A genetic algorithm with a permutation type chromosome works well on this problem. I have an R notebook demonstrating the approach that can be downloaded here. Since a GA is a metaheuristic, there is no guarantee of optimality, but it seems to perform pretty well (and quickly) on test problems.

6

Another possibility is to consider an integer linear extended formulation. Let $\mathcal{A}_b$ be the set of valid assignments for base $b$. I.e., an element of $\mathcal{A}_b$ determines $\alpha_b$ unique positions among the available ones $\{1, \ldots, n\}$, which are the positions taken by items of base $b$ in the solution. Denote with \$\mathcal{A} = \...

5

A first attempt is to model this problem using a special case of the Quadratic Assignment Problem (QAP), in which we want to assign URLs to positions in the permutation. To make the model smaller, we first note that we don't need to provide the exact position of each URL, because URLs with the same hostname are indistinguishable for the purpose of computing ...

Top 50 recent answers are included