Turn off the ovens! An optimization problem

Question

The problem is more abstract, but can be illustrated nicely using ovens. A oven can produce any heat, but is most efficient when it produces $c$ heat. The inefficency increases quadratically as one moves away from the ideal temperature.

For a concretely example imagine we have the following three ovens

$ \hspace{1cm} A = 10, B = 15, C = 20 $

The efficiency loss could then be modeled by

$\hspace{1cm} E(x,y,z) = g(10, x) + g(15, y) + g(20, z) $

Where $g$ is given as

$ \hspace{1cm} g(a, x) = \left\{ \begin{array}{ccc} 100(a-x)^2/a & \text{if} & x > 0 \\ 0 & \text{if} & x = 0 \end{array} \right. $

The problem is at which rate the ovens should run to generate the heat $T$. In other words minimize $E(x,y,z)$ subject to $x + y + z = T$.

Is there some efficient way to achieve this? For 3, I can iterate over them but for 10 this is harder...

Answer 1

The inefficiency is a quadratic function of your variables, and the constraint is a hyperplane. By an appropriate (fairly easy) linear transformation the inefficiency is the Euclidean distance of your variable vector to the origin, and then you are minimizing the distance from the origin to a variable point on a hyperplane: the minimum is reached at the orthogonal projection of the origin on the hyperplane.

Answer 2

I was able to solve this with the global MINLP solvers Baron and Couenne.

The $y$ variables are binary variables indicating if an oven is on or off. I added an implication $y_i=0 \Rightarrow x_i=0$. The other way around is not needed (if $x_i=0$ the objective will make sure $y_i=0$ as that is better).

The option $optcr=0$ sets a tolerance so that global optimal solutions are found, instead of just good solutions.

The results for $T=23$ look like:

----     29 PARAMETER T                    =       23.000  heat

----     29 PARAMETER a  ideal temperature

A 10.000,    B 15.000,    C 20.000


----     29 VARIABLE y.L  use oven

A 1.000,    B 1.000


----     29 VARIABLE x.L  temperature oven

A  9.200,    B 13.800


----     29 VARIABLE loss.L  efficieny loss

A 6.400,    B 9.600


----     29 VARIABLE E.L                   =       16.000  total efficiency loss

Oven C is turned off here. You can try out Baron and Couenne yourself on NEOS. Or if you post some larger data set I am happy to try that.

Update

I was not completely happy with my model. Indeed we can formulate it as a quadratic model thereby making the model less non-linear. In fact it can be stated as a convex MIQP (Mixed Integer Quadratic Programming) model. This will allow many more solvers to be able to handle this problem. It is a little bit more complex however:

The idea is to add a slack variable $s$ that is left to float freely when the oven is off ($y_i=0$). In that case the optimizer will choose a zero loss automatically. If the oven is turned on ($y_i=1$) we require that the slack is zero. In that case the correct loss is calculated.

For a compact conic formulation of this problem see here.