{"id":815,"date":"2010-03-03T04:43:32","date_gmt":"2010-03-03T12:43:32","guid":{"rendered":"http:\/\/obliviousrounding.com\/blog\/?p=815"},"modified":"2026-09-30T09:14:46","modified_gmt":"2026-09-30T17:14:46","slug":"modeling","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/linear-programming\/modeling\/","title":{"rendered":"modeling Set Cover and Multicommodity Flow"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<blockquote class=\"quote\"><p><center><em>Set Cover and Multicommodity flow as (integer) linear programs.<\/em><\/center><\/p><\/blockquote>\n<p>  Modeling a problem as a linear program or integer linear program is a basic skill. Here are two examples.<!--more--><\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<hr \/>\n<div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for background material\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for background material\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/linear-programming\">Linear programming<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<\/div>\n<hr \/>\n<\/p>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000003\">Set Cover<\/h1>\n<p> <a href=\"http:\/\/algnotes.info\/on\/greedy-example\">Recall<\/a> the definition of Set Cover: Given a collection <script type=\"math\/tex;\">{\\cal S}<\/script> of finite sets from a universe <script type=\"math\/tex;\">U<\/script> and a cost <script type=\"math\/tex;\">c_s<\/script> for each set <script type=\"math\/tex;\">s\\in {\\cal S}<\/script>, the problem is to choose a minimum-cost <em>set cover<\/em> \u2014 a collection <script type=\"math\/tex;\">{\\cal C}<\/script> of sets in <script type=\"math\/tex;\">{\\cal S}<\/script> such that each element <script type=\"math\/tex;\">e\\in U<\/script> is contained in at least one set in <script type=\"math\/tex;\">{\\cal C}<\/script>. The cost of <script type=\"math\/tex;\">{\\cal C}<\/script> is <script type=\"math\/tex;\">\\sum _{s\\in {\\cal C}} c_s<\/script>. <\/p>\n<p>The standard <a href=\"http:\/\/algnotes.info\/on\/modeling\">integer linear program<\/a> for the problem is <\/p>\n<div id=\"a0000000004\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\min \\Big\\{  c\\cdot x ~ |~  x\\in {\\mathbb Z}_+^{|{\\cal S}|};\\,  (\\forall e\\in U)\\, \\sum _{s\\ni e} x_s \\ge 1\\Big\\} .  <\/script><\/div>\n<p> In the linear-program relaxation of the problem, the variables can take non-integer values: <\/p>\n<div id=\"a0000000005\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\min \\Big\\{  c\\cdot x ~ |~  x\\in {\\mathbb R}_+^{|{\\cal S}|};\\,  (\\forall e\\in U)\\, \\sum _{s\\ni e} x_s \\ge 1\\Big\\} .  <\/script><\/div>\n<p> If a (possibly fractional) <script type=\"math\/tex;\">x<\/script> meets the constraint <script type=\"math\/tex;\">\\sum _{s\\ni e} x_s \\ge 1<\/script> for an element <script type=\"math\/tex;\">e<\/script>, we say that <script type=\"math\/tex;\">x<\/script> <em>covers<\/em> <script type=\"math\/tex;\">e<\/script>, and, if <script type=\"math\/tex;\">x<\/script> covers all elements, it is a <em>fractional set cover<\/em> \u2014 a feasible solution to the linear program. If <script type=\"math\/tex;\">x<\/script> is an integer solution, we identify it with the collection of sets <script type=\"math\/tex;\">\\{ s\\in {\\cal S}: x_s \\gt 0\\} <\/script>. <\/p>\n<p><span style=\"float:right;margin:0.8em;margin-right:-0.5in;\"> <img decoding=\"async\" src=\"http:\/\/algnotes.info\/b\/wp-content\/uploads\/2011\/11\/img-0001.png\" alt=\"\\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=3.75in]{shared\/graphics\/set_cover_graph}\" style=\"width:3.75in\" class=\"zoooom\" \/> <\/span> <em>The figure shows a fractional set cover of size 2 (that is, <script type=\"math\/tex;\">\\sum _s x_s = 2<\/script>). The value assigned to each variable <script type=\"math\/tex;\">x_s<\/script> is written above its set <script type=\"math\/tex;\">s<\/script>. For each element <script type=\"math\/tex;\">e<\/script>, the total coverage <script type=\"math\/tex;\">\\sum _{s\\ni e} x_s<\/script> of <script type=\"math\/tex;\">e<\/script> is shown below <script type=\"math\/tex;\">e<\/script>. The total coverage of each element is at least 1, so <script type=\"math\/tex;\">x<\/script> is a fractional set cover.<\/em> <\/p>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000006\">Multicommodity Flow<\/h1>\n<p> Maximum multicommodity flow (defined in <a href=\"http:\/\/algnotes.info\/on\/lagrangian-relaxation-example\">this note<\/a>) is exactly modeled by the following linear program: <\/p>\n<div id=\"a0000000007\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\max \\Big\\{  |f| : f\\in {\\mathbb R}_+^{|P|}, (\\forall e\\in E)\\, \\sum _{p\\ni e} f_p \\le c_e\\Big\\} .  <\/script><\/div>\n<p> For each path <script type=\"math\/tex;\">p\\in P<\/script>, there is a variable <script type=\"math\/tex;\">f_p<\/script> representing the flow on path <script type=\"math\/tex;\">p<\/script>. For each edge <script type=\"math\/tex;\">e<\/script>, there is a constraint that the total flow on paths through the edge is at most the edge capacity <script type=\"math\/tex;\">c_e<\/script>. Subject to these constraints, the objective is to maximize the total flow <script type=\"math\/tex;\">|f|<\/script> (i.e., <script type=\"math\/tex;\">\\sum _p f_p<\/script>) on all paths. <\/p>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Remark.<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The number of variables in this formulation can be exponential in the size of the graph.<a href=\"#a0000000008\" class=\"footnote\"><sup class=\"footnotemark\">1<\/sup><\/a> Greedy and Lagrangian-relaxation algorithms can deal with this, as long as they have an appropriate oracle (optimization subroutine). <\/p>\n<div id=\"a0000000009\" class=\"my-theorem latex-paragraph latex-exercise\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Exercise.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>Describe how, given a graph <script type=\"math\/tex;\">G<\/script>, to model the problem of finding a maximum-size independent set in <script type=\"math\/tex;\">G<\/script> as an integer linear programming problem. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000010\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for answer \u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for answer \u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<div id=\"a0000000011\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\max \\sum _{v\\in V} x_v \\mbox{ such that } x\\in {\\mathbb N}^V, \\forall v\\in V.~  0 \\le x_v \\le 1  <\/script><\/div>\n<\/p><\/div>\n<\/details>\n<\/div>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000012\">Wikipedia<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Set_cover_problem\">Set cover<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Multi-commodity_flow_problem\">Multi-commodity flow<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Linear_programming#Covering-packing_dualities\">covering and packing<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Linear_programming\">linear programming<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n<div id=\"footnotes\">\n<div>\n<h2>Footnotes<\/h2>\n<ol>\n<li id=\"a0000000008\">You may be familiar with an alternate formulation of network flow using flow variables for the edges. That formulation can be smaller, but has both negative and positive coefficients \u2014 it is not a packing or covering linear program.<\/li>\n<\/ol><\/div>\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Set Cover and Multicommodity flow as (integer) linear programs. Modeling a problem as a linear program or integer linear program is a basic skill. Here are two examples.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1468,"menu_order":10,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-815","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/815","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/comments?post=815"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/815\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1468"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=815"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}