Python: run through all integer combinations subject to a constraint (find the minimum of a function)
Question: I would like to find a way to return the set of all vectors [x_1,...,x_n]
subject to the constraint x_1+...+x_n=constant, each x_i is a nonnegative
integer, and the order doesn't matter. (so [1,1,1,2]=[2,1,1,1]). I have very
little experience with programming but I've been working with Python (sage)
for the past month or so.

In particular, I'm trying to find the minimum value of a 15-variable
(symmetric) function over nonnegative integers (subject to a constraint), but
I'd like to write a program to do it because I can use it for similar projects
as well.

I have been trying to write a program for 4 days now, and I'm suddenly coming
to the realization that I have to somehow recursively define my function...and
I have no idea what to do. I have a code which does something similar to what
I want (but it's no where near done). I'll post it even though I'm sure it's
the least efficient way to do what I'm trying to do:

    
    
    def each_comb_first_step(vec):
        row_num=floor(math.fabs((vec[0,vec.ncols()-1]-vec[0,vec.ncols()-2]))/2)+1
        mat=matrix(ZZ, row_num, vec.ncols(), 0)
        for j in range(row_num):
            mat[j]=vec
            vec[0,vec.ncols()-2]=vec[0,vec.ncols()-2]+1
            vec[0,vec.ncols()-1]=vec[0,vec.ncols()-1]-1
        return mat
    
    def each_comb(num,const):
        vec1=matrix(ZZ,1,num,0)
        vec1[0,num-1]=const
        time=0
        steps=0
    subtot=0
        for i in (2,..,num-1):
            steps=floor(const/(i+1))
            for j in (1,..,steps):
                time=j
                for k in (num-i-1,..,num-2):
                    vec1[0,k]=time
                    time=time+1
                subtot=0
                for l in range(num-1):
                    subtot=subtot+vec1[0,l]
                vec1[0,num-1]=const-subtot
                mat1=each_comb_first_step(vec1)
                return mat1
    

Is there by any chance a function which already does this, or something
similar? Any help or suggestions would be greatly appreciated.


Answer: A **brute force** solution is as follows:

    
    
    import itertools as it
    
    # Constraint function returns true if inputs meet constraint requirement
    def constraint(x1, x2, x3, x4): 
        return x1 + x2 + x3 + x4 == 10
    
    numbers = range(1,10)   #valid numbers (non-negative integers)
    num_variables = 4       #size of number tuple to create
    
    #vectors contains all tuples of 4 numbers that meet constraint
    vectors = [t for t in it.combinations_with_replacement(numbers, num_variables)
               if constraint(*t)]
    
    print vectors
    

outputs

    
    
    [(1, 1, 1, 7), (1, 1, 2, 6), (1, 1, 3, 5), (1, 1, 4, 4), (1, 2, 2, 5), (1, 2, 3, 4), (1, 3, 3, 3), (2, 2, 2, 4), (2, 2, 3, 3)]
    

The running time is `O(numbers**num_variables)`, so will probably be
prohibitively slow with your 15 variable solution. You might want to look into
linear programming techniques. There's a free course on [Linear
Optimization](https://www.coursera.org/course/linearopt) at the Cousera
website that can be used to solve these sorts of problems much quicker.

Check out this [Stack Overflow
question](http://stackoverflow.com/questions/12543092/trying-to-find-a-pure-
python-integer-linear-programming-solver-with-inequalities) for a link to a
python module that is an integer constraint solver.

