Piecewise function with two variables

Question

I have a square like region centered at the origin, which is divided into 4 sub-regions. Region 1 can formed from by the diagonal of a square, $x + y \leq 0$. Region 2 is formed by joining the center of the square, and midpoint of one of the sides $x + y \geq 0, y \geq 0, x \leq 0$. Region 3 is formed by joining the center of the square, and midpoint of the opposite side, $x + y \geq 0, y \leq 0, x \geq 0$. Region 4 is the remaining piece, $x + y \geq 0, y \geq 0, x \geq 0$. I want to model a function $g(x, y)$ which takes the value $g_1(x, y)$ in region 1, $g_2(x, y)$ in region 2, $g_3(x, y)$ in region 3, and $g_4(x, y)$ in region 4.

I thought of modeling this with disjunctive constraints using two binary variables $z_1$ and $z_2$ such that $z_1 = 0, z_2 = 0$ in region 1, $z_1 = 1, z_2 = 0$ in region 2, $z_1 = 0, z_2 = 1$ in region 3, and $z_1 = 1, z_2 = 1$ in region 4. However, I am not sure how to use two binary variables in the region specific constraints without using product of binary variables. Is it possible to model $g(x, y)$ as linear mixed integer program.

Answer 1

You have a disjunction of four polyhedra $A_i x \le b_i$. Introduce four binary variables $r_i$ (one per region) and impose linear constraints: \begin{align} \sum_{i=1}^4 r_i &= 1 \\ A_i x - b_i &\le M_i (1 - r_i) &&\text{for $i\in\{1,2,3,4\}$} \\ \end{align} Now $$g(x,y) = \sum_{i=1}^4 g_i(x,y) r_i,$$ which you can enforce with further big-M constraints $$L_i (1-r_i) \le g(x,y) - g_i(x,y) \le U_i (1-r_i)$$

---

If you want to use only two binary variables instead of four, relax each $r_i$ and linearize \begin{align} r_1 &= (1-z_1)(1-z_2) \\ r_2 &= z_1(1-z_2) \\ r_3 &= (1-z_1)z_2 \\ r_4 &= z_1 z_2 \end{align} by linearizing the product $z_1 z_2$ in the usual way.