The conventional statement of linear programming duality is completely inscrutable.<\/p>\n

\n
• Prime: maximise subject to and .<\/li>\n
• Dual: minimise subject to and .<\/li>\n<\/ul>\n

  If either problem has a finite optimum then so does the other, and the optima agree.<\/p>\n

  I\u00a0do<\/em> understand concrete examples. \u00a0Suppose we want to pack the maximum number vertex-disjoint copies of a graph into a graph . \u00a0In the fractional relaxation, we want to assign each copy of a weight such that the weight of all the copies of at each vertex is at most , and the total weight is as large as possible. \u00a0Formally, we want to<\/p>\n

  maximise subject to and ,<\/p>\n

  which dualises to<\/p>\n

  minimise subject to and .<\/p>\n

  That is, we want to weight vertices as cheaply as possible so that every copy of contains (fractional) vertex.<\/p>\n

  To get from the prime to the dual, all we had to was change a max to a min, swap the variables indexed by for variables indexed by and flip one inequality. \u00a0This is so easy that I never get it wrong when I’m writing on paper or a board! \u00a0But I thought for years that I didn’t understand linear programming duality.<\/p>\n

  (There are some features of this problem that make things particularly easy: the vectors and in the conventional statement both have all their entries equal to , and the matrix is -valued. \u00a0This is very often the case for problems coming from combinatorics. \u00a0It also matters that I chose not to make explicit that the inequalities should hold for every (or , as appropriate).)<\/p>\n

  Returning to the general statement, I think I’d be happier with<\/p>\n

  \n
  • Prime: maximise subject to and .<\/li>\n
  • Dual: minimise subject to and .<\/li>\n<\/ul>\n

    My real objection might be to matrix transposes and a tendency to use notation for matrix multiplication just because it’s there. \u00a0In this setting a matrix is just a function that takes arguments of two different types ( and or, if you must, and ), and I’d rather label the types explicitly than rely on an arbitrary convention.<\/p>\n","protected":false},"excerpt":{"rendered":"

    The conventional statement of linear programming duality is completely inscrutable. Prime: maximise subject to and . Dual: minimise subject to and . If either problem has a finite optimum then so does the other, and the optima agree. I\u00a0do understand concrete examples. \u00a0Suppose we want to pack the maximum number vertex-disjoint copies of a graph … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[26],"_links":{"self":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/342"}],"collection":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/comments?post=342"}],"version-history":[{"count":0,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/posts\/342\/revisions"}],"wp:attachment":[{"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/media?parent=342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/categories?post=342"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/babarber.uk\/wp-json\/wp\/v2\/tags?post=342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}