[Coin-discuss] Re: Benchmark Instances & Format conversion code

[Anureet Saxena]

hi,
   
  Thanks for replying to my earlier email and educating me on some of the relevant issues. After going through the comments, this is what I have decided to do.
   
  I would maintain a repository (instances or www-links to instances) of benchmark instances available in .mps format. If some of these instances were converted from ASCII format, then the conversion code (preferably using COIN-OR libraries) along with a description of the model would also be made available under a suitable license.  
   
  I am conducting an experiment which requires me to get an estimation of hardness of the instances. For this purpose, I generate the following information which would be included alongwith:
   
  1. Problem Stats: nrows, ncols, nbinary-var, nint-var
2. Best Solution (actual solution and solution value) obtained by CPLEX within a certain time-limit of T min. (T=15 or 60)
3. Number of B&B nodes enumerated and the best lower bound obtained by CPLEX within T min.
   
  As for the format, I can ensure that these .mps files are OsiClp-readable. I would post the database on my homepage and if this initiative gathers sufficient momentum then we can shift it to COIN-repository in future.
   
  I presently have the following instances in .mps format along with the additional information mentioned above:
   
  OrLib:-
- Capacitated Warehouse Location Problems (Set 1: 37 instances, Set 2: 12 instances)
- Capacitated p-Median Problems (20 instances)
- AirLanding Scheduling Problems (25 instances)
   
  Atamturk Instances:- (These are available in .mps format on Prof. Atamturk's homepage)
- Mixed Knapsack Problems (Unbounded: 30 instances, Bounded: 90 instances)
- Fixed Charge Network Flow Problems (20 instances)
- Capacitated Lot Sizing Problems (100 instances) 
- Splittable Network Flow Problems (33 instances)
- Network design with additive Upper Bound Constraints (60 instance)
   
  Miscellaneous Instances:-
- Holmberg Single Source Capacitated Facility Location Problems (71 instances)
- Generalized Assignment Problems of Mutsunori Yagiura (58 instances)
   
  If you have problem instances in .mps format or ASCII format with a conversion code, please free to send them to me with a short message which gives me permission to put them on www. 
   
  regards,
Anureet Saxena
anureet at cmu.edu
   
  PS: Comments are welcome. Please write directly to anureet at cmu.edu. 
   
  PS: Why in .mps format?
   
  Many people raised concerns about the .mps format. I am not a big admirer of .mps format or any other format which masks the inherent structural information. Nevertheless .mps format is easily the best available "structure-free" format for expressing most of the mixed integer "linear" programming models. For instance, suppose one would like to test the effect of adding the flow-cuts in network models of several different types. There are in-numerous network models and access to such a structure-free format can tremendously speed up the research-process. I am presently involved in a similar experiment related to split cuts and that explains the reason to start such a repository.
   
  Finally a quick comment on models with exponentially many inequalities. Indeed these models cannot be represented via the .mps format. However, a relaxation of these instances obtained by keeping only the cuts generated at the root node (by SYMPHONY or CONCORDE for instance) could provide an extremely useful relaxation for testing cutting plane methods. I have preliminary understanding of SYMPHONY and I am sure there is a neat way (just 2 lines of code at the right place should suffice) of extracting such a relaxation. Unfortunately, I have been so far unsuccessful in hacking the code to do so :( If someone has experience with SYMPHONY and knows an easy way to extract such a root-relaxation, please let me know.
   
   
   


Anureet Saxena
 anureet at cmu.edu
 anureet at yahoo.com
 
--This mail was delivered to you on 100% recyclable electrons.
			
---------------------------------
Yahoo! Mail goes everywhere you do.  Get it on your phone.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20060501/a96e74d0/attachment.html>