{"id":646,"date":"2008-06-10T15:50:12","date_gmt":"2008-06-10T15:50:12","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2008\/06\/10\/solving-linear-programming-problems\/"},"modified":"2008-06-10T15:50:12","modified_gmt":"2008-06-10T15:50:12","slug":"solving-linear-programming-problems","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2008\/06\/10\/solving-linear-programming-problems\/","title":{"rendered":"Solving Linear Programming Problems"},"content":{"rendered":"

So, I’ve finally had some time to get back to the linear programming
\nfollowup. You might want to go back and look at the earlier post<\/a> to remember what I was talking about.<\/p>\n

<\/p>\n

The basic idea is that we’ve got a system we’d like to optimize. The constraints of the system are defined by a set of linear inequalities, and
\nwe’ve got a linear expression that we’d like to maximize.<\/p>\n

So, for example, we could have a factory which is capable of producing two
\ndifferent kinds of widgets. The factory has a maximum capacity of what it can
\nproduce of 300 widgets per day. It gets a supply of metal and plastic for
\nmaking widgets: 5000 kilograms of steel, and 100 kilograms of plastic. There
\nare two kinds of widgets. Type 1 widgets take 23 kg of steel, and 2kg of
\nplastic, and sell for $900 each. Type 2 widgets take 5kg of steel, and 2
\nkilograms of plastic, and sell for $700 each. The factories customers need a
\nminimum of 5 type 1 and 2 type 2 widgets per day. So, the question is, what’s the optimal way to run the factory? How many of each widget should it make?<\/p>\n

Using the formulation we discussed last time, we can formulate this
\nas a linear programming problem as follows:<\/p>\n

    \n
  1. Let x1 be the number of type one widgets we produce.<\/li>\n
  2. Let x2 be the number of type two widgets we produce.<\/li>\n
  3. Objective:<\/b> maximize 900x1<\/sub> + 700x2<\/sub>, where:<\/li>\n
  4. x1<\/sub> + x2<\/sub> ≤ 300<\/li>\n
  5. 23x1<\/sub> + 5x2<\/sub> ≤ 500<\/li>\n
  6. 2x1<\/sub> + 2x2<\/sub> ≤ 50<\/li>\n
  7. x1<\/sub> ≥ 5, x2<\/sub> ≥ 2<\/li>\n<\/ol>\n

    Now, how do we get the answer? As I discussed last time,
    \nthere’s a conceptually simple algorithm called simplex<\/em>. The
    \nidea of the simplex algorithm is to do a basic form of something called hill-climbing. The idea of hill-climbing is really simple. You’re looking for the highest possible point in something which is modeled as a surface. So you try to go uphill: each step, you look for the next step which will get you the furthest up.<\/p>\n

    In simplex, you know that the solution is a vertex of an N-dimensional polygon. So you find an initial vertex – it doesn’t matter which one. Then you look at the edges that are incident on that vertex – and you pick the one that looks like it’ll get you the farthest uphill. You keep doing that until you get to one where no edge will take you to a higher vertex – and you’re at the maximum.<\/p>\n

    In general, simplex is very fast. Typically, even if you have the bad luck to start at a minimum vertex, you’ll get to the maximum very quickly. But the worst case is pretty bad: you can create LP problems where you’ll wind up visiting every<\/em> vertex. You can see why by imagining a cube. You can distort the cube so that if you start at the minimum vertex, and always climb the edge with the steepest slope, you’ll have to visit every single vertex. And there are O(2n<\/sup>) vertices in an N-dimensional polygon. As you increase dimensions, you can do the same distortion trick, to force the simplex algorithm to visit all of the vertices. (Or at least O(2N<\/sup>) vertices.) But those cases are very rare, and frankly very contrived. So
    \nin general, you don’t worry about them.<\/p>\n

    There are other algorithms to solve linear programming problems. There’s a very fast one – fast even in the pathological worst cases – called the interior points method. But for the most part, simplex is the way people go. <\/p>\n

    If you really need to solve a linear programming problem, you
    \ndon’t<\/em> generally write simplex yourself. Implementing simplex
    \ncorrectly is a pain. It’s typical of complex numerical analysis problems –
    \nit’s a miserable pain in the ass to implement. But, it’s also such a common
    \nproblem that there are a huge number of highly optimized solvers already
    \nwritten; you just grab one off the shelf. (There’s a lesson in there;
    \nnever waste time doing work yourself if you know someone else has already done it.) So, for this post, I grabbed a copy
    \nof     maxima<\/a>, an open-source symbolic algebra system, which
    \nincludes a very nice solver.<\/p>\n

    In the last post, I showed how you can formulate the problem as a matrix, which is the input for the simplex algorithm. But maxima, since it’s so good at symbolic work, doesn’t even require you to do that (although most<\/em> simplex solvers do take the problem in matrix form). Here’s how I wrote the problem as a maxima script:<\/p>\n

    \nload(\"simplex\")$\nmaximize_lp(\t9*x1 + 7*x2,\n[x1 + x2 <= 300,\n23*x1 + 5*x2 <= 500,\n2*x1 + 2*x2 <= 50,\nx1 >= 5,\nx2 >= 2]), nonegative_lp=true;\n<\/pre>\n
     When I feed that in to maxima, it converts it to the matrix form,
    \nand then solves it. The answer is that the maximum profit is
    \nabout $21,667, which you can make by producing 4 1\/6 type 1 widgets,
    \nand 20 5\/6 type 2 widgets. <\/p>\n
     Now, that’s very nice isn’t it? We can maximize the factory’s profit
    \nby producing 4 1\/6 type one widgets. How how we produce 1\/6th of a widget?<\/p>\n
     The way we formulated the problem is great for working out probabilities
    \nfor optimal grand strategies for zero-sum games – probabilities can
    \nbe arbitrary real numbers. But for the problem that we’re talking about – optimizing profit by producing discrete entities, you need an additional
    \nconstraint: the values in the solution must be integers. <\/p>\n
     For integer solutions, the simplex method goes right out the window. It’s actually an entirely different problem: integer linear programming. The strategies and solutions for solving ILP programs are quite different. Integer linear programming is a much harder problem. Instead of the polynomial time
    \nalgorithms that work for general LP, ILP is NP-hard – that is, its decision
    \nproblem (asking “Is this the optimal solution?”) is NP-complete; actually computing the answer is even worse.<\/p>\n
     Anyway, next post, we’ll get back to game theory – how we can set
    \nup a zero-sum game as a linear programming matrix in order to find the
    \noptimal grand strategy.<\/p>\n","protected":false},"excerpt":{"rendered":"
    So, I’ve finally had some time to get back to the linear programming followup. You might want to go back and look at the earlier post to remember what I was talking about.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[88],"tags":[],"class_list":["post-646","post","type-post","status-publish","format-standard","hentry","category-game-theory"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-aq","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/646","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=646"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/646\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=646"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=646"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=646"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}