If you have a good LP solver, then the linear programming approach often works well. You don’t want to implement your own simplex or interior point code for LP though. A specialized variant of the simplex method due to Barrodale and Roberts is a popular approach to this problem, but it takes some effort to implement this efficiently and you might be better ...


You should have a look at Satisfiability Modulo Theories or SMT for short. A huge number of problems can be thought of as instances of SMT for a particular theory. For example, correctly designing certain types of integrated circuits can be phrased as an SMT problem. The problem you're describing fits under the theory of quantifier-free linear integer ...


Thanks to Wolfgang Bangerth for pointing out that this can be rewritten as a linear problem. My reformulation would be: $$\min_{x\in\mathbb{R}^N}\|Ax-b\|_1 \implies$$ $$\min_{(x,y)\in\mathbb{R}^{N+M}}\sum_{i=1}^N y_i, $$ $$Ax - y \leq b$$ $$-(Ax+y) \leq -b$$ $$y\geq0$$

Only top voted, non community-wiki answers of a minimum length are eligible