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

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.

• Is it zhihu where you found Vielma's review paper?
– xd y
Aug 30, 2021 at 15:43

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?

• Glad to help. If you are satisfied with it, please mark it as accepted. Aug 30, 2021 at 16:17
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.
• For the equivalence, your $Ax\le b$ should instead be $Ax < b$. You are right that I treated $C$ as a vector instead of a matrix. I guess we need clarification from the OP about which interpretation was intended. Aug 30, 2021 at 16:32