2
$\begingroup$

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}

$\endgroup$
4
  • 2
    $\begingroup$ What are the bounds on $x_2$ and $x_3$? $\endgroup$
    – RobPratt
    Apr 26 at 19:25
  • 2
    $\begingroup$ By any chance does $a=b\cdot d$? Otherwise the value of $x_1$ when $x_2 \ge c$ and $x_3 = d$ is ambiguous. $\endgroup$
    – prubin
    Apr 26 at 20:04
  • $\begingroup$ No, $a$ is not equal to $b \cdot d$. I will work on this ambiguity. Thanks! $\endgroup$ Apr 26 at 20:17
  • $\begingroup$ $x_2$ and $x_3$ are bounded by a max value from both sides, e.g., $-p_{max} \leq x_2 \leq p_{max}$ and $-e_{max} \leq x_3 \leq e_{max}$. $\endgroup$ Apr 26 at 20:21
8
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}

$\endgroup$
2
  • 1
    $\begingroup$ If this is meant to be an implementation of my answer, no I don't see why you would need to add two additional binary variables. if you move the $x_1$ model to a linearization of $x_1 = a\delta_1 + b\delta_2x_3$ you do not need any new binary variables as it is simply $-M(1-\delta_2) \leq y_1-x_3 \leq M(1-\delta_2)$ $\endgroup$ Apr 28 at 7:05
  • 1
    $\begingroup$ if it is your own attempt, well it looks correct(-ish), but the model is less clear to untangle, and more complex combinatorially. A start is to write the logical conditions and structure first to understand how the indicators relate to the initial model, and then write the MILP interpretations, instead of just listing the final MILP model. $\endgroup$ Apr 28 at 7:16

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.