{"id":1468,"date":"2010-03-01T00:44:34","date_gmt":"2010-03-01T08:44:34","guid":{"rendered":"http:\/\/greedyalgs.com\/blog\/?p=1468"},"modified":"2026-09-30T09:14:39","modified_gmt":"2026-09-30T17:14:39","slug":"linear-programming","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/background\/linear-programming\/","title":{"rendered":"Linear programming"},"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>Notes on Linear Programming and Integer Linear Programming.<\/em><\/center><\/p><\/blockquote>\n<p><!--more--><\/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=\"a0000000002\">Linear programming and integer linear programming<\/h1>\n<p> An instance of Linear Programming requires finding a vector <script type=\"math\/tex;\">x<\/script> that optimizes a linear objective function subject to linear constraints. For example, given a matrix <script type=\"math\/tex;\">A\\in {\\mathbb R}^{n\\times m}<\/script> and vectors <script type=\"math\/tex;\">b\\in {\\mathbb R}^n<\/script>, <script type=\"math\/tex;\">c\\in {\\mathbb R}^m<\/script>, find <\/p>\n<div id=\"a0000000003\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\min _x \\{  c\\cdot x ~ |~  x\\in {\\mathbb R}_+^m, ~ Ax \\ge b\\} . <\/script><\/div>\n<p>A <em>feasible solution<\/em> is any vector <script type=\"math\/tex;\">x<\/script> satisfying the constraints <script type=\"math\/tex;\">x\\in {\\mathbb R}_+^m<\/script> and <script type=\"math\/tex;\">Ax \\ge b<\/script>, and the objective function (or <em>cost<\/em>) is <script type=\"math\/tex;\">c\\cdot x = \\sum _j c_j x_j<\/script>. Linear programs may take other forms, for example <script type=\"math\/tex;\"> \\max \\{  c\\cdot x ~ |~  x\\in {\\mathbb R}_+^m, ~ Ax \\le b\\} .<\/script> <\/p>\n<p>Integer Linear Programming adds an additional constraint <script type=\"math\/tex;\">x\\in {\\mathbb Z}_+^m<\/script> \u2014 the variables should be assigned integer values. For example, given <script type=\"math\/tex;\">(A,b,c)<\/script> as above, find <script type=\"math\/tex;\"> \\min \\{  c\\cdot x ~ |~  x\\in {\\mathbb Z}_+^m, ~ Ax \\ge b\\} .<\/script> (The feasible solutions are constrained to have integer values.) <\/p>\n<p>A linear program (or integer linear program) is a <em>packing<\/em> problem provided it is of the form <script type=\"math\/tex;\">\\max \\{ c\\cdot x ~ |~  A x \\le b, x \\ge 0\\} <\/script> where every entry in <script type=\"math\/tex;\">A<\/script> is non-negative. Likewise, a linear program is a <em>covering<\/em> problem if it is of the form <script type=\"math\/tex;\">\\min \\{ c\\cdot x ~ |~  A x \\ge b, x \\ge 0\\} <\/script>, and <script type=\"math\/tex;\">A<\/script> has only non-negative entries. <\/p>\n<p>Linear Programming is efficiently solvable \u2014 there are algorithms that, given any linear program, are guaranteed to find an optimal solution and to run in time polynomial in the size of the input. No such algorithms are known for Integer Linear Programming. Integer Linear Programming is NP-hard (constraining variables to take integer values allows small systems of linear constraints to represent computationally intractable combinatorial problems). That is, Integer Linear Programming does not have a polynomial-time algorithm unless P=NP. Integer Linear Programming is still a very useful abstraction for designing approximation algorithms. <\/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=\"a0000000004\">Example<\/h1>\n<p> The packing problem <script type=\"math\/tex;\">\\max x+y<\/script> subject to <script type=\"math\/tex;\">x+2y\\le 10<\/script>, <script type=\"math\/tex;\">5x+3y \\le 20<\/script>, and <script type=\"math\/tex;\">x,y\\ge 0<\/script> is illustrated in the two-dimensional plane below. <\/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\/08\/img-0001.png\" alt=\"\\includegraphics[type=pdf,ext=.pdf,read=.pdf,width=3.75in]{shared\/graphics\/linear_program}\" style=\"width:3.75in\" class=\"zoooom\" \/> <\/span> <\/p>\n<p>The feasible region is the white area in the positive quadrant. The dashed vector points in the direction of increasing cost (<script type=\"math\/tex;\">x+y<\/script>). The optimal feasible solution is <script type=\"math\/tex;\">(1\\frac{3}{7},4\\frac{2}{7})<\/script> (marked by \u201c*\u201d), of cost <script type=\"math\/tex;\">5\\frac{5}{7}<\/script>. The feasible integer solutions (feasible solutions of the corresponding integer linear program) are marked with black dots. Three of these have maximum cost <script type=\"math\/tex;\">5<\/script>. The solution <script type=\"math\/tex;\">(2,2)<\/script> of cost <script type=\"math\/tex;\">4<\/script> is a <script type=\"math\/tex;\">1\\frac{1}{4}<\/script>-approximate solution to the integer linear program and a <script type=\"math\/tex;\">1\\frac{3}{7}<\/script>-approximate solution to the linear program. <\/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=\"a0000000005\">Additional notes related to linear programming<\/h1>\n<div class=\"ccchildpages\"><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/background\/linear-programming\/modeling\/\" class=\"\">modeling Set Cover and Multicommodity Flow<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>Set Cover and Multicommodity flow as (integer) linear programs.<\/em><\/center><\/blockquote>  Modeling a problem as a linear program or integer linear program is a basic skill. Here are two examples.\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/background\/linear-programming\/modeling\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><article class=\"hentry ccchildpage\">\r\n<header class=\"entry-header\">\r\n<h1 class=\"entry-title\">\r\n<a href=\"https:\/\/algnotes.info\/on\/background\/linear-programming\/rounding\/\" class=\"\">rounding an LP relaxation<\/a>\r\n<\/h1>\r\n<\/header>\r\n<div class=\"entry-summary\">\r\n<div class=\"latex-file\"><div class=\"latex-document\"> <div class=\"latex-outer-sheet\"><div class=\"latex-inner-sheet\"> <p><blockquote class=\"quote\"><center><em>A simple example of computing an approximate solution by rounding the solution to a linear-program relaxation.<\/em><\/center><\/blockquote><p>The basic paradigm: <\/p><ol class=\"enumerate\"> <li value=\"1\"><p>Model your problem as an integer linear program. <\/p><\/li><li value=\"2\"><p>Solve its linear program relaxation. <\/p><\/li><li value=\"3\"><p>Somehow <em>round<\/em> the solution <script type=\"math\/tex;\">x^*<\/script> of the relaxed problem to get a solution <script type=\"math\/tex;\">\\tilde x<\/script> of the original problem. <\/p><\/li> <\/ol><p>The rounding step is typically most easily done with a so-called <em>randomized rounding<\/em> scheme. <\/p><p>Rounding a relaxation is one of two standard ways to use linear-programming relaxations to design approximation algorithms. (The other way is the <em>primal-dual method<\/em>.)\r\n<!--- a href=\"https:\/\/algnotes.info\/on\/background\/linear-programming\/rounding\/\" class=\"\">More...<\/a --->\r\n<\/div>\r\n<footer class=\"entry-meta\">\r\n<\/footer>\r\n<\/article><\/div>\n<\/div>\n<div class=\"latex-section\">\n<h1 id=\"a0000000006\">Wikipedia<\/h1>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Linear_programming\">linear programming<\/a> <\/p>\n<\/li>\n<li>\n<p><a href=\"http:\/\/en.wikipedia.org\/wiki\/Linear_programming#Covering.2Fpacking_dualities\">covering and packing<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Notes on Linear Programming and Integer Linear Programming.<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8676,"menu_order":3,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1468","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1468","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=1468"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/1468\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8676"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=1468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}