Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length
Introduce variables $y_{hi}$ together with constraints 
$y_{hi}=\sum_j (a_{hij} x_j + b_{hj})$ for all $h$ and $i$.
Introduce variables $z_h$ together with constraints 
$z_h\ge y_{hi}$ for all $h$ and $i$.
Then minimize $\sum_h z_h$.


The resulting linear program can be solved in time polynomially bounded in $\ell, m, n$ and the logarithm of the largest cost coefficient. 

(I am not sure whether you are asking for a strongly polynomial solution. 
This seems to be out of reach.)