Balancing scales

Question

Suppose I had $N$ rocks with known weights $w_n$. How could I set all rocks on either side of a weight balance to reach an optimal level of balance? Put formally, is there a way I can either solve or approximately solve the following integer program without using an exhaustive search?

\begin{align} \min_x \left| \sum_n w_n x_n\right| \\ x_n \in \{-1, +1\} \end{align}

Answer 1

This is a version of the subset sum problem which is well known to be NP-Hard. Branch and bound methods will work well for small instances, but if the number of $w_{n}$ is large this problem rapidly becomes practically intractable.

Answer 2

I can't predict performance (never having tried it myself), but you could probably get a decent (not necessarily optimal) solution with a few basic heuristics. Setting aside an integer programming approach, which works for small instances but may not scale all that well, here's what I would try. $N$ is the number of objects in what follows.

1. Sort the objects in descending weight order ($O(N\log N)$), then assign them to sides using the pattern LRRLLRRL... (L = left, R = right). Evaluate the objective value of the solution.
2. Try to improve the solution by considering swaps of pairs of objects (one from each side). Evaluate all pairs ($O(N^2)$) at each iteration and accept the swap that makes the most improvement. This is a analogous to the 2-opt heuristic for the TSP.
3. If not exhausted, repeat the above considering all possible swaps of one object from one side with two objects from the other side ($O(N^3)$). This is analogous to the 3-opt heuristic for the TSP.

As an alternative to taking the best swap at each step, you could take the first one you find that makes an improvement (possibly faster, possibly less effective).

You could also try any of the vast collection of metaheuristics (genetic algorithms, tabu search, simulated annealing, ...).