[Solved]: Minimize the maximum component of a sum of vectors

Problem Detail: 

I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$, find a function $f$ minimizing the expression

$$\max_k \sum_i a_{i,f(i),k}$$

An example using a different formulation might make it clearer: You're given a set of sets of vectors like

{     {(3, 0, 0, 0, 0), (1, 0, 2, 0, 0)},     {(0, 1, 0, 0, 0), (0, 0, 0, 1, 0)},     {(0, 0, 0, 2, 0), (0, 1, 0, 1, 0)} } 

Choose one vector from each set, so that the maximum component of their sum is minimal. For example, you may choose

(1, 0, 2, 0, 0) + (0, 1, 0, 0, 0) + (0, 1, 0, 1, 0) = (1, 1, 2, 1, 0) 

with the maximum component equal to 2, which is clearly optimal here.

I'm curious if this is a well-known problem and what problem-specific approximate solution methods are available. It should be fast and easy to program (no ILP solver, etc.). No exact solution is needed as it's only an approximation of the real problem.

---

I see that I should have added some details about the problem instances I'm interested in:

• $i \in \{0, 1, \ldots, 63\}$, i.e., there're always 64 rows (when written as in the above example).
• $j \in \{0, 1\}$, i.e., there're only 2 vectors per row.
• $k \in \{0, 1, \ldots, N-1\}$ where $N$ (the vector length) is between 10 and 1000.

Moreover, on each row the sum of the elements of all vectors is the same, i.e.,

$$\forall i, j, j':\quad \sum_k a_{i,j,k} = \sum_k a_{i,j',k}$$

and the sum of the elements of the sum vector is less than its length, i.e.,

$$\sum_k \sum_i a_{i,f(i),k} < N$$

Asked By : maaartinus

Answered By : hi mods

Reduction from 3SAT to the two-vector version: given a formula, let $i$ index variables, $j \in \{0,1\}$, and $k$ index clauses. Let $a_{i,j,k}$ be the number of times variable $i$ appears positively (if $j = 0$) or negatively (if $j = 1$) in clause $k$. OPT is less than $3$ iff the formula is satisfiable (the bijection is obvious).

How I would attack this problem: large neighborhood search. Start with any solution. Choose $r$ rows at random. Use brute force to find the best solution where $f$ can change only on those rows—very doable for even moderate $k$ given that the problem size is $64$ rows. Repeat.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2741