Algorithm for sorting numbers summing to a total and respecting criterions in python

Question

I am trying to do a feed optimisation calculation for animal feeding but I am a rookie in term of python coding.

Actually what I try to achieve is compute the less expensive combination of n ingredients by groups of k or less that supply enough of A and B criterions.

My problem is that when ingredients number start going up, python hangs in the calculations. So is there a way to have python use more memory or a better algorithm or already available package for those kind of computations. I searched the net for answer but maybe this particular problem has a mathematical name I am unaware of.

What I am doing now:

1. Create the ingredient matrix: each ingredient has a name and then P,A,B,C,D... where P is the price and A,B,C,... are the values for different nutritive elements
2. Create the limit matrix: Each element has a minimum and maximum value of the total mix.
3. Create the objective vector: What I want to obtain for now it is a A=X vector and B=Y vector but I would like to specify C,D, etc. in the future.
4. I then compute all the possible combinations of ingredients summing to a total (usually 1000) and by group of k ingredients.
5. Remove the combinations that do not fit the limit matrix to get the available combination matrix
6. Multiply the ingredient matrix by the combination matrix to get the final composition matrix
7. Remove all the values in the composition matrix that do not fit the objective vector for criterions A and B.
8. Sort the resulting list by price and give the result.

I am using Numpy for most of those operations.

The approach (to my knowledge) cannot be a simple linear algebra problem because sometimes there will be no perfect solution which is why the numerical approach was taken in the first place.

Thanks

Answer 1

I think you should be looking at scipy.optimize - it will quite happily deal with numpy arrays and is generally quite fast. See ref http://docs.scipy.org/doc/scipy-0.8.x/reference/tutorial/optimize.html

If you have an input vector A which specifies the amount of each ingredient, and an ingredient matrix I which specifies the price and nutrient-values of each ingredient, then AI should give you the total price and nutritional value of a given mixture.

You now need an evaluation function which normalizes A (multiplies it by the lowest possible constant such that all nutrient values are at least their minimum required value) and returns the total price, plus a steep penalty for any amount of nutrient over a maximum value, plus a lesser penalty for a large number of ingredients. The optimizer then plays with A (while keeping all values >= 0) to minimize the result of the evaluation function.

Answer 2

This is definitely a linear programming problem---it's often called the Diet Problem. As Hugh Bothwell said look at scipy.optimize. The following should get you started,

from scipy import array,dot
from scipy.optimize import fmin_slsqp as fmin

c = array([173.0,184.0,167.0])    # cost or prices
b = array([0.1,0.1,0.1])          # lower nutrient bounds
A = array([[ 0.39, 0.09, 0.77],   # nutrient composition
           [ 0.75, 0.32, 0.15],
           [ 0.32, 0.76, 0.65]])

x = array([0.5,0.5,0.5])          # initial guess

def obj(x):
    # I'm the objective function
    return dot(c,x)

def con(x):
    # I'm the inequality constraints
    return dot(A,x) - b

print fmin(obj,x,f_ieqcons=con)