Practical Implementation for Refinement Order on Integer Partitions

The refinement order on partitions of an integer $n$ can be defined as follows: $\lambda=(\lambda_1,\dots,\lambda_k)\leq\mu=(\mu_1,\dots,\mu_\ell)$ if there is a partition of the parts of $\lambda$ into blocks whose sums are the parts of $\mu$.

It is known that the problem of deciding whether $\lambda\leq\mu$ is NP-complete. However, for a practical application I would need an algorithm which performs reasonably when $n$ is around $200$. Ideally, this algorithm would already have a (free) implementation...

I tried the following naive approach:

• find the last index $j$ such that $\mu_j>\lambda_1$
• if $\mu_{j+1} = \lambda_1$ remove $\mu_{j+1}$ from $\mu$ and $\lambda_1$ from $\lambda$ and recurse
• otherwise, for $j\in\{j,j-1,\dots,1\}$:
• subtract $\lambda_1$ from $\mu_j$ and reorder to obtain a new partition, and recurse with this partition and the rest of $\lambda$

Although this seems to work reasonably well for many pairs $(\lambda,\mu)$ of partitions of size around $200$, it performs poorly when $\lambda$ has many small parts but is not a refinement of $\mu$.

• Why do you expect such an algorithm to exist? – Yuval Filmus Nov 14 '15 at 14:40
• @YuvalFilmus: I am only hoping for it, because I would like to use it. Perhaps I do have some hope because even the simple approach I outlined above seems to perform very badly only in very few cases. I'd also be interested in any experiments other people did. – Martin Rubey Nov 16 '15 at 8:22
• A couple approaches in Sage have shown up on Math.SE. – Austin Mohr Jun 7 '16 at 20:22

I suggest you try using integer linear programming. Introduce $k\ell$ zero-or-one variables $x_{i,j}$, with the constraints

$$\sum_j x_{i,j} \lambda_j = \mu_i$$

and

$$\sum_i x_{i,j} = 1.$$

Feed it to an off-the-shelf ILP solver. If it can find a feasible solution for you, then you know that $\lambda \le \mu$. If it can determine that no solution exists, then you know that $\lambda \not\le \mu$.

• Admittedly a very "soft" question: should I expect that a specialised approach (whatever that would be) performs in the worst case just as badly as this approach? – Martin Rubey Nov 16 '15 at 7:55
• I did a test, indeed it seems that linear programming (I used cplex) is better in the worst case. I ran (a slightly refined) version of the algorithm in the question for 1000 random partitions of 100, and got a worst case timing of 320 seconds, whereas MILP's worst case was around 0.1 seconds. – Martin Rubey Nov 16 '15 at 9:39
• My comment above has bad numbers, but seems to be essentially correct. (I found a partition of 200 where "my" algorithm takes around 20 seconds, but nothing like that for cplex.) Sorry for the noise. – Martin Rubey Nov 16 '15 at 9:54
• Unfortunately, it seems that only cplex does the job quickly. I tried GLPK and CBC now, and they are both unusable for the problem, it appears... – Martin Rubey Nov 16 '15 at 11:52
• Sorry, with "linear programming" I meant "integer linear programming". The "only" remaining problem is that I probably can't use cplex for the real thing (a website), and GLPK and CBC are not up to the task... – Martin Rubey Nov 16 '15 at 16:27