1
$\begingroup$

I have solved and MILP that has binary variables: $b_h \quad \forall h \in\{0, 1, 2, ..n\}$

After solving, an example of the values of $b$ could be : $$ b=\{0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0 \} $$

$b$ represents the states of an engine (on/off) with time. Now I would like to introduce a restriction or extend the objective function in order to minimize the amount of state changes.

I though about including in the objective function the following. $$ f_{min}:\quad abs(b_h - b_{h-1}) \quad \forall h \in\{1, 2, ..n\} $$

I don't know how to properly linearize this or if there is a better way to do what I described.

$\endgroup$
  • $\begingroup$ there is a way to linearize $|b_h - b_{h-1}|$ $\endgroup$ – gt6989b Sep 12 '17 at 15:39
1
$\begingroup$

First of all, $|b_h-b_{h-1}|$ is not an objective function. You may however consider $\displaystyle\sum_{h=1}^{n} |b_h-b_{h-1}|$ as your objective function. Given your current assumptions, we can define the auxiliary continuous variable $y_h$ for each $h\in\{1,\dots,n\}$ which represents the value of $|b_h-b_{h-1}|$ (note that you can also define $y_h$ as a binary variable but sometimes it is not coputationally good to add extra integer variables to your model). We can express your problem as a mixed integer linear program as follows: \begin{align} \min & \sum_{h=1}^{n} y_h \\ & b_h-b_{h-1} \le y_h \ \ \ \ \ \ \forall h\in\{1,\dots,n\}\\ & b_{h-1}-b_{h} \le y_h \ \ \ \ \ \ \forall h\in\{1,\dots,n\}\\ & b_h \in \{0,1\} \ \ \ \ \ \ \ \ \ \ \ \ \ \forall h\in\{0,\dots,n\}\\ & y_h \ge 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall h\in\{1,\dots,n\}.\\ \end{align}

If the states are cyclic, then you may define an extra variable $y_{0}$ which represents the value of $|b_n-b_{0}|$. Your model would then be \begin{align} \min & \sum_{h=0}^{n} y_h \\ & b_h-b_{h-1} \le y_h \ \ \ \ \ \ \forall h\in\{1,\dots,n\}\\ & b_{h-1}-b_{h} \le y_h \ \ \ \ \ \ \forall h\in\{1,\dots,n\}\\ & b_n-b_{0} \le y_0 \\ & b_{0}-b_{n} \le y_0 \\ & b_h \in \{0,1\} \ \ \ \ \ \ \ \ \ \ \ \ \ \forall h\in\{0,\dots,n\}\\ & y_h \ge 0 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \forall h\in\{0,\dots,n\}.\\ \end{align}

| cite | improve this answer | |
$\endgroup$

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.