Select the smallest strict positive value from a list of variables in a linear program.

Question

I have constraints set up for my Linear Program.

The constraints enforce a certain amount of decision variables $R_{w,h}$ to be either $0$ or $1$ (0-1 variable).

The value to minimise is the difference between the largest and smallest $w*h$ for which $R_{w,h} = 1$.

In my application it holds that $0 \lt w*h$.

An initial attempt is to implement a $min$ and $max$ behaviour in additional linear constraints and subtract the results. This is OK for the $max$ part, as we just have to find the largest $R_{w,h}*w*h$. But for finding the minimum, we can't just find the smallest $R_{w,h}*w*h$ because that'll result in a $0$ if $R_{w,h} = 0$ and that is not the desired result (see above).

The method suggested in an answer here is thus not applicable.

Is there a way to linearise this or is this inherently non-linear?

Answer 1

Something like:

\begin{align} \min\> & whmax - whmin\\ & whmax \ge R_{w,h} \cdot w \cdot h & \forall w,h\\ & whmin \le w \cdot h + M (1-R_{w,h}) & \forall w,h\\ \end{align} where $M$ is a large enough number (e.g. $\max(w)\cdot\max(h)+1$).