# Binary variables state change minimization in MILP

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.

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

## 1 Answer

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}