You've just discovered by combinatorial optimization is considered a "hard" problem. In general searching for an optimum integer solution takes a very long time as you have discovered.
If you can accept merely a pretty-good solution, there are heuristics you can apply. One of them is...