{"id":1357,"date":"2011-01-23T14:24:06","date_gmt":"2011-01-23T18:24:06","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1357"},"modified":"2011-01-23T14:24:06","modified_gmt":"2011-01-23T18:24:06","slug":"the-sexiness-of-integer-programming","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2011\/01\/23\/the-sexiness-of-integer-programming\/","title":{"rendered":"The Sexiness of Integer Programming"},"content":{"rendered":"<p><a href=\"http:\/\/www.cs.utah.edu\/~suresh\/web\/\">Suresh Venkatasubramanian<\/a>, of the excellent <a href=\"http:\/\/geomblog.blogspot.com\/\">Geomblog<\/a>, is at SODA and covered some preconference conferences.  When <a href=\"http:\/\/geomblog.blogspot.com\/2011\/01\/alenexanalco.html\">covering a paper that used integer programming<\/a> (via CPLEX), his comment was:<\/p>\n<blockquote><p>It&#8217;s not the &#8220;sexiest&#8221; thing in the world to solve algorithms problems in practice by using large industrial strength packages.<\/p><\/blockquote>\n<p><em>Oh, he didn&#8217;t say that, did he?<\/em><\/p>\n<p>I spend most of my life &#8220;solving algorithms problems in practice by using large industrial strength packages&#8221;.  I solve sports scheduling problems, logistics problems, and even problems in social choice with large scale integer programming software as my primary tool.  Who says I am not sexy?  Or, worse, that <em>my research<\/em> is not sexy?<\/p>\n<p>I can think of a few misconceptions that might lead one to doubt the sexiness of integer programming.  <\/p>\n<ul>\n<li><em>Integer Programming is uncreative. <\/em> After all, you just formulate the problem in terms of variables, linear objective, and linear constraints, toss it in a code, and you are done.  Where is the research?\n<p>Such a view ignores the tremendous number of choices once must make in formulating integer programming.  The choice of variables, constraints, and objective can have a tremendous impact on the effectiveness of the solver.  While solvers continue to get better at automatically identifying formulation improvements, formulating integer programs is still an art.  It is an art, however, enhanced by theory.  As we better understand the polyhedral characteristics of integer programming formulations, we create better and better formulations.<\/p>\n<p>This creative effort is expanded when alternatives to &#8220;basic&#8221; formulations are included.  Creating a branch-and-price, branch-and-cut, Benders, or other type of formulation can be the key to solving real problems, but may require significant research effort.<\/p>\n<\/li>\n<li><em>Integer programming is slow. <\/em> This seems to be the most common response I get from those outside the integer programming subfield.  One quote from a person at a well-known computer science-oriented firm:  &#8220;I tried integer programming.  It doesn&#8217;t work.&#8221;  Not &#8220;It doesn&#8217;t work for this problem&#8221; or &#8220;I couldn&#8217;t make it work&#8221;.  Just &#8220;It doesn&#8217;t work&#8221;.  How can a topic be sexy if it doesn&#8217;t work?\n<p>I think one of the great stories in all of mathematics and business is the incredible confluence between increased data, faster computers, algorithmic improvements, and implementation successes that have led to many orders of magnitude speed increases in integer programs.  Over the last fifteen years, we have gotten much, much better at solving integer programming models.  With the underlying linear programming solvers being more than million times faster (no hyperbole:  both computers and algorithms provide more than a 1000 time speedup each), lots of instances formerly out of reach can now be solved routinely.<\/p>\n<p>Of course, integer programming is exponential time in the worst case.  But I am not sure why a polynomial time algorithm that gets an approximate solution within a factor of, say, 42 is any &#8220;sexier&#8221; than an algorithm that finds the optimal solution in a reasonable amount of time for any instance of practical import.\n<\/li>\n<li><em>Integer programming is expensive.<\/em>  Hey, if you have to spend tens of thousands of dollars for solutions, that really doesn&#8217;t count does it?  It is like a troll dressed up in a $5,000 suit:  it might look OK, but it&#8217;s not sexy!\n<p>No one has to pay a lot for high quality integer programming software.  Suresh refers to this in his post:<\/p>\n<blockquote><p>This was surprising to me on two levels: firstly, that CPLEX is actually free for academic use (who knew!) and that such a simple approach is so effective.<\/p><\/blockquote>\n<p>Actually, all the major programs offer a way for free academic use.  I particularly like <a href=\"http:\/\/www.gurobi.com\/html\/academic.html\">Gurobi&#8217;s approach<\/a>, which is based on periodic validation through a &#8220;.edu&#8221; domain, but academics can also get <a href=\"https:\/\/www.ibm.com\/developerworks\/university\/academicinitiative\/\">CPLEX<\/a> (as you would have <a href=\"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1048\">read on my blog <\/a>last year) and <a href=\"http:\/\/optimization.fico.com\/academic-partner-program-app.html\">XPRESS<\/a>.<\/p>\n<p>And if you are not an academic?  <a href=\"http:\/\/www.coin-or.org\">COIN-OR<\/a> offers &#8220;industrial strength&#8221; linear and integer programming in an open source approach.\n<\/li>\n<\/ul>\n<p>In Suresh&#8217;s defense, here is the full quote, where he makes clear his support for this type of research:<\/p>\n<blockquote><p>It&#8217;s not the &#8220;sexiest&#8221; thing in the world to solve algorithms problems in practice by using large industrial strength packages. However, both CPLEX and  SAT solvers are examples of tools that can be used in practice to solve fairly intractable problems. It still takes a lot of engineering and skill to make the heuristics work well, but it&#8217;s something that we should be using as a matter of course when designing heuristics before trying to invent an algorithm from scratch.<\/p><\/blockquote>\n<p>Suresh obviously gets it:  let&#8217;s hope his post expands interest in integer programming methods for these problems.<\/p>\n<p>Integer programming is useful, fast, and cheap.  If that isn&#8217;t sexy (for an algorithm!), then I don&#8217;t know what is.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Suresh Venkatasubramanian, of the excellent Geomblog, is at SODA and covered some preconference conferences. When covering a paper that used integer programming (via CPLEX), his comment was: It&#8217;s not the &#8220;sexiest&#8221; thing in the world to solve algorithms problems in practice by using large industrial strength packages. Oh, he didn&#8217;t say that, did he? I &hellip; <a href=\"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2011\/01\/23\/the-sexiness-of-integer-programming\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;The Sexiness of Integer Programming&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6,37,46],"tags":[],"class_list":["post-1357","post","type-post","status-publish","format-standard","hentry","category-blogs-and-web","category-open-source","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1357","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1357"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1357\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1357"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}