Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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"? –  joriki Sep 21 '12 at 22:31
    
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. –  s_hewitt Sep 21 '12 at 22:34
    
@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. –  Rod Carvalho Sep 21 '12 at 22:37
    
@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. –  s_hewitt Sep 21 '12 at 22:40
    
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. –  joriki Sep 21 '12 at 22:44

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
Thank you both for your help –  s_hewitt Sep 24 '12 at 15:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.