## Friday, April 12, 2024

### Instead of integers use binaries

In [1], a small (fragment of a) model is proposed:

High-Level Model
\begin{align} \min\> & \sum_i | \color{darkblue}a_i\cdot \color{darkred}x_i| \\ & \max_i |\color{darkred}x_i| = 1 \\ & \color{darkred}x_i \in \{-1,0,1\} \end{align}

Can we formulate this as a straight MIP?

The objective is not very complicated. We can handle this with standard formulations, similar to what is used in LAD (Least Absolute Deviation) regression [2]. The constraint is more problematic. It can be interpreted as "at least one of the $$\color{darkred}x_i$$ should be nonzero". This type of counting typically needs binary variables. When we need binary variables anyway, it may be easier just to go all the way, and define: $\color{darkred}y_{i,k} = \begin{cases} 1 & \text{if \color{darkred}x_i=k} \\ 0 & \text{otherwise}\end{cases}$ where $$k \in \{-1,0,1\}$$. With this, a straightforward model is:

Binary Expansion
\begin{align} \min\> & \sum_{i,k} | \color{darkblue}a_i | \cdot |\color{darkblue} k| \cdot \color{darkred}y_{i,k} \\ &\color{darkred}x_i = \sum_k \color{darkblue} k \cdot \color{darkred}y_{i,k}\\ & \sum_k \color{darkred}y_{i,k} = 1 \\ & \sum_i \left(\color{darkred}y_{i,-1}+\color{darkred}y_{i,1}\right) \ge 1 \\ & \color{darkred}x_i \in \{-1,0,1\} \\&\color{darkred}y_{i,k} \in \{0,1\}\end{align}

Notes:
• If we want we can make $$\color{darkred}x_i$$ a continuous variable.
• The first constraint is an accounting row.
• We can also drop $$\color{darkred}x_i$$ completely from the model and recover it during reporting of the solution. I.e. remove the accounting row from the model.
It is not unusual that a model with integer variables is difficult to formulate as a MIP, while a corresponding model with binary variables is straightforward.