# Find minimum sum over absolute values of linear functions

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.

• However in your example the linear functions do not have integer coefficients. – D. G. Apr 25 '19 at 12:16
• I am under the impression that the more general algorithms would be inefficient. Is there a more specific algorithm that can run in polynomial time, if the one I was considering remains incorrect? – D. G. Apr 25 '19 at 12:18
• OK, just multiply all coefficients by $9$. – Robert Israel Apr 25 '19 at 12:58
• Yours is not polynomial time either: the number of roundings is $2^d$. – Robert Israel Apr 25 '19 at 13:00
• You are right about multiplying the coefficients, easy fix... However, the number of roundings is constant, because I can guarantee that $L_i(\mathbf{x}) = k_i(x_j + s_j)$ for $d$ values of $i$, as in the concrete example I gave. – D. G. Apr 25 '19 at 13:08