This is a web site to post certain instances from the paper A Parallel, Linear Programming Based Heuristic for Large Scale Set Partitioning Problems, by J. T. Linderoth, E. K. Lee, and M. W. P. Savelsbergh, that appeared in INFORMS Journal on Computing, 13 (2001), pp. 191-209.

Jeff is posting these here as a public service, and the information here is based on his notes taken at the time and his best recollections five years after he actually worked with the instances. Thus, he can’t really guarantee to be very helpful in answering any questions you have about the instances. But feel free to ask…

Happy MIP Solving!

727 Instance

The pairings are broken in 9 files. The files consist of lines whose first entry is the cost of the pairing, and the remaining (integer) entries are the row indices of the flight les that pairing covers. There are 342 rows and 12618766 columns in the IP. The LP relaxation has value zlp = 637.246540. The best known solution is 1108.86.

• 727pairings.40.txt.bz2
  
• 727pairings.41.txt.bz2
  
• 727pairings.42.txt.bz2
  
• 727pairings.43.txt.bz2
  
• 727pairings.44.txt.bz2
  
• 727pairings.45.txt.bz2
  
• 727pairings.46.txt.bz2
  
• 727pairings.47.txt.bz2
  
• 727pairings.48.txt.bz2
  

a320 instance

There are 190 rows and 8122371 columns in the IP formulation. The initial LP value is 940.649322 and the Optimal solution is 1078.

• a320-2.0.sp.bz2
  
• a320-2.1.sp.bz2
  
• a320-2.2.sp.bz2
  
• a320-2.3.sp.bz2
  
• a320-2.4.sp.bz2
  
• a320-2.5.sp.bz2
  
• a320-2.6.sp.bz2
  
• a320-2.7.sp.bz2
  
• a320-2.8.sp.bz2
  
• a320-2.9.sp.bz2
  

Inventory Routing

This instance comes from an Inventory Routing Application, and is given in MPS format…

• irp.mps.bz2
  

Vehicle Routing

These instances compe from capacitated vehicle routing. They are the set of routes I obtained after running a “few” rounds of a branch-and-price approach to solving the initial linear programming relaxation, with some extra routes just thrown in…

• eil33.2.mps.bz2
  
• eilA76.mps.bz2
  
• eilA101.2.mps.bz2
  
• eilB76.mps.bz2
  
• eilB101.mps.bz2
  
• eilB101.2.mps.bz2
  
• eilC76.mps.bz2
  
• eilC76.2.mps.bz2
  
• eilD76.mps.bz2
  
• eilD76.2.mps.bz2