How to linearize a constraint with a maximum of a linear function

Question

I want to linearize the following statement into a MILP: $\forall x\in \mathbb{R}^{m}$ satisfying $Cx \le d$, $\exists i\in \{1,\cdots,m\}$ such that $a_i^Tx \ge b_i$, where $a_i$ and $b_i$ are given coefficients.

My previous trial is based on Farkas's theorem of alternative. Specifically, I previously transform the above statement into: there is no feasible solution to $Ax \le b, Cx \le d$, where $A$ and $b$ are the vertical concatenation of $a_i$ and $b_i$, respectively. Then, such statement can be transformed into another linear system according to Farkas's lemma. However, such modeling will encounter a problem: the big-M modeling used in $Cx \le d$ makes the LP relaxation quite loose, which makes the solver slow.

Therefore, I am wondering is it possible to linearize it through the following modeling idea: $\forall x\in \mathbb{R}^{m}$ satisfying $Cx \le d$, $\exists i\in \{1,\cdots,m\}$, $\min_{x}\{a_i^Tx\} \ge b_i$? More specifically, I try to model such statement following the disjunctive modeling principle suggested in "Vielma J P. Mixed integer linear programming formulation techniques[J]. Siam Review, 2015, 57(1): 3-57." However, I am unable to find an appropriate way to model the problem with disjunctive polytopes.

Answer 1

You can model the logical implication $$Cx < d \implies \bigvee_{i=1}^m \left(a_i^T x \ge b_i\right)$$ by introducing $m+1$ binary variables $y_i$, where $i\in\{0,\dots,m\}$, and linear constraints \begin{align} d - Cx &\le M_0 y_0 \tag1\\ \sum_{i=1}^m y_i &\ge y_0 \tag2 \\ b_i - a_i^T x &\le M_i (1-y_i) &&\text{for $i\in\{1,\dots,m\}$} \tag3 \end{align} Constraint $(1)$ enforces $Cx < d \implies y_0=1$. Constraint $(2)$ enforces $y_0 = 1 \implies \bigvee_{i=1}^m \left(y_i = 1\right)$. Constraint $(3)$ enforces $y_i = 1 \implies a_i^T x \ge b_i$.

Is this the big-M formulation you already tried?

Answer 2

I think your constraint is equivalent to $$ \neg \left[\begin{pmatrix} A\\ C \end{pmatrix} x \leq \begin{pmatrix} b\\ d\end{pmatrix}\right] $$ because $$ \begin{align} &Cx \leq d \;\Longrightarrow\;\bigvee(a_i^Tx \geq b_i)\\ \Longleftrightarrow\;&\neg(Cx \leq d) \;\vee\;\neg(Ax\leq b)\\ \Longleftrightarrow\;&\neg(Ax\leq b \;\wedge Cx\leq d) \end{align} $$

So it means at least one row is violated, which could be modeled as $$ Ax \geq b - M_1\circ (1-u)\\ Cx \geq d - M_2\circ (1-v)\\ \sum u_i+\sum v_j \geq 1 $$ where $\circ$ means element-wise product.

If the matrix $C$ is a row vector, this model is identical with RobPratt's. But in his model, when $Ax \leq b$, it forces $y_0=0$, then forces $Cx \geq d$, which is unnecessary(?).

Edit: some $\varepsilon$'s are absolutely needed.