Instances for the paper    Basis Reduction and the Complexity of Branch-and-Bound   

The INEQUALITY constrained instances are of the form b - e ≤ Ax ≤ b, 0 ≤ x ≤ e, x integral ,
where A is a 5 by 40 matrix with entries in {1, ..., M} , and b = Ae/2 (rounded down)
There are 12 instances for the values of M = 100, 1000, 10000 each.
We give the original formulations, and the rangespace reformulations.

The EQUALITY constrained instances are of the form { Ax = b, 0 ≤ x ≤ e, x integral , }. where A and b are the same as above.
We give the original formulations, and the Aardal-Hurkens-Lenstra, i.e. nullspace reformulations.

A surprising phenomenon (whose theoretical explanation is in the paper) that the reformulations become easier as M grows.

  INEQUALITY CONSTRAINED PROBLEMS

  1. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  2. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  3. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  4. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  5. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  6. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  7. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  8. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  9. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  10. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  11. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef
  12. M=100: Original   RSRef    M=1000: Original   RSRef    M=10000: Original   RSRef

  EQUALITY CONSTRAINED PROBLEMS

  1. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  2. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  3. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  4. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  5. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  6. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  7. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  8. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  9. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  10. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  11. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef
  12. M=100: Original   NSRef    M=1000: Original   NSRef    M=10000: Original   NSRef


You can also download ALL the lp files listed here as a single file created with winrar here.