[Coin-discuss] Benchmark Instances & code for format conversions

Anureet Saxena anureet at yahoo.com
Thu Apr 27 01:10:29 EDT 2006


dear all,
   
  I am a doctoral student at Carnegie Mellon University working on computational mixed integer programming. I am conducting an experiment to evaluate the effectiveness of rank-1 split cuts on structured mixed integer programs. As I started out to construct a test-bed for my experiment, I faced several problems and I believe this is an appropriate forum to discuss them.
   
  While COIN-OR provides wonderful "COmputational INfrastructure" for developing algorithmic tools in OR, it gives no support for "testing" these tools. For instance, consider the following scenario. You read about an optimization algorithm in a paper and you get an idea on how to improve it. There are two steps which are involved in putting your idea to a litmus test:
   
  1. A correct implementation of your idea.
2. Access to the set of benchmark instances which were used in the paper  in "appropriate format".
   
  While COIN-OR can go a long way in simplifying step 1 above, there is presently no support for step 2. Consequently, even after someone has developed an implementation of his idea, he can still be handicapped by the unavailability of the instances. The problem of unavailability of benchmark instances is more complex than it seems for the following reason:
   
  1. Maintaining benchmarks in usable format and making them publicly available is a difficult task. Here is a reply I got from an author after requesting for benchmark instances which were used in his 2003 paper
   
  "....Regarding the instances, I regret to say that they are lost, after moving so much. ..."
   
  2. Even if the instances are publicly available, they are available in ASCII format which entails additional work in converting them to .mps format. For instance, there is an amazing collection of benchmark instances at OR-Library. However to use them in my experiment, I need to write additional code to convert them to .mps format. Interestingly, anyone who would like to experiment with the branch-and-cut approach on these instances "HAS" to undergo this programming exercise.
   
  3. Many a times people use random instances for their experiments. Unless the experiment is repeated with precisely those instances, it is very difficult to accurately gauge the impact of any new idea. (And of course there is an implementation effort involved in reproducing those instances, see (2) above).
   
  4. There is no central library for OR-Benchmark instances (please correct me if I am wrong). Benchmark instances are scattered all across the www and it is extremely difficult to find them in the correct format. The problem is even more acute when the instances are available in a software-specific format -- for instance making the instances available in modelling (opl, mozel) formats of CPLEX/XPRESS is not very helpful, if you do not have access to these softwares.
   
  To summarize, availability of benchmark instances in "appropriate format" is an equally important aspect of computational OR as is the availability of the code. In my opinion, maintaining benchmark instances and "format conversion codes" along with the implementation code would greatly enhance the scope and reach of COIN-OR. 
   
  I would like to know the reaction of others on this issue. 
   
  regards,
Anureet Saxena,
ACO PhD Student,
Tepper School of Business,
Carnegie Mellon University.
http://www.andrew.cmu.edu/user/anureets/
  
PS1: I have a code for a converting the ASCII instances of OR-Library to .mps format for the following classes of problems: Capacitated Warehouse Location Problem, Capacitated p-Median Problem and AirLanding Scheduling Problems. I would be happy to contribute this code along with the .mps instances. 
   
  PS2: I am searching for benchmark instances (both structured and unstructured MIPs) and would appreciate any pointers to publicly available instances besides the following: MIPLIB, Mittleman Instances, CORAL Instances, OR-Library, Atamturk Instances, DIMACS challenge instances.
   
  
 


Anureet Saxena
 anureet at cmu.edu
 anureet at yahoo.com
 
--This mail was delivered to you on 100% recyclable electrons.
		
---------------------------------
How low will we go? Check out Yahoo! Messenger’s low  PC-to-Phone call rates.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20060426/34d44652/attachment.html>


More information about the Coin-discuss mailing list