I am trying to solve an optimization problem, in order to find an optimal runtime schedule for a machine.
It involves one boolean variable $x_{t} \in \mathbb{\{0,1\}}$, that describes whetever the machine is on or off at a given time $t$.
One part off the cost function, has to describe the effect that turning off the machine has a certain cost. To simplify we normalize the cost to 1.
Here is how i have chosen to describe this part of the cost function.
$$ c_{off}=(x_{t}-x_{t+1})(1-x_{t+1})=x_{t}-x_{t+1}-x_{t+1}x_{t}+x_{t+1}^{2} $$
This captures what we want because $(x_{t}-x_{t+1})\neq 0$ only when the machine changes state from $t$ to $t+1$. Furthermore $(1-x_{t+1})\neq 0$ enforces that the cost only applies to a turn off and not a turn on. It may happen that switching on the machine hast a different cost, but it should be completely analogous.
The drawback is that we introduce a square into the costfunction, that renders our function into a relatively hard to solve Mixed Integer Quadratic Problem (MIQP), instead of a much simplear Mixed Integer Linear Problem (MILP).
However i fail to rewrite the cost function in an appropriate way such that it is linear, but still behaves as expected. Does anyone know if such a reformulation is possible, and if so how it looks like?
The $x_{t+1}^2$ is not a problem because if $x \in \{0,1\}$, $x^2 = x$. The $x_t x_{t+1}$ can be turned into a new binary variable $y_t$ such that $y_t \ge x_t + x_{t+1} - 1$ and $y_t \le (x_t + x_{t+1})/2$. You may need only one of these...