Mathematics Asked by Kamer73 on March 13, 2021
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.
Answered by LinAlg on March 13, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP