Minimum maximal solutions of LPs

Question

Linear programming is, of course, nowadays very well understood. We have a lot of work that characterises the structure of feasible solutions, and the structure of optimal solutions. We have the strong duality, poly-time algorithms, etc.

But what is known about minimum maximal solutions of LPs? Or, equivalently, maximum minimal solutions?

(This is not really a research question, but maybe we can have something less technical for the holidays. I'm just being curious, and after some googling I got the feeling that I must be missing the right keywords. It feels like an obvious problem to study, but I only found some sporadic papers that mention the problem.)

---

To keep things simple, let's focus on packing and covering LPs. In a packing LP we are given a non-negative matrix $A$. A vector $x$ is feasible if $x \ge 0$ and $Ax \le 1$. We say that $x$ is maximal if it is feasible and we can't greedily increase any component. That is, if $y \ge 0$ and $y \ne 0$, then $x + y$ is not feasible. And finally, $x$ is a minimum maximal solution, if it minimises the objective function $\sum_i x_i$ among all maximal solutions.

(You can define a maximum minimal solution of a covering LP in an analogous manner.)

What does the space of minimum maximal solutions look like? How can we find such solutions? How difficult it is to find such solutions? How can we approximate such solutions? Who studies such things, and what is the right term for it?

---

These questions were originally motivated by edge dominating sets and minimum maximal matchings. It is well known (and fairly easy to see) that a minimum maximal matching is a minimum edge dominating set; conversely, given a minimum edge dominating set, it is easy to construct a minimum maximal matching.

So they are, in essence, the same problem. Both problems are NP-hard and APX-hard. There is a trivial 2-approximation algorithm: any maximal matching.

However, their "natural" LP relaxations look very different. If you take the edge dominating set problem and form a natural LP relaxation, you get a covering LP. However, if you take the problem of finding a minimum maximal matching and try to come up with an LP relaxation, then what do you get? Well, of course fractional matchings are feasible solutions of a packing LP; then maximal fractional matchings are maximal solutions of such LPs, and minimum maximal fractional matchings are therefore minimum maximal solutions of such LPs. :)

Answer 1

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 <= 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.

Answer 2

You may find it useful to look into blocking and anti-blocking pairs of polyhedra. Say you have a packing problem. Then your feasible region $P$ is a corner polyhedron in the nonnegative orthant, and its anti-blocker $A(P)$ (also a corner polyhedron) is basically the set of inequalities defining $P$.

For example, if you take the stable set polytope $STAB(G)$ for some graph $G$ (i.e. the convex hull of incidence vectors of stable sets), its anti-blocker is the fractional clique polytope of $G$, i.e. $QSTAB(\bar G)$ (i.e. the set of nonnegative weightings such that no stable set has total weight $> 1$).

If you look at "The ellipsoid method and its consequences in combinatorial optimization" by Grötschel, Lovász, and Schrijver, you'll find that optimization over $P$ is in a sense computationally equivalent to optimization over $A(P)$. This is one way to prove that computing the fractional chromatic number is NP-hard, since the dual region to the LP is the anti-blocker of the stable set polytope!

Sadly I have had a hard time finding a transparent explanation of this stuff, but I'm by no means an expert on polyhedra. Hopefully you'll find it relevant to the problem at hand.