Clutters III

A long time ago I started a series of posts abut clutters. The most recent post followed the textbook by Gérards Cornuéjols in defining several important classes, and introduced a Venn diagram, showing the relationships between them.

ClutterVenn

In this post we will spend a little more time discussing this diagram.

We let $H=(S,\mathcal{A})$ be a clutter. This means that $S$ is a finite set, and the members of $\mathcal{A}$ are subsets of $S$, none of which is properly contained in another. We let $M$ stand for the incidence matrix of $H$. This means that the columns of $M$ are labelled by the elements of $S$, and the rows are labelled by members of $\mathcal{A}$, where an entry of $M$ is one if and only if the corresponding element of $S$ is contained in the corresponding member of $\mathcal{A}$. Any entry of $M$ that is not one is zero. Let $w$ be a vector in $\mathbb{R}^{S}$ with non-negative values. We have two fundamental linear programs:

(1) Find $x\in \mathbb{R}^{S}$ that minimises $w^{T}x$ subject to the constraints $x\geq \mathbf{0}$ and $Mx\geq \mathbf{1}$.

The vectors $\mathbf{0}$ and $\mathbf{1}$ have all entries equal to zero and one, respectively. When we write that real vectors $a$ and $b$ with the same number of entries satisfy $a\geq b$, we mean that each entry of $a$ is at least equal to the corresponding entry in $b$.

(2) Find $y\in\mathbb{R}^{\mathcal{A}}$ that maximises $y^{T}\mathbf{1}$ subject to the constraints $y\geq \mathbf{0}$ and $y^{T}M\leq w$.

Lemma 1. Any clutter with the Max Flow Min Cut property also has the packing property.

Proof. Let $H$ be a clutter with the Max Flow Min Cut property. This means that for any choice of vector $w$ with non-negative integer entries, the programs (1) and (2) both have optimal solutions with integer values.

We will show that $H$ has the packing property. According to the definition in the literature, this means that for any choice of vector $w$ with entries equal to $0$, $1$, or $+\infty$, there are optimal solutions to (1) and (2) with integer entries. I think there is a problem with this definition. Assume that $r$ is a row of $M$, and every member of the support of $r$ receives a weight of $+\infty$ in the vector $w$. Then (2) cannot have an optimal solution. If $y$ is a purported optimal solution, then we can improve it by adding $1$ to the entry of $y$ that corresponds to row $r$. We are instructed that if entry $i$ in $w$ is $+\infty$, then this means when $x$ is a solution to (1), then entry $i$ of $x$ must be $0$. Again, we have a problem, for if $r$ is a row of $M$, and the entire support of $r$ is weighted $+\infty$, then (1) has no solution: if $x$ were a solution, then it would be zero in every entry in the support of $r$, meaning that $Mx$ has a zero entry.

The literature is unanimous in saying that $H$ has the packing property if (1) and (2) both have integral optimal solutions for any choice of vector $w$ with entries $0$, $1$, and $+\infty$. As far as I can see, this means that any clutter with $\mathcal{A}$ non-empty does not have the packing property: simple declare $w$ to be the vector with all entries equal to $+\infty$. Then neither (1) nor (2) has an optimal solution at all. I think the way to recover the definition is to say that whenever $w$ with entries $0$, $1$, or $+\infty$ is chosen in such a way that (1) and (2) have solutions, they both have optimal solutions that are integral. This is the definition that I will use here.

After this detour, we return to our task, and assume that $H$ has the Max Flow Min Cut property. Assume that $w$ is a vector with entries equal to $0$, $1$, or $+\infty$, and that (1) and (2) both have solutions. This means that any row in $M$ has a member of its support which is not weighted $+\infty$ by $w$. We obtain the vector $u$ by replacing each $+\infty$ entry in $w$ with an integer that is greater than $|S|$. Now because $H$ has the Max Flow Min Cut property, it follows that there are optimal integral solutions, $x$ and $y$, to (1) and (2) (relative to the vector $u$). We will show that $x$ and $y$ are also optimal solutions to (1) and (2) relative to the vector $w$.

We partition $S$ into $S_{0}$, $S_{1}$, and $S_{+\infty}$ according to whether an element of $S$ receives a weight of $0$, $1$, or $+\infty$ in $w$. We have assumed that no member of $\mathcal{A}$ is contained in $S_{+\infty}$. We note that if $z\in \mathbb{Z}^{S}$ is a vector which is equal to zero for each element of $S_{+\infty}$, and one everywhere else, then $z$ is a solution to (1), by this assumption. Moreover, $w^{T}z=u^{T}z\leq |S|$. Now it follows that $x$ must be zero in every entry in $S_{+\infty}$, for otherwise $u^{T}x>|S|$, and therefore $x$ is not an optimal solution to (1) relative to $u$. Since $x$ is integral and optimal, it follows that we can assume every entry is either one or zero. If $x$ is not an optimal solution to (1) relative to $w$, then we let $z$ be an optimal solution with $w^{T}z < w^{T}x$. But by convention, $z$ must be zero in every entry of $S_{+\infty}$. Therefore $u^{T}z=w^{T}z < w^{T}x=u^{T}z$, and we have a contradiction to the optimality of $x$. Thus $x$ is an optimal solution to (1) relative to the $\{0,1,+\infty\}$-vector $w$.

Now for problem (2). Since $y$ is integral and non-negative, and $y^{T}M\leq w$, where every member of $\mathcal{A}$ contains an element of $S_{0}$ or $S_{1}$, it follows that each entry of $y$ must be either one or zero. Let $z$ be any solution of (2) relative to $w$. Exactly the same argument shows that each entry of $z$ is between zero and one. Therefore $z^{T}\mathbf{1}\leq y^{T}\mathbf{1}$ so $y$ is an optimal solution to (2).

We have shown that relative to the vector $w$, both (1) and (2) have optimal solutions that are integral. Hence $H$ has the packing property. $\square$

Lemma 2. A clutter with the packing property packs.

Proof. This one is easy. In order to prove that $H$ packs, we merely need to show that (1) and (2) have optimal integral solutions when $w$ is the vector with all entries equal to one. But this follows immediately from our revised definition of clutters with the packing property. $\square$

The final containment we should show is that clutters with the packing property are ideal. Idealness means that (1) has an optimal integral solution for all vectors $w\in \mathbb{R}^{S}$. This proof is difficult, so I will leave it for a future post. Usually we prove it by using a theorem due to Lehman [Leh].

Theorem (Lehman). The clutter $H$ is ideal if and only if (1) has an optimal integral solution for all choices of vector $w\in\{0,1,+\infty\}^{S}$.

Question. Is there a short proof that clutters with the packing property are ideal? One that does not rely on Lehman’s (quite difficult) theorem?

We will conclude with some examples showing that various containments are proper.

Let $C_{3}^{2}$ and $C_{3}^{2+}$ be the clutters with incidence matrices
\[
\begin{bmatrix}
1&1&0\\
0&1&1\\
1&0&1
\end{bmatrix}
\quad\text{and}\quad
\begin{bmatrix}
1&1&0&1\\
0&1&1&1\\
1&0&1&1
\end{bmatrix}.
\]
Let $Q_{6}$ and $Q_{6}^{+}$ be the clutters with incidence matrices
\[
\begin{bmatrix}
1&1&0&1&0&0\\
1&0&1&0&1&0\\
0&1&1&0&0&1\\
0&0&0&1&1&1
\end{bmatrix}
\quad\text{and}\quad
\begin{bmatrix}
1&1&0&1&0&0&1\\
1&0&1&0&1&0&1\\
0&1&1&0&0&1&1\\
0&0&0&1&1&1&1
\end{bmatrix}
\]

Exercise. Check that:

  1. $C_{3}^{2}$ is not ideal and does not pack,
  2. $C_{3}^{2+}$ packs, but is not ideal,
  3. $Q_{6}$ is ideal, but does not pack,
  4. $Q_{6}^{+}$ is ideal and packs, but does not have the packing property.

This leaves one cell in the Venn diagram without a clutter: the clutters with the packing property that do not have the Max Flow Min Cut property. In fact, Conforti and Cornuéjols [CC] have speculated that no such clutter exists.

Conjecture (Conforti and Cornuéjols). A clutter has the packing property if and only if it has the Max Flow Min Cut property.

[CC] M. Conforti and G. Cornuéjols, Clutters that Pack and the Max Flow Min Cut Property: A Conjecture, The Fourth Bellairs Workshop on Combinatorial Optimization, W.R. Pulleyblank and F.B. Shepherd eds. (1993).

[Leh] A. Lehman, On the width-length inequality. Mathematical Programming December 1979, Volume 16, Issue 1, pp 245–259.

Leave a Reply

Your email address will not be published. Required fields are marked *