I am currently trying to discretize a non-linear problem in order to express it as a MIP. I don't think I am talking exactly of a SOS as order doesn't really matter; nonetheless, it seems possible to consider as such. I will edit as soon as someone gives a better name for those variables. I put in italics the physical situation if it seems of interest to someone: I am trying to take into account the thermal inertia from one hour to another.
Temperature discretization at hour h:
$\sum_{i}\epsilon_{i}=1; \forall i \in \{1,...N\}: 0 \le \epsilon_{i} \le 1 \space and \space \epsilon_{i} \in \{0;1\} - binaries$
Temperature discretization at hour h-1:
$\sum_{j}\gamma_{j}=1; \forall j \in \{1,...N\}: 0 \le \gamma_{j} \le 1 \space and \space \gamma_{j} \in \{0;1\} - binaries$
I need to linearize:
$\sum_{i,j} \epsilon_{i} \gamma_{j} T_{i} T_{j}$
$T_{i}$ correspond to the temperature levels
I know this could be done by introducing: $ z_{i,j} = \epsilon_{i} \gamma_{j}$ and the corresponding constraints such as in here, but it represents a number of variable of N².
My question is therefore: is it possible to reduce that number? Considering the constraints, I feel that a mathematical astuce might exist.
You can rewrite it as $\sum_i \epsilon_i (\sum_j \gamma_j T_i T_j)$ and treat it as a product of a binary and a continuous variable. I will assume that the temperatures are nonnegative, so switch to Kelvin if necessary (numerically it would be better to switch to an arbitrary unit in a way that the smallest temperature is $0$). The expression then becomes $\sum_i z_i$ and the following constraints ensure that $z_i = \epsilon_i (\sum_j \gamma_j T_i T_j)$
$$z_i \leq \epsilon_i M_i$$ $$z_i \leq \sum_j \gamma_j T_i T_j$$ $$z_j \geq \sum_j \gamma_j T_i T_j - (1-\epsilon_i)M_i $$ $$z_j \geq 0$$ with $M_i = \max_j T_i T_j$. This scales linearly in $n$ instead of quadratically. You should verify that it is actually a better method, because in the end what matters is the strength of the relaxation.