> As with many NP-hard problems (e.g. SAT, TSP), there are very good solvers these days that are much faster than anything you could ever hope to write yourself – and they produce fully optimal solutions.

And if it's not fast enough, you can use one of a number of relaxations to a standard LP and call it a day.