I want to find the minimum value of an expression like
$$ \lvert -1 + 2x + 6y + 14z \rvert + 2 \lvert -1 - 3x - 7y - 15z \rvert + 3 \lvert +1 + x \rvert + 4 \lvert +1 + y \rvert + 5 \lvert -1 + z \rvert $$
where $x$, $y$ and $z$ are integers, or more generally, find $$ \min_{\mathbf{x} \in \mathbb{Z}^d} \sum_{i=1}^n \lvert L_i(\mathbf{x}) \rvert $$
where $L_i$ are linear functions with integer coefficients. I have thought of the following approach:
For each possible set of $d$ linear functions $L_i$, set the $L_i$ to $0$, solve for $\mathbf{x} \in \mathbb{R}^d$, then try all possible roundings to $\mathbf{x} \in \mathbb{Z}^d$.
In my case, I have $d = n - 2$, and most components of $\mathbf{x}$ will already be integers. These constraints provide reasonable efficiency, with $O(d^2) = O(n^2)$ choices of $L_i$, and $O(1)$ possible roundings. However, I am not sure of the method's correctness.
Is the above method correct? Are there better / more efficient alternatives?
It is not correct. Consider e.g. $d=2$ with objective $ |5x -3y-1| + \left|(50/9) x - (32/9) y - 1\right|$. The summands are $0$ at $(1/2,1/2)$; rounding this, the four points with $x = 0$ or $1$ and $y=0$ or $1$ have values $2$ or $77/9$, but the minimum occurs at $(-1,-2)$ and $(2,3)$ with value $5/9$.
The problem can be expressed as a mixed integer linear programming problem:
minimize $\sum_{i=1}^n t_i$ subject to $t_i \ge L_i(x)$ and $t_i \ge -L_i(x)$ for $i=1\ldots n$, with $x \in \mathbb Z^d$.
There are various algorithms for this type of problem, e.g. branch-and-bound.