A convex piecewise-linear function can be defined as $f_i(x) = \textbf{max}_{j=1,\cdots,m} a_jx+b_j$ where $a_j, b_j, x \in \mathbb{R}$.
To find its minimum, I can construct a linear program using auxiliary scalar variable
$t$. Namely:
$$
\textbf{minimize } t \\
\textbf{ subject to } a_ix+b_i \leq t, i = 1, \cdots m
$$
And i can use similar strategy when solving minum of $f_1(x) + f_2(x)$.
Suppose i have a set of piecewise-linear functions $F = \{f_1(x), \cdots, f_i(x), \cdots, f_n(x) \}$.
How can i efficiently find an optimal partition $(L, R)$ of $F$ such that the $\textbf{min} \sum_{l \in L} f_l(x) + \textbf{min} \sum_{k \in R} f_k(x)$ is minimized ?
Best Answer
As in https://math.stackexchange.com/a/4246169/683666, introduce a binary decision variable $z_i$ to indicate whether $i\in L$. Now minimize $t_1+t_2$ subject to linear big-M constraints \begin{align} a_i x + b_i - t_1 &\le M_i(1-z_i) &&\text{for $i\in\{1,\dots,m\}$} \tag1 \\ a_i x + b_i - t_2 &\le M_i z_i &&\text{for $i\in\{1,\dots,m\}$} \tag2 \\ \end{align} Constraint $(1)$ enforces the logical implication $i\in L \implies a_i x+ b_i \le t_1$. Constraint $(2)$ enforces the logical implication $i\in R \implies a_i x+ b_i \le t_2$.