The Markowitz tolerance balances sparsity (for performance) and numerical stability when constructing the LU factorization of the basis matrix in the simplex algorithm. You can change this value via the MarkowitzTol parameter.

During the LU factorization (Gaussian elimination), a new pivot element has to be determined from the current submatrix. Elements with sparse rows and columns are preferred to avoid fill-in (additional non-zero elements in the resulting factorization). The **Markowitz count** refers to the number \(m_{ij}=(r_i-1)\cdot (c_j-1)\) where \(r_i\) represents the number of non-zero elements in the \(i\)th row of the reduced submatrix and \(c_j\) represents this count regarding the \(j\)th column. Pivot candidates are sorted in increasing order of their Markowitz counts (with 0 referring to singleton rows or columns that avoid fill-in as much as possible). A candidate with a minimum Markowitz count would be unacceptable if it is very small compared to other entries. To ensure the numerical stability of the selected pivot, it must satisfy \(|a_{ij}| \geq \mu \max_k |a_{kj}|\) with \(\mu\) being the Markowitz tolerance. Pivot elements with a large absolute value contribute to more stability in the resulting LU factorization.

The Markowitz tolerance in Gurobi is a number between \(10^{-4}\) and \(0.999\). A smaller number favors sparsity at the cost of numerical stability. At the same time, a value closer to one emphasizes selecting a stable pivot element rather than avoiding fill-in.

## Comments

0 comments

Please sign in to leave a comment.