This problem is NP-hard by reduction from Vertex Cover.
In the Vertex Cover problem, we are given a graph $G = (V, E)$ and a number $r$, and our task is to determine whether there is some subset $U$ of at most $r$ vertices from $V$ such that every edge in $E$ is incident on at least one vertex in $U$. (Equivalently: Is it possible to kill every edge in $G$ by deleting at most $r$ vertices?)
First, partitioning $A$ into $s$ disjoint subsets is equivalent to assigning each element in $A$ exactly one of $s$ possible labels. The basic idea of the reduction is to create a label $S_j$ for each vertex $v_j$ in $V$, and to "allow" each edge to be assigned only one of the two labels corresponding to its endpoints, in the following sense: assigning an edge a corresponding label introduces no (genuine) constraint on what other edges can be assigned the same label, while assigning an edge to a non-corresponding label prevents any other edge being assigned the same label -- which of course has the effect of pushing up the number of distinct labels required.
To construct an instance $(A, a, s)$ of your problem from an instance $(G, r)$ of Vertex Cover:
- Set $k$ to $|E|$, and create an element $(i, j)$ in $A$ for each edge $v_iv_j$ in $E$. (These pairs can be thought of as the integers $1, \dots, k$; any bijection between them will do.)
- Set $a_{(b, c), d}$ to $|E|$ if $d=b$ or $d=c$; otherwise, set $a_{(b, c), d}$ to 1.
- Set $s=r$.
If $(G, r)$ is a YES-instance of Vertex Cover, then it's easy to see that the just-constructed instance of your problem is also a YES-instance: just pick the labels $S_j$ corresponding to the vertices $v_j$ in any solution $U$, and for each edge $v_bv_c \in E$ assign the corresponding element $(b, c) \in A$ whichever one of the labels $S_b$ or $S_c$ was picked (choose arbitrarily if both labels were picked). This solution uses $s$ subsets, and is valid because the only $a_{ij}$ in force are those for corresponding labels, which have the (non-) effect of preventing more than $|E|$ edges being assigned the same label.
It remains to show that a YES-instance $X=(A, a, s)$ of your problem implies that the original $(G, r)$ is a YES-instance of Vertex Cover. This is slightly more complicated, since a valid solution $Y$ to $X$ may in general assign an edge $(i, j)$ a non-corresponding label $S_m$, i.e., $m \notin \{i, j\}$, meaning that we can't necessarily "read off" a valid vertex cover $U$ from a valid solution $Y$.
However, assigning a non-corresponding label has a high cost that severely limits the structure of the solution: whenever an edge $(i, j)$ is assigned such a label $S_m$, with $m \notin \{i, j\}$, the fact that $a_{(i, j), m} = 1$ ensures that it must be the only edge assigned this label. So, in any solution $Y$ containing such a non-correspondingly-labelled edge $(i, j) \mapsto S_m$, we could construct an alternative solution $Y'$ as follows:
- Arbitrarily choose the new label $S_z$ for $(i, j)$ to be either $S_i$ or $S_j$.
- Assign $(i, j)$ this new label. If this results in an invalid solution, it must be because exactly one other edge $(i', j')$, $z \notin \{i', j'\}$ had already been assigned the label $S_z$. In that case, set $(i, j) = (i', j')$ and go to step 1.
The above algorithm must terminate in one of two ways: either a new label $S_z$ is found that introduces no contradiction, or a complete cycle of vertices is found. In the former case, a valid new solution with $s-1$ sets is found, while in the latter case a valid new solution with $s$ sets is found; either way, we have constructed a valid new solution with at least one more edge assigned to a corresponding label. After repeating this entire process at most $|E|$ times, we will have produced a valid solution $Y''$ from which a solution to the original Vertex Cover problem can be read off.
This construction is clearly polynomial time, so it follows that your problem is NP-hard.
