Routines for solving the underdetermined box-constrained integer least squares problem $$ \min_{\boldsymbol{x}\in \mathbb{Z}^n,\ \boldsymbol{l} \leq \boldsymbol{x}\leq \boldsymbol{u}}\|\boldsymbol{y}-\boldsymbol{B}\boldsymbol{x}\|_2, $$ where \(\boldsymbol{B} \in \mathbb{R}^{m\times n}\) with \(rank(\boldsymbol{B}) < n\), \(\boldsymbol{y}\in \mathbb{R}^n\), \(\boldsymbol{l}\in \mathbb{Z}^n\) and \(\boldsymbol{u}\in \mathbb{Z}^n\) (last updated: December 2022):

If you use this package in your research work to be published, please include explicit mention of the package in your publication:

X.-W. Chang. MILES: MATLAB package for solving mixed integer least squares problems, School of Computer Science, McGill University, http://www.cs.mcgill.ca/~chang/software/MILES.php. Last updated: December 2022.

• Direct tree search method
  • ubils.m for a user who wants to view the source code.
  • ubils.zip (includes three files) for a user who wants to run the code faster (sub-functions are in MEX form)

  Contributors: Xiao-Wen Chang, Jing Zhu, Xiangyu Ren, Zhilong Chen

  The routines use the algorithms proposed in the following publications:

  [1] X.-W. Chang and X. Yang. An efficient tree search decoder with column reordering for underdetermined MIMO systems, Proceedings of IEEE GLOBECOM 2007, pp. 4375 - 4379.

  [2] S. Breen and X.-W. Chang. Column Reordering for Box-constrained Integer Least Squares Problems, Proceedings of IEEE GLOBECOM 2011, 6 pages.

  [3] J. Zhu. Numerical methods for underdetermined box-constrained integer least squares problems, M.Sc. Thesis, School of Computer Science, McGill University, 2016.

• ADMM based tree search method - this may be much faster the first method especially when the constraint box is large.
  • ubils_admm.zip (includes three files, sub-functions are in MEX form)

  Contributors: Xiao-Wen Chang, Tianchi Ma, Xiangyu Ren, Zhilong Chen

  The routines use the algorithms proposed in the following publications:

  [1] X.-W. Chang and X. Yang. An efficient tree search decoder with column reordering for underdetermined MIMO systems, Proceedings of IEEE GLOBECOM 2007, pp. 4375 - 4379.

  [2] S. Breen and X.-W. Chang. Column Reordering for Box-constrained Integer Least Squares Problems, Proceedings of IEEE GLOBECOM 2011, 6 pages.

  [3] T. Ma. An ADMM Method for Underdetermined Box-constrained Integer Least Squares Problems, M.Sc. Thesis, School of Computer Science, McGill University, May 2021.