The authors consider the interval linear matrix equation \({\mathbf A}X={\mathbf B}\), where \({\mathbf A}\) and \({\mathbf B}\) are given interval matrices of dimension \(m\times m\) and \(m\times n\), respectively. The solution of this equation is defined as a particular subset of the so-called united solution set \[ \Xi_{\exists\exists}'({\mathbf A},{\mathbf B})= \{X\in \mathbb{R}^{m\times n}\mid (\exists A\in{\mathbf A})(\exists B\in{\mathbf B});\;AX= B\} \] according to additional restrictions expressed by some mixture of all and existence qualifiers. The authors give some characterizations of these AE-solution sets and use a linear programming method in order to find the interval hull of \(\Xi_{\exists\exists}'({\mathbf A},{\mathbf B})\), i.e., the smallest enclosure of this solution set by an \(m\times n\) interval matrix. A coarser enclosure is computed by means of the interval Gaussian algorithm.