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}\]

  • 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.



  1. Unless I'm missing something, what you propose seems overkill. First, couldn't you just rewrite with K binary variables as follows:

    min sum_i abs(a_i) * x_i
    s.t. sum_i x_i >= 1
    x_i binary

    And if this model is standalone (as opposed to a part of a larger model), why not just find the minimum abs(a_i), which can be done in linear time?

    1. Indeed, because abs(a * b) = abs(a) * abs(b), both objective and constraints are only dependent on abs(x_i)

  2. I think you inadvertently omitted sum_k y_{i,k} = 1 for all i.