3
$\begingroup$

I am trying to come up with the set of equations that will help solve the following problem, but am stuck without a starting point - I can't classify the question to look up more info.

The problem:

Divide a set of products among a set of categories such that a product does not belong to more than one category and the total products within each category satisfies a minimum number.

Example:

I have 6 products that can belong to 3 categories with the required minimums for each category in the final row. For each row, the allowed categories for that product are marked with an X - eg. Product A can only be categorized in CatX, Product B can only be categorized in CatX or CatY. $$ \begin{matrix} Product & CatX & CatY & CatZ \\ A & X & & \\ B & X & X & \\ C & X & & \\ D & X & X & X \\ E & & & X\\ F & & X & \\ Min Required& 3 & 1 & 2\\ \end{matrix} $$ The solution - where * marks how the product was categorized: $$ \begin{matrix} Product & CatX & CatY & CatZ \\ A & * & & \\ B & * & & \\ C & * & & \\ D & & & * \\ E & & & *\\ F & & * & \\ Total & 3 & 1 & 2\\ \end{matrix} $$

  • 0
    You write "The solution" with a definite article, but nothing in the problem description appears to require this particular arrangement. Are further conditions missing, or did you mean "a solution"?2012-09-21
  • 0
    I think it is the only solution to the example problem I gave. For clarity, in the first table, Product A can only be classified in CatX, Product B only in CatX or CatY, and so on.2012-09-21
  • 0
    @s_hewitt: In the first table, the products are labeled using letters from the Latin alphabet, whereas in the second table they are labeled using numerals. Also, you relabeled the categories.2012-09-21
  • 0
    @RodCarvalho Sorry, you are correct. I edited the first table but not the second by mistake. I have fixed the second table so it uses the same classifications.2012-09-21
  • 0
    I see. I suggest to add the clarification to the question; it's currently not apparent (to me) from the question that the $X$s in the first table show admissible assignments whereas the $X$s in the second table show actual assignments.2012-09-21
  • 0
    @joriki Agreed, I've been looking at it for a while. Thanks for helping me clarify. Is it clear now?2012-09-21
  • 0
    Yes, much clearer; except there should be some punctuation or a line break between "The solution" and the rest; currently it looks as if that whole line were one sentence.2012-09-21

2 Answers 2

2

Let $x_{ij} = 1$ if you put product $i$ in category $j$, $0$ otherwise. You need $\sum_i x_{ij} \ge m_j$ for each $j$, where $m_j$ is the minimum for category $j$, and $\sum_j x_{ij} = 1$ for each $i$, and each $x_{ij} \in \{0,1\}$. The last requirement takes it out of the realm of linear algebra. However, look up "Transportation problem".

2

Robert has already answered your question, but I will expand upon what he wrote.

Suppose that you have $m$ products and $n$ categories. Then, you have a binary assignment matrix $X \in \{0,1\}^{m \times n}$ whose $(i,j)$-th entry, which we denote by $x_{ij}$, is given by

  • $x_{ij} = 1$ if product $i$ is assigned to category $j$.
  • $x_{ij} = 0$ otherwise.

There are some constraints on this matrix, namely:

  • since a product cannot belong to more than one category, we have that there's only one entry equal to $1$ per row. We can write that as $X 1_n = 1_n$ where $1_n$ is the $n$-dimensional vector whose entries are all equal to $1$.
  • since the total number of products within each category must be greater than a given number $b_j$, we have that the sum of the elements in the $j$-th column of $X$ will be greater or equal than $b_j$. We can write that as $1_m^T X \geq b^T$, where $\geq$ applied to vectors denotes entry-wise $\geq$.

In the example you gave, we have $m = 6$ and $n = 3$. If you want to brute-force this problem, you could generate all $2^{18} = 262144$ binary matrices of dimensions $6 \times 3$, and keep only the ones that satisfy the equality constraint $X 1_n = 1_n$ and the inequality constraint $1_m^T X \geq b^T$. However, there are much smarter ways of solving the problem. For example, you could start with a zero matrix and then pick one entry in each row and make it equal to $1$, which guarantees that $X$ satisfies the equality constraint.

  • 0
    Thank you both for your help2012-09-24