**Least Median of Squares regression**problem:

\[\begin{align}\min\>&z\\&\delta_i=1 \Rightarrow \> –z \le r_i \le z\\&\sum_i \delta_i = h\\&r_i = y_i - \sum_j X_{i,j} \beta_j\\&\delta_i \in \{0,1\} \end{align}\] |

Here \(X\) and \(y\) are data. Modern solvers like Cplex and Gurobi support **indicator constraints**. This allows us to directly pass on the above model to a solver without resorting to other formulations (such as binary variables with big-M constraints or SOS1 structures).

This particular model is interesting: it has an unbounded LP relaxation. E.g. the start of the Cplex log shows:

Nodes Cuts/ 0 0 unbounded 0 . . . |

Gurobi has some real problems on this model:

Optimize a model with 48 rows, 97 columns and 188 nonzeros Root relaxation: unbounded, 77 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work 0 0 postponed 0 - - - - 0s ... 139309129 6259738 0.02538 65 23 0.26206 - - 28.3 28775s |

This model does not seem to finish (the model has only 47 discrete variables so this log indicates something is seriously wrong: this model should solve in a manner of seconds). Gurobi was never able to establish a lower bound (column **BestBd**). Notice that Gurobi translates the implications to SOS1 variables (see [1] for the SOS1 version of this model).

There is a simple work around: add the bound \(z \ge 0\). Now things solve very fast. We have a normal bound and no more any of these “postponed” nodes.

Root relaxation: objective 0.000000e+00, 52 iterations, 0.00 seconds Nodes | Current Node | Objective Bounds | Work 0 0 0.00000 0 24 - 0.00000 - - 0s . . . |

The bound \(z\ge 0\) can be deduced from the constraints \(–z \le r_i \le z\) (we know \(h\) of them have to hold). Presolvers are not able to find this out automatically.

See [2] for some other interesting observations on indicator constraints.

Update: Gurobi has identified the problem and it has been fixed (available in next version).

##### References

- Integer Programming and Least Median of Squares Regression, http://yetanothermathprogrammingconsultant.blogspot.com/2017/11/integer-programming-and-least-median-of.html
- Belotti, P., Bonami, P., Fischetti, M. et al.,
*On handling indicator constraints in mixed integer programming,*Comput Optim Appl (2016) 65: 545.