TransWikia.com

Linearize product of Two Special Ordered Sets and minimize number of variables

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.

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP