Can you please help in formulating the following optimization problem:
Consider the problem of finding an $x\in\mathbb{R}^n$ that satisfies at least $k$ (with $1\le k\le n$) of the following $m$ constraints: $$a_i^Tx\le b_i,\quad\text{for } i=1,\dots,m. $$ Show that such a problem admits a formulation that involves only linear and binary constraints. Justify your answer. (Hint: Introduce binary variables $y_1,\dots,y_m\in\{0,1\}$ with $y_i=0$ if and only if the $i$th constraint must be satisfied.)
For $i\in\{1,\dots,m\}$, let $M_i$ be an upper bound on $a_i^T x - b_i$. Then the following linear constraints enforce the desired behavior: \begin{align} \sum_{i=1}^m (1 - y_i) &\ge k \\ a_i^T x - b_i & \le M_i y_i &&\text{for $i\in\{1,\dots,m\}$} \end{align} Note that you need only $y_i = 0 \implies a_i^T x \le b_i$ and not the converse.