The MVE estimator is an important tool in robust regression and outlier detection in statistics. Given a set of points, MVE estimator is based on an ellipsoid which encloses a fixed number of points (usually at least half of them) and has the smallest possible volume. Finding such an ellipsoid is computationally very challenging especially for large data sets. This paper develops a 2-exchange heuristic and a branch-and-bound algorithm for computing the MVE estimator. Comparative computational results are provided which demonstrate the strength of the algorithm.