Re: combinatorial optimization of a sum




In article <1181012530.289267.11930@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
penasquitos@xxxxxxxxx writes:
I'd like to minimize a function of several indices

F(i,j,k) = A(i) + B(j) + C(k) + X(i,j) + Y(j,k) + Z(k,i)

where each index takes ingeger values in some range 1,2,..R,

(If there are N indices (N=3 above), the total number of terms in F is
N + N*(N-1)/2)

Simply enumerating all arguments in search of the minimum takes R^N
steps, so I wonder if there are more efficient algorithms.

I'm interested in both exact and inexact algorithms (if the exact
algorithms are inefficent)

Any advice, including search keyword suggestions, is appreciated.


integer programming, branch and bound and cut:
look here http://plato.asu.edu/sub/discrete.html
hth
peter
.