optimization problem: find ingredients that add up to given totals [closed]

Question

imagine you have a list of ingredients. Each ingredient has five traits, let's call them A, B, C, D and E. You want a mix of ingredients for which the sum of each trait is known.

for example:

• ingredient 1 has 5 A, 2 B, 0 C, 0 D and 3 E.
• ingredient 2 has 0 A, 3 B, 2 C, 2 D and 0 E
• ingredient 3 has 0 A, 0 B, 6 C, 6 D and 4 E.
• the goal is 10 A, 10 B, 10 C, 10 D and 10 E.
• the algorithm finds that you need 2 x ingredient 1, 2 x ingredient 2 and 1 x ingredient 3.

the algorithm should work

• for any amount of ingredients (my real problem has 206)
• for ingredients which could contain any combination of the five traits
• for any finite sum goal
• if there is no possible combination, the algorithm should return it is impossible

thanks for the help! Aron

Answer 1

Let $b_i$ be the demand for trait $i$. Let $a_{ij}$ be the number of trait $i$ in ingredient $j$. Let nonnegative integer decision variable $x_j$ be the number of times ingredient $j$ is used. The problem is to find a feasible solution to the linear equations $$\sum_j a_{ij} x_j = b_i \quad \text{for all $i$}$$ You can use an integer linear programming solver to either find a solution or detect infeasibility.