a colouring / matching problem

Question

While trying to find a bijection which preserves various combinatorial statistics, I was led to the problem below. Very much to my surprise, a closely related question, Coloring summands of given n-partition with given weights of colors, was asked here almost the same day I stumbled across the problem.

I have a number of boxes, each with a number of items in it, and a number of coloured tags. The total number of items equals the total number of coloured tags.

Essentially, Coloring summands of given n-partition with given weights of colors asks how to find the number of possibilities to assign the tags to the items, such that the items in one box all have the same colour.

I have to consider the following variant: each item has additionally a number written on it and so has each coloured tag.

I am in need of a reasonably efficient algorithm that decides whether one can assign the tags to the items in the boxes, such that

1. the number on the tag and on the item is always the same, and
2. the items in one box all have the same colour.

I am currently stuck with an instance of the problem that has roughly 350 boxes with a total of roughly 2800 items. The numbers on the tags range from 1 to 8 and there are 4 different colours.

Examples:

Suppose we have 4 boxes with items numbered either 1 or 2: \begin{array}{ccc} 1&1&1,\\ 1&1&2,\\ 1&2,&\\ 2&2.& \end{array} and colour tags blue with numbers 1,1,2,2,2 and red with numbers 1,1,1,1,2. Then there is a unique way to colour the boxes: first and last box red.

If the colour tags are blue with numbers 1,1,1,2,2 and red with numbers 1,1,1,2,2 then there are two ways to colour the boxes.

EDIT:

To facilitate playing with the problem, here is some python/sage code, including some examples, and the instance I am stuck with. I'll award the bounty to any presenter of an algorithm which yields a colouring in reasonable time (or proves that no such colouring exists)...

NEXT EDIT:

I discovered that it makes a huge difference in which order the colours are tried. The most natural heuristic is to try colours which have tags for all numbers still available first. The linked file reflects this finding.

ANOTHER EDIT:

A possibly helpful observation is that in the problematic instance, any box contains either 2 items, 4 items or 8 items. More precisely: there are 2 distinct boxes with 2 items, 11 distinct boxes with 4 items, the remaining boxes contain 8 items. Is there an obvious way to take advantage of this?

Is there any strategy to show that no solution exists?

Answer 1

One extreme of few color and few numbers is two colors and only one number. With the further simplification that both colors occur equally often we get an NP-complete problem.

The Partition Problem is

Given a multiset $S=[x_1,\cdots,x_m]$ of positive integers with $\sum_S=\sum_1^mx_i=2N$, determine if $S$ can be partitioned into sub-multisets $S_1,S_2$ with $\sum_{S_1}=\sum_{S_2}=N.$

To reduce to your problem, Make $m$ boxes where box $B_i$ contains $x_i$ items each with numeral $1$ written on it. Also $N$ red and $N$ blue tags each with $1$ written on it.

Now it may be that in some sense, most instances are easy.

In various cases one might be able to ignore the tags or ignore the colors (and/or amalgamate to have only two colors or two tags). If any of those reduced problems has no solution , neither does the main problem. If one of them has only a few solutions then one has a few simpler problems to solve. But it seems like there is no hope of an all purpose efficient algorithm.

Answer 2

Since you are looking for finding a feasible solution of a particular instance in a relatively short time, I would combine a couple techniques.

I would start by doing some breadth first searches, essentially finding small subsets of boxes and determining how many feasible colorings there are of each small subset. These would be exhaustive but quick, and the number of feasible colorings might serve to indicate what are the hard boxes to color.

Based on the data, I would then pick a feasible coloring and do a depth first search trying to extend the coloring as far as I could. If that started to look like it eats too much time, fix a coloring, and go back to the BFS strategy on the partially solved instance.

The distinction between this and attempting colorings at random is that you give yourself opportunity to study the instance and "game" the search towards possible or maximal success. Whether it is better to start with hard-to-color boxes or not is up to you and your sense of the instance.

There is also exploiting symmetry: if several boxes have the same contents, it may be prudent to leave those boxes out of the search and save them to the last, rather than generating many possible partial colorings involving those boxes.

Gerhard "Likes Feasible And Exhaustive Search" Paseman, 2014.09.19

Answer 3

Adding numbers does not make the problem (much) harder, I think. First, we remake the tags in new colors, corresponding to old color and number. Each item can then only be colored with a subset of new colors, which corresponds to that the old number on the tag and the item is the same.

Also, all items in one box must have the same color. Thus, in each box, we can find the biggest list of all valid colors we may color the items in that box with.

Thus, the problem can be reduced to the original problem about coloring boxes, but with some restrictions on what colors that are allowed for each box.

We can encode this as follows: Say you have $\lambda_i$ colors of color $i$, and $s_j$ items in box $j$. Then the number of valid colorings is given by the coefficient of $x_1^{\lambda_1}\dots x_k^{\lambda_k}$ in $$ \prod_{j=1}^{boxes} (x^{s_j}_{c_{j1}}+x^{s_j}_{c_{j2}}+\dots+x^{s_j}_{c_{jm_j}}) $$ where $c_{j1},c_{j2},\dots,c_{j{m_j}}$ are the valid colors to use in box $j$.

The right-hand side is a polynomial with degree equal to the total number of items. Extraction of the coefficient is theoretically possible with computing a high-order derivative of this... but it is most likely nasty.