Given constant matrices $A_1\in\mathbb{R}^{1\times l}$ and $A_2\in\mathbb{R}^{1\times l}$, and constants $b_i$, $i=1,\dots,n$. Consider the following mixed integer program (MIP) with decision variables $c_i\in\{0,1\}$ and $X=[x_1,\dots,x_n]\in\mathbb{R}^{l\times n}$ with $x_i\in\mathbb{R}^{l}$ for $i=1,\dots,n$.
Objective: min $\sum_{i=1}^{n} |c_iA_1x_i|$
Constraints: $A_2x_i \le c_ib_i$; $\;\;$ $\sum_{1}^nc_i \ge 1$; $\;\;$ $c_i\in\{0,1\}$.
This problem is intractable because the objective function contains the product of the decision variables $c_i$ and $x_i$. Is it possible to derive a tractable formulation for this problem?
You can linearize the problem as follows. Introduce nonnegative decision variables $y_i$ to represent $|c_i A_1 x_i|$, change the objective to minimizing $\sum_i y_i$, let $M_i$ be a small constant upper bound on $|A_1 x_i|$, and impose additional linear big-M constraints \begin{align} A_1 x_i - y_i &\le M_i(1-c_i) &&\text{for all $i$} \\ -A_1 x_i - y_i &\le M_i(1-c_i) &&\text{for all $i$} \end{align}