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$.

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$.

StackExchange Computer Science Q#49474, answer score: 3