Finding the Pareto frontier when the optimization problem is simple?

Question

I am working on the following problem:

Find integer $\vec{x}\geq 0$ within the solution space $\mathbf{A}\cdot \vec{x} \leq -1$ such that none of $(x_1, \ldots, x_n)$ can be made any smaller.

1. In other words, I am interested in computing the exact Pareto frontier of the solution space; that is to say, the set of all minimal solutions $\vec{x}$. A solution $\vec{x}$ is minimal if there is no other more efficient solution $\vec{y}$ where $x_i \geq y_i$ in every component.

2. The set of minimal solutions exists and is finite, by Dickson's lemma.

3. Computing the Pareto frontier is usually computationally hard and approached through approximation. I am trying to design a clever search algorithm to find all of the minimal solutions exactly and terminate, by taking advantage of the especially simplifying features of this problem:

   • The domain is defined by a linear system of inequalities.
   • The system uses only the coefficients {-1, 0, 1}, which I have proven means, for example, that the $L_1$ distance between any point $\vec{x}$ and the nearest solution is at least "1 + the maximum of the positive components of $\mathbf{A}\cdot \vec{x}$". This is an admissible and consistent search heuristic.
   • While this is a "multi-objective optimization" problem, it's a particularly decoupled one because the different objectives are completely independent --- decreasing one never increases another. All the complexity comes from the domain restriction $\mathbf{A}\cdot \vec{x} \leq -1$.

My default plan is to use a branch-and-bound style search algorithm to find all minimal solutions. This is guaranteed to be complete, but unfortunately does not have a way of knowing when all solutions have been found so that searching can terminate. In particular, one specific problem is determining that the algorithm should stop exploring a candidate node $\vec{x}$, because all solutions that $\vec{x}$ dominates are also dominated by one of the minimal solutions already found.

My questions are:

1. Is search an appropriate paradigm for finding the exact solutions?
2. Are there other exact solution procedures I should consider?
3. Have I taken full advantage of the simplifying structure of the problem?
4. Is there a way to confirm that all minimal solutions are found and/or to eventually eliminate all paths that are guaranteed not to lead to a minimal solution?