  The exact nonnegative matrix factorization (exact NMF) problem is the
following: given an $m$-by-$n$ nonnegative matrix $X$ and a factorization rank
$r$, find, if possible, an $m$-by-$r$ nonnegative matrix $W$ and an $r$-by-$n$
nonnegative matrix $H$ such that $X = WH$. In this paper, we propose two
heuristics for exact NMF, one inspired from simulated annealing and the other
from the greedy randomized adaptive search procedure. We show that these two
heuristics are able to compute exact nonnegative factorizations for several
classes of nonnegative matrices (namely, linear Euclidean distance matrices,
slack matrices, unique-disjointness matrices, and randomly generated matrices)
and as such demonstrate their superiority over standard multi-start strategies.
We also consider a hybridization between these two heuristics that allows us to
combine the advantages of both methods. Finally, we discuss the use of these
heuristics to gain insight on the behavior of the nonnegative rank, i.e., the
minimum factorization rank such that an exact NMF exists. In particular, we
disprove a conjecture on the nonnegative rank of a Kronecker product, propose a
new upper bound on the extension complexity of generic $n$-gons and conjecture
the exact value of (i) the extension complexity of regular $n$-gons and (ii)
the nonnegative rank of a submatrix of the slack matrix of the correlation
polytope.
