Exact inverse-M interval solution hulls by 2n linear programs

For a rational interval matrix every member of which is an inverse M-matrix,
and an arbitrary rational interval right-hand side, the paper computes the
exact interval hull of the solution set using $2n$ linear programs, each with
$n$ variables and $2n$ inequalities. Writing the interval matrix by its
midpoint $C$ and radius $R$, it shows that for each sign vector $\sigma$, with
$D_\sigma$ its diagonal matrix, the absolute value equation
$Cx - D_\sigma R|x| = b$ has a unique solution,
because every member of the interval matrix is nonsingular, and that a linear
program in complementary parts computes it. A sign argument using the inverse
M-matrix property shows that, for suitable sign vectors and right-hand-side
vertices, these solutions attain the coordinatewise hull endpoints. With
polynomial-time rational linear programming, the exact hull is computed in
time polynomial in the binary input length.