Category: Challenges

I have been thinking about the issue of how a field knows what they know.  In a previous post, I wrote about how the field of social psychology is working through the implications of fraudulent research, and is closely examining the cozy interactions between journals, reviewers, and famous researchers.   And any empirical field based on statistical analysis has got to live with the fact that if there 1000 results in the field, some number (50 perhaps, if p=.05 is a normal cutoff and lots of results are just under that value) are going to be wrong just because the statistical test created a false positive.  Of course, replication can help determine what is real and what is not, but how often do you see a paper “Confirming Prof. X’s result”?  Definitely not a smooth path to tenure.

This is worse if malevolent forces are at work.  Suppose a pharmaceutical company has bet the firm on drug X, and they want to show that drug X works.  And suppose drug X doesn’t work.  No problem!  Simply find 20 researchers, sign them to a non-disclosure, and ask them to see if drug X works.  Chances are one or more researchers will come back with a statistically significant result (in fact, there is about a 65% chance that one or more will, given a p=.05).  Publish the result, and voila!  The company is saved!  Hurray for statistics and capitalism!

Fortunately, I am not the first to see this issue:  way back in 1997, the US Congress passed a bill requiring the registration of clinical trials, before the trials get underway.

The first U.S. Federal law to require trial registration was the Food and Drug Administration Modernization Act of 1997 (FDAMA) (PDF).

Section 113 of FDAMA required that the National Institutes of Health (NIH) create a public information resource on certain clinical trials regulated by the Food and Drug Administration (FDA). Specifically, FDAMA 113 required that the registry include information about federally or privately funded clinical trials conducted under investigational new drug applications (INDs) to test the effectiveness of experimental drugs for patients with serious or life-threatening diseases or conditions.

This led to the creation of clinicaltrials.gov (where I am getting this history and the quotes) in 2000.  This was followed by major journals requiring registration before papers could be considered for publication:

In 2005 the International Committee of Medical Journal Editors (ICMJE) began to require trial registration as a condition of publication.

• ICMJE Uniform Requirements for Manuscripts Submitted to Biomedical Journals – Obligation to Register Clinical Trials
• ICMJE Frequently Asked Questions about Clinical Trials Registration

MIPLIB is a collection of instances of Mixed Integer Programs.  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.  We know we are getting better!  Of course, there is a downside:  maybe we are just getting better at solving MIPLIB instances.  For instance, here is an extract from an excellent optimization code to attack MIPLIB:

if (problem == "team10") then {
       sol_val = 924;
    }
else if (problem == "a1c1s1") then { ...

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.

This makes it important that MIPLIB reflect a broad range of issues faced “in the real world”.  So it is very good that the MIPLIB people (a group based at ZIB in Berlin, but including people from all over) are updating the library to create MIPLIB 2010.  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.  The more varied the library, the better our field will be.

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.  Once an instance is in an MPS file, it is often extremely difficult to back out the underlying structure.  Our constraint programming brethren are happy to talk about formulations with global constraints like alldifferent 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) and matching(x,y) and other common substructures).  By limiting ourselves to MPS format, the structures we exploit tend to be those easiest to find, like knapsack and setcovering).

But that is a topic for the future:  right now, we need to be sure MIPLIB 2010 is as varied and interesting as it can be!