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&gt;\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$.