{"id":2256,"date":"2017-08-22T19:48:57","date_gmt":"2017-08-22T23:48:57","guid":{"rendered":"http:\/\/matroidunion.org\/?p=2256"},"modified":"2017-08-22T19:48:57","modified_gmt":"2017-08-22T23:48:57","slug":"clutters-iii","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=2256","title":{"rendered":"Clutters III"},"content":{"rendered":"

A long time ago I started a series of posts abut clutters. The most recent post<\/a> followed the textbook by G\u00e9rards Cornu\u00e9jols<\/a> in defining several important classes, and introduced a Venn diagram, showing the relationships between them.<\/p>\n

\"ClutterVenn\"<\/a><\/p>\n

In this post we will spend a little more time discussing this diagram.<\/p>\n

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:<\/p>\n

(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}$.<\/p>\n

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$.<\/p>\n

(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$.<\/p>\n

Lemma 1.<\/strong> Any clutter with the Max Flow Min Cut property also has the packing property.<\/em><\/p>\n

Proof.<\/em> 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.<\/p>\n

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.<\/p>\n

The literature is unanimous in saying that $H$ has the packing property if (1) and (2) both have integral optimal solutions for any<\/strong> 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.<\/p>\n

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$.<\/p>\n

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$.<\/p>\n

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).<\/p>\n

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$<\/p>\n

Lemma 2.<\/strong> A clutter with the packing property packs.<\/em><\/p>\n

Proof.<\/em> 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$<\/p>\n

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].<\/p>\n

Theorem<\/strong> (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}$.<\/p>\n

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

We will conclude with some examples showing that various containments are proper.<\/p>\n

Let $C_{3}^{2}$ and $C_{3}^{2+}$ be the clutters with incidence matrices
\n\\[
\n\\begin{bmatrix}
\n1&1&0\\\\
\n0&1&1\\\\
\n1&0&1
\n\\end{bmatrix}
\n\\quad\\text{and}\\quad
\n\\begin{bmatrix}
\n1&1&0&1\\\\
\n0&1&1&1\\\\
\n1&0&1&1
\n\\end{bmatrix}.
\n\\]
\nLet $Q_{6}$ and $Q_{6}^{+}$ be the clutters with incidence matrices
\n\\[
\n\\begin{bmatrix}
\n1&1&0&1&0&0\\\\
\n1&0&1&0&1&0\\\\
\n0&1&1&0&0&1\\\\
\n0&0&0&1&1&1
\n\\end{bmatrix}
\n\\quad\\text{and}\\quad
\n\\begin{bmatrix}
\n1&1&0&1&0&0&1\\\\
\n1&0&1&0&1&0&1\\\\
\n0&1&1&0&0&1&1\\\\
\n0&0&0&1&1&1&1
\n\\end{bmatrix}
\n\\]<\/p>\n

Exercise.<\/strong> Check that:<\/p>\n

    \n
  1. $C_{3}^{2}$ is not ideal and does not pack,<\/li>\n
  2. $C_{3}^{2+}$ packs, but is not ideal,<\/li>\n
  3. $Q_{6}$ is ideal, but does not pack,<\/li>\n
  4. $Q_{6}^{+}$ is ideal and packs, but does not have the packing property.\n<\/ol>\n

    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\u00e9jols [CC] have speculated that no such clutter exists.<\/p>\n

    Conjecture<\/strong> (Conforti and Cornu\u00e9jols). A clutter has the packing property if and only if it has the Max Flow Min Cut property.<\/p>\n

    [CC] M. Conforti and G. Cornu\u00e9jols, Clutters that Pack and the Max Flow Min Cut Property: A Conjecture<\/em>, The Fourth Bellairs Workshop on Combinatorial Optimization, W.R. Pulleyblank and F.B. Shepherd eds. (1993).<\/p>\n

    [Leh] A. Lehman, On the width-length inequality.<\/em> Mathematical Programming<\/em> December 1979, Volume 16, Issue 1, pp 245\u2013259.<\/p>\n","protected":false},"excerpt":{"rendered":"

    A long time ago I started a series of posts abut clutters. The most recent post followed the textbook by G\u00e9rards Cornu\u00e9jols in defining several important classes, and introduced a Venn diagram, showing the relationships between them. In this post … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-2256","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2256","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2256"}],"version-history":[{"count":26,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2256\/revisions"}],"predecessor-version":[{"id":2283,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/2256\/revisions\/2283"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2256"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2256"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2256"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}