3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What are the sides of the square? $\endgroup$
    – RobPratt
    Commented Jul 20, 2022 at 1:01
  • $\begingroup$ Any big-M number. $x, y \in [-M, M]$. I wonder if that is necessary. The only reason I said a square in the question is because I wanted to give geometric intuition to the problem. $\endgroup$
    – Kumar
    Commented Jul 20, 2022 at 1:05

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for your response. I suppose here $M_i$ are vectors to match the number of constraints in $A_i$. Is it possible to solve with two binary variables, instead of 4. $\endgroup$
    – Kumar
    Commented Jul 20, 2022 at 12:06
  • $\begingroup$ Yes, both $b_i$ and $M_i$ are vectors. Yes, you can capture the four possibilities with two binary variables, but I would be surprised if it makes much difference in the solve time. $\endgroup$
    – RobPratt
    Commented Jul 20, 2022 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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