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.

  • $\begingroup$ However in your example the linear functions do not have integer coefficients. $\endgroup$ – D. G. Apr 25 '19 at 12:16
  • $\begingroup$ 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? $\endgroup$ – D. G. Apr 25 '19 at 12:18
  • $\begingroup$ OK, just multiply all coefficients by $9$. $\endgroup$ – Robert Israel Apr 25 '19 at 12:58
  • $\begingroup$ Yours is not polynomial time either: the number of roundings is $2^d$. $\endgroup$ – Robert Israel Apr 25 '19 at 13:00
  • $\begingroup$ 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. $\endgroup$ – D. G. Apr 25 '19 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.