# Linear Inequalities - Allocation Problem

The problem at hand can be summarized as follows: we have to allocate a ressource to $n$ production units. The allocation to production unit $i$ is $x_i$. Each of the production unit will produce at different rate. Let us define ${\bf r} = (r_1,...,r_n)$ where the production rate of unit $i$ is $r_i$.

We have also a method to come up with an initial allocation $(x_1,...,x_n)$ for a total desired production $R$ (a given constant). We do not give any details about this method because it is irrelevant to the question.

So the method finds a solution ${\bf x}=(x_1,...,x_n)$ to the system $$R={\bf r}{\bf x}^T$$ where ${\bf x}\geq {\bf 0}$.

We also regroup the production units into categories. We would like to obtain a minimum production from certain categories and a maximum production in other categories. This can be expressed by a system of linear inequalities $B{\bf x}\geq{\bf b}$.

The initial solution found by the method does not necessarily meets all the constraints.

My Questions:

• what would be the best approach to shift the production from one category of production units to another when the constraints are not met (and still have $R={\bf r}{\bf x}^T$ )? We would like the final solution not too far from the initial one and the all the constraints are respected.
• Can you provide some reference (papers, website, etc.) for this type of problems?

Thank you.

• You are missing some important constraints: $\mathbf{x}\ge 0$. Or can you use negative resources? – Sergio Parreiras Apr 4 '14 at 16:29
• "The initial solution found by the method". Which method are you referring to? – Sergio Parreiras Apr 4 '14 at 16:30
• Are you trying to maximize $R$ or $R$ is just a constant? – Sergio Parreiras Apr 4 '14 at 16:31
• $R$ is a constant and ${\bf x}\geq {\bf 0}$. The method to come up with the initial solution is not specified. We only know that it does not guarantee that the constraints are respected, but that it gives a solution that is close to the desired final result. (I have edited the original question) – quantguy Apr 4 '14 at 17:17
• I would not call the "initial solution" a solution since it does not satisfy the inequalities. – Sergio Parreiras Apr 4 '14 at 19:31

This is not probably the answer you want, but you have some $\mathbf{x_0}\ge 0$ such that $\mathbf{r}\mathbf{x_0}^T=R$ and you want to solve:

$$\min_{\mathbf{x}} (\mathbf{x}-\mathbf{x_0})\,D\,(\mathbf{x}-\mathbf{x_0})^T$$ subject to the following constraints: $\mathbf{x\ge 0}$, $\mathbf{r}\mathbf{x}^T=R$ and $B\mathbf{x}\ge \mathbf{b}$.

Here $D$ is a symmetric, positive-definite matrix so it defines an inner product, if $D$ is the identity, we have the usual inner product.

This becomes a standard quadratic minimization problem with linear constaints. You are trying to minimize the distance between $\mathbf{x}$ and your original point $\mathbf{x_0}$.

If it is more costly to change some production categories than others, you can adjust the weights of $D$ to reflect that.

As for references, I think any quadratic programming book must be able to cover this problem.

Notice that there is no guarantee that your feasible set $\mathbf{x\ge 0}$, $\mathbf{r}\mathbf{x}^T=R$ and $B\mathbf{x}\ge \mathbf{b}$ is not empty.

In practice if you have few categories (say two or three), you can check whether the feasible set is empty of not using some computer algebra package. See cylindrical algebraic decomposition in Mathematica or Maple.

• You are right: this is not exactly the answer I was looking for. But I think you have part of the solution. I must confess that the ojbective is rather vague. In fact, I would like to have some methodology to move the solution to a given direction ${\bf d}_i$ when I try to fill the gap in constraint $i$. For example, if a category exceeds its limit in the original solution, then I would like to deflect the excess in another pre-selected category, rather than letting the alogorithm choose any category. Do you think we can incorporate these preferences in the $D$ matrix ? – quantguy Apr 4 '14 at 20:33
• Using $D$ you can some how direct priority of adjustment. Imagine $D$ has zero outside the diagonals and the diagonal is positive. If you increase the entry $i$ at the diagonal, the resource $i$ is going to display less variation from the original solution. Assume 3 resources: Say if you want to use resource number 3 to adjust, than you increases the entries 1 and 2 and decrease the 3 entry. – Sergio Parreiras Apr 4 '14 at 22:25