How to deal with a decision variable in the objective function that depends on if-else conditions involving other decision variables?

Question

I'm modeling an optimization problem in which a decision variable $x_1$ in the objective function depends on if-else conditions involving decision variables $x_2$ and $x_3$, as the following equation, where $a$, $b$, $c$, and $d$ are constants. I know a possibility would be using binary variables, but I'm not sure how to do it. Could someone help me? \begin{equation} x_1 = \begin{cases} a, & \text{if } x_2 \geq c \ \text{and} \ x_3 \geq d\\ b \cdot x_3, & \text{if } x_2 \geq c \ \text{and} \ 0 \leq x_3 \leq d\\ 0, & \text{otherwise} \end{cases} \end{equation}

Answer 1

Introduce four binary variables indicating which region you are in and the function value.

$$\begin{align} \delta_1 &\rightarrow x_2\geq c, ~x_3\geq d, ~x_1 = a\\ \delta_2 &\rightarrow x_2\geq c, ~0\leq x_3 \leq d, ~x_1 = bx_3\\ \delta_3 &\rightarrow x_2\leq c, ~x_1 = 0\\ \delta_4 &\rightarrow x_3\leq 0, ~x_1 = 0 \end{align} $$

You are in one of the regions so $\delta_1+\delta_2 +\delta_3+\delta_4=1$, and all the implications are standard big-M representable such as $x_2-c\geq -M(1-\delta_1), -M(1-\delta_1) \leq x_1-a\leq M(1-\delta_1)$ etc. By exloiting structure and linearity in some terms this can be reduced and simplified, but this is the basic model.

Answer 2

The quickest way to study this is to use Generalized Disjunctive Programming.

If we use disjunctions to formulate the problem, we get:

$$ min/max \quad z=f(x)\\ \begin{bmatrix} Y_1 \\ x_1 = a \\ x_2 \geq c\\x_3 \geq d \end{bmatrix} \veebar \begin{bmatrix} Y_2 \\ x_1 = b·x_3 \\ x_2 \geq c\\0\leq x_3 \leq d \end{bmatrix} \veebar \begin{bmatrix} Y_3 \\ x_1 = 0 \\ x_2 \leq c\\ \end{bmatrix} \veebar \begin{bmatrix} Y_4 \\ x_1 = 0 \\ x_3 \leq 0\\ \end{bmatrix}$$

Where $Y_1, ... Y_4$, are Boolean variables that represent the disjunctions.

What Johan answered is perfectly correct, since it is the Big-M formulation for this GDP problem. I am just gonna add the Convex Hull formulation, which for linear problems tends (not always) to produce a tighter feasible region.

First you have to disaggregate the variables. Let's assume that the set of disjunctions is $i\in \{1,2,3,4\}$, we dissagregate variables $x_1,...x_4$ into $x_1^i, ..., x_4^i$:

$ \sum_i x_1^i = x_1\\\sum_i x_2^i = x_2\\\sum_i x_3^i = x_3$

Then, consider a binary variable $y_i$ that will have a value of 1 if disjunction $Y_i$ is active and 0 otherwise.

We also need limits for all degrees of freedom. But normally it is good to have limits for all the variables. These parameters will be called $\overline{x_1},\overline{x_3},\overline{x_3}$ for the upper bounds and $\underline{x_1},\underline{x_3},\underline{x_3}$ for the lower bounds.

The whole formulation would therefore be:

$$ min/max \qquad z = f(x) \\ \sum_i x_1^i = x_1\\\sum_i x_2^i = x_2\\\sum_i x_3^i = x_3 \\ x_1^1 = ay_1 \\ x_2^1 \geq cy_1 \\ x_3^1 \geq dy_1 \\ x_1^2 = bx_3^2 \\ x_2^2 \geq cy_2 \\ x_3^2 \geq 0 \\ x_3^2 \leq dy_2 \\ x_1^3 = 0 \\ x_2^3 \leq cy_3 \\ x_1^4 = 0 \\ x_3^4 \leq 0 \\ \underline{x_1} y_i\leq x_1^i \leq \overline{x_1}y_i \qquad \forall i \\ \underline{x_2} y_i\leq x_2^i \leq \overline{x_2}y_i \qquad \forall i \\ \underline{x_3} y_i\leq x_3^i \leq \overline{x_3}y_i \qquad \forall i \\ \underline{x_4} y_i\leq x_4^i \leq \overline{x_4}y_i \qquad \forall i \\ $$

And it is missing the logic constraints for the binaries. Since it is an exclusive OR, we have to add the following:

$$ \sum_i y_i = 1$$

There are some redundancies there in the constraints, but it is the tightest convex envelope that can be generated for this problem.

However, you have to also notice that, if the disjunctions are not continuous (This meaning, $Y_2$ gives a different result for $x_1$ when $x_3=d$ than $Y_1$ does, for example), it will be able to choose any of the two disjunctions indistinctively. This may be the intended behavior, of course.

Answer 3

Is the following model correct?

Consider $\delta_i$ as binary variables, whereas $x_i$ and $y_1$ are continuous.

\begin{equation} x_1 = a \delta_1 + y_1 \end{equation}

For the first if statement: \begin{equation} \begin{matrix} c - M(1 - \delta_2) \leq x_2 \leq c + M\delta_2\\ d - M(1 - \delta_3) \leq x_3 \leq d + M\delta_3\\ \delta_2 + \delta_3 \geq2\delta_1 \end{matrix} \end{equation}

For the second if statement: \begin{equation} \begin{matrix} - M(1 - \delta_4) \leq x_3 \leq M\delta_4\\ d - M\delta_5 \leq x_3 \leq d + M(1 - \delta_5)\\ \delta_2 + \delta_4 + \delta_5 \geq 3\delta_6\\ bx_3 - M(1 - \delta_6) \leq y_1 \leq bx_3 + M(1 - \delta_6)\\ -M\delta_6 \leq y_1 \leq M\delta_6\\ \end{matrix} \end{equation}