I am working with an integer linear optimization problem which, abstractly, is:
Find $\vec{x}$ such that $\mathbf{A}\cdot \vec{x} \leq -1$, and such that the sum of the entries of $\vec{x}$ is as small as possible. The entries of $\vec{x}$ must be nonnegative integers. (Note that $\mathbf{A}$ is a given integer-valued matrix.)
I have found that this problem has a unique minimum solution $x^*$. Now, because of the inequality constraint, I know that positive multiples of $x^*$ are also a solution. I can even, for any $y$, find sufficiently large $\alpha$ so that $y+\alpha x$ is also a solution. But these solutions are in general boringly dependent on $x^*$— I am interested in finding further solutions that are "independent" of $x^*$, which I have formalized as "any solution $y$ which does not contain $x^*$—which is not weakly greater than $x^*$ in each dimension."
The "independence" condition is a kind of partial order on the space $\mathbb{Z}_+^{n}$ of solutions: $x \preceq y$ iff $x$ is elementwise less than or equal to $y$ in each component. And in the language of partial orders, I'm looking for maximal independent sets of solutions— maximal antichains in the solution space ordered by $\preceq$.
This intersection of linear optimization and order theory is a bit out of my depth. I'm wondering:
Is there a unique maximal antichain?
Is it possible/likely that the maximum antichain is finite? How could I tell?
(i.e. is there intuition for knowing whether the antichain is finite without knowing the specific value of $\mathbf{A}$? Or what properties of $\mathbf{A}$ would let you know?)
What I have tried so far is considering specific simpler examples.
Power sets seem to have maximal antichains consisting of $n/2$ element subsets, and these antichains do not seem to be unique.
I have used computational methods to form a sort of "sieve" method: I solve the original optimization problem, then add the constraint that future solutions must not contain ($\preceq$) any solution so far found; then I iterate. This process becomes slow, due to the increasing complexity of the constraints, but has not terminated. My initial concern was sparked by curiosity about whether I could know that this process will always yield new solutions, and whether the antichain I was constructing depended on idiosyncracies of the program or was genuinely unique.
My intuition for this problem is that there are arbitrarily large antichains. But I have competing intuitions about this --- on one hand, the matrix $\mathbf{A}$ is finite-dimensional (18x18). On the other, the values in $\mathbb{Z}_+^n$ are unbounded. On the third, the antichain constraint carves out large infinite sections of the space, but on the fourth, these probably do not ever end up partitioning the entire solution space, which suggests that there are infinitely many independent minimal solutions.
Edit: When I've experimented on small matrices, e.g. 2x2 or 3x3 matrices with entries in {-1, 0, +1} (like $\mathbf{A}$ itself, actually), I find there are finitely many antichains in all the cases I've considered so far.
Take the problem: $$\left\{\begin{align}x_1+x_2&\geq 3\\ x_1&\geq 1 \\ x_2&\geq 1\end{align}\right.$$ It has two optimal solutions $(2, 1)$ and $(1, 2)$
As you noticed, it is easy to find examples for which there are multiple maximum antichains. There is always an infinite number of maximal antichains. Take an arbitrary solution, and for any positive multiples, construct a maximal antichain from it.
If you require $x^*$ to be part of the antichain, then you may have as antichain only the one composed of $x^*$, but as long as you can find another solution $y$ not comparable to $x^*$, you can construct arbitrary chains by taking $x^*$ and $y+\alpha$, where $\alpha$ makes $y$ grow in a direction that keeps it not comparable to $x$.
If you require your vectors in the antichain to be minimal towards every other solution, then the maximal antichain is unique and is called the Pareto front.
This is impossible to find an infinite antichain, this is a direct consequence of Dickson's lemma, but you can fin arbitrary big antichains.