Group assignment optimization with very large number of elements

Question

The problem: I have n distinct elements. There are m categories into which each element can be assigned. Each element can be assigned to 1 or more categories. Performance of these assignments can then be evaluated for each element or group individually ti. a performance score can be computed for each element or group of elements.

The question: What optimization algorithm would you recommend for efficiently solving (maximizing the sum of scores of individual elements) this problem with very large values of n and m (where n > m and n and m are in the order of 10^5)? As a side question, to what combinatorial optimization problem does this particular problem reduce?

Using genetic algorithms seems a bit off. Making a population of chromosomes, each with possible say 20000 group assignments for all elements... or is it? I have no idea what kind of mutation, selection and crossover operators to use on such large chromosomes.

Answer 1

The large values of n and m limit your choices. If you model it as n*m boolean decision variables, so in the order of 10^10 variables... then it might be to big to load a single instance into RAM memory. If you model it as 20*n variables of type M, then you limit the number of connections for a variable to an arbitrary number (20 in this case) and need to add a hard constraints that no 2 variables for the same n should have the same M value, but it would be loadable into RAM memory.

Presuming that your constraints (performance score) isn't trivial: the only optimization algorithms I 've seen scale to such a high number of variables is Local Search variants (Tabu Search, Late Acceptance, ...), for example in the Roadef2012 competition.