3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Is it zhihu where you found Vielma's review paper? $\endgroup$
    – xd y
    Aug 30 at 15:43
11
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Glad to help. If you are satisfied with it, please mark it as accepted. $\endgroup$
    – RobPratt
    Aug 30 at 16:17
  • $\begingroup$ Hi Rob, please check my answer. $\endgroup$
    – xd y
    Aug 30 at 16:22
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – RobPratt
    Aug 30 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.