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

$\endgroup$

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.