Formulating an Optimization Problem

Question

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.)

The hint is pretty helpful, do you understand what it's telling you to do? — 79037662, Sep 20 '19 at 14:43

score 0 · Accepted Answer · answered Sep 21 '19 at 00:32

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.

Formulating an Optimization Problem

1 Answers1