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
.

Relevant Pages

  • combinatorial optimization of a sum
    ... where each index takes ingeger values in some range 1,2,..R, ... I'm interested in both exact and inexact algorithms (if the exact ... Any advice, including search keyword suggestions, is appreciated. ...
    (comp.theory)
  • combinatorial optimization of a sum
    ... where each index takes ingeger values in some range 1,2,..R, ... I'm interested in both exact and inexact algorithms (if the exact ... Any advice, including search keyword suggestions, is appreciated. ...
    (sci.math.num-analysis)
  • combinatorial optimization of a sum
    ... where each index takes ingeger values in some range 1,2,..R, ... I'm interested in both exact and inexact algorithms (if the exact ... Any advice, including search keyword suggestions, is appreciated. ...
    (sci.math.research)
  • Re: The spinoza papers: design of the extra-precision number object 2
    ... common representation for a reason? ... "exact" reals. ... Implement algorithms without premature attention to efficiency, ... while avoiding NP completeness as much as possible and repeated, ...
    (comp.programming)
  • Re: Relevance of density of primes
    ... available for determining the primality of n directly. ... > Exact formulae for pido exist. ... > We have algorithms, based upon these formulae that will compute ... I'm not "looking for" anything, high-school level or otherwise, ...
    (sci.math)