Minimum maximal solutions of LPs
Maximality and minimality: They are kinds of Pareto optimality.
Complexity: I think finding a minimum maximal solution is NP-hard.  I would reduce the independence domination problem (aka the minimum maximal independent set problem) in bipartite graphs.  This problem (more precisely its decision version) is known to be NP-complete (D. G. Corneil and Y. Perl, Clustering and domination in perfect graphs.  Discrete Applied Mathematics 9 (1984) 27-39).  Since a bipartite graph is perfect, its independent set polytope is determined by the clique inequalities, and the number of cliques in a bipartite graph is polynomial.  Therefore, we can explicitly write down a system of linear inequalities Ax &lt;= 1, x >= 0 for the independent set polytope.  The extreme solutions correspond to the independent sets, and the extreme maximal solutions correspond to the maximal independent sets.