{"id":1208,"date":"2010-09-14T12:04:40","date_gmt":"2010-09-14T16:04:40","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1208"},"modified":"2010-09-14T12:04:40","modified_gmt":"2010-09-14T16:04:40","slug":"call-for-challenging-mip-problems","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2010\/09\/14\/call-for-challenging-mip-problems\/","title":{"rendered":"Call for Challenging MIP Problems"},"content":{"rendered":"

MIPLIB<\/a> is a collection of instances of Mixed Integer Programs.\u00a0 Versions of MIPLIB have been around since 1992, and these have been invaluable as we see how we have advanced in solving difficult MIP instances. Some instances that were essentially unsolvable twenty years ago can now be solved in a fraction of a second.\u00a0 We know we are getting better!\u00a0 Of course, there is a downside:\u00a0 maybe we are just getting better at solving MIPLIB instances.\u00a0 For instance, here is an extract from an excellent optimization code to attack MIPLIB:<\/p>\n

if (problem == \"team10\") then {\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 sol_val = 924;\n\u00a0\u00a0\u00a0 }\nelse if (problem == \"a1c1s1\") then { ...\n<\/pre>\n
Now, I don’t claim that any real code cheats this blatantly, but it is inevitable that as codes use benchmarks like MIPLIB, they will become tuned to the issues that come from those instances.<\/p>\n
This makes it important that MIPLIB reflect a broad range of issues faced “in the real world”.\u00a0 So it is very good that the MIPLIB people (a group based at ZIB in Berlin<\/a>, but including people from all over) are updating the library to create MIPLIB 2010<\/a>.\u00a0 If you have hard or real-life MIP instances, particularly if they are taking 15 minutes to 2 hours with commercial codes, you are welcome to upload those instances for consideration for the new library.\u00a0 The more varied the library, the better our field will be.<\/p>\n
There is one other biasing aspect that an update to MIPLIB 2010 does not fix and that is the emphasis on talking about integer programs as MPS files.\u00a0 Once an instance is in an MPS file, it is often extremely difficult to back out the underlying structure.\u00a0 Our constraint programming brethren are happy to talk about formulations with global constraints like alldifferent<\/em> and to have codes that explicitly take advantage of those structures.  I do wonder if we would be better at solving integer programs if we talked about them as higher-level structures (like tour(x1,x2,x3)<\/em> and matching(x,y)<\/em> and other common substructures).\u00a0 By limiting ourselves to MPS format, the structures we exploit tend to be those easiest to find, like knapsack<\/em> and setcovering<\/em>).<\/p>\n
But that is a topic for the future:\u00a0 right now, we need to be sure MIPLIB 2010 is as varied and interesting as it can be!<\/p>\n","protected":false},"excerpt":{"rendered":"
MIPLIB is a collection of instances of Mixed Integer Programs.\u00a0 Versions of MIPLIB have been around since 1992, and these have been invaluable as we see how we have advanced in solving difficult MIP instances. Some instances that were essentially unsolvable twenty years ago can now be solved in a fraction of a second.\u00a0 We … Continue reading “Call for Challenging MIP Problems”<\/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":[10,12],"tags":[],"class_list":["post-1208","post","type-post","status-publish","format-standard","hentry","category-challenges","category-computing"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1208","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=1208"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1208\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1208"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1208"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1208"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}