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.

### References

- How to use abs() and max() operator in pulp?, https://stackoverflow.com/questions/78079656/how-to-use-abs-and-max-operator-in-pulp
- Linear Programming and LAD Regression, https://yetanothermathprogrammingconsultant.blogspot.com/2017/11/lp-and-lad-regression.html

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

ReplyDeletemin 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?

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

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

ReplyDeleteThanks.

Delete