For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of:


$$
\max\_{x \in [0,1]^n} \|Ax+b \|\_1
$$


Or is this problem NP-hard?



How can I find the maximum value of this function?
Note that since the objective is convex, 
there are optimal solutions that are extreme points of the feasible region, i.e. we can assume all $x\_i \in \{0,1\}$. 


We can encode an Ising hamiltonian in this problem, with spins $\sigma\_i = (-1, 1)$ corresponding to $x\_i = (0, 1)$. 


Thus a term 
$$J \sigma\_1 \sigma\_2 = \cases{ | J x\_1 + J x\_2 - 2 J| - J & if $J > 0$\cr
 |J x\_1- J x\_2| + J & if $J < 0$ }$$
while for single spins
$$ h \sigma = \cases{|2h x | - h & if $h > 0$\cr |2hx - 2h| + h & if $h < 0$\cr}$$


Maximizing (or minimizing) such a Hamiltonian is well-known to be NP-hard.


