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