1
$\begingroup$

my given problem is:

choose n-vectors from n-sets (one vector from each set) so that the biggest element in the sum of the chosen vectors is minimal. Unfortunately the problem is NP-hard. So I'm looking for a heuristic. However i don't know a name for that kind of problem so i couldn't find anything in literature.

Do you have any idea for a good heuristic solution?

Edit

The vectors can contain negative numbers, have the same size and are bounded

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

First of all, I would suggest to model the problem as Mixed Integer Program and try to solve it with a MIP solver. If it turns out to be to hard because the problem is too large, you can try a heuristic procedure. Your problem seems to fit for neighbourhood search algorithms, i.e. you run through the search space by always exchanging one (or a few) of the vectors by other vectors and compare the resulting objective value. Probably a Simulated Annealing algorithm will do.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .