  For some weighted $NP$-complete problems, checking whether a proposed
solution is optimal is a non-trivial task. Such is the case for the celebrated
traveling salesman problem, or the spin-glass problem in 3 dimensions. In this
letter, we consider the weighted tripartite matching problem, a well known
$NP$-complete problem. We write mean-field finite temperature equations for
this model, and show that they become exact at zero temperature. As a
consequence, given a possible solution, we propose an algorithm which allows to
check in a polynomial time if the solution is indeed optimal. This algorithm is
generalized to a class of variants of the multiple traveling salesmen problem.
