converting con-convex region to convex

Question

I'm trying to model a problem using Linear Programming theory, though the feasible region of the problem is non-convex. Yet, I think using Big-M and some binary variables this region can be converted to a convex feasible region. Is there any way to convert the following non-convex region to a convex region (with higher dimension) using integer programming "if-then" constraints?

Answer 1

You can introduce a binary variable $z$, where $z=1$ indicates that the point $(x,y)$ is in the $1 \times 3$ rectangle and $z=0$ indicates that $(x,y)$ is in the trapezoid. Now impose the following linear big-M constraints to enforce that: \begin{align} 0 \le x &\le 2 + z \\ x - y &\le 3z \\ 1-z \le y &\le 2-z \\ \end{align} Checking the two cases, we see that \begin{align} z=1 &\implies (x,y) \in [0,3] \times [0,1] \\ z=0 &\implies x \in [0,y] \land y \in [1,2] \\ \end{align} More generally, you can represent a union of polyhedra $P_i$ by introducing a binary variable $z_i$ for each one, along with linear constraints $\sum_i z_i=1$ and linear big-M constraints that enforce $z_i=1 \implies x \in P_i$.