Column basis reduction and decomposable knapsack problems   DOI

Given below are the CPLEX .lp files for the ten instances reported in the paper. All instances have the coefficient vectors decompose as a = pM + r, for M = 10000. Orig gives the original problem in each case. RSRef and NSRef give the rangespace and nullspace reformulations of the original problem, respectively. BranchOnpx gives the formulation of the original problem with the branching direction px added as a separate variable (equivalently, the constraint x51 = px is added).

DKPFEAS gives the default (feasibility) version of DKP: { β1ax ≤ β2, 0xu}. DKPOPT gives the optimality version: max { ax | ax ≤ β2, 0xu }. Let the optimal objective function value of this problem be βa. Eq_ba gives the equality-constrained knapsack problem with ax = βa, and Eq_ba_p1 gives the equality-constrained knapsack problem with ax = βa+1. The unbounded equality knapsacks are { ax = β | x0 }. β* is the largest value of β for which the infeasibility of the unbounded equality knapsack is proven by branching on px, and Frob(a) gives the Frobenius number of a (which is the largest number that cannot be expressed as a non-negative integer linear combination of the numbers aj).

The parameter settings used for normal CPLEX runs is here, while that for very basic CPLEX is here.


  DKPs with u=e

  1. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef
  2. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  3. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  4. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  5. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  6. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  7. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  8. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  9. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  10. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  

  DKPs with u=10e

  1. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  2. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  3. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  4. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  5. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  6. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  7. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  8. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  9. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  
  10. DKPFEAS: Orig   RSRef   BranchOnpx     DKPOPT: Orig   RSRef    Eq_ba: Orig   RSRef   NSRef     Eq_ba_p1: Orig   RSRef   NSRef  

  Unbounded equality knapsacks

  1. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  2. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  3. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  4. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  5. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  6. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  7. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  8. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  9. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    
  10. β=β*: Orig   RSRef   NSRef   BranchOnpx;       β=Frob(a): Orig   RSRef   NSRef   BranchOnpx    

You can also download ALL the lp files listed here as a single tar-bzip2-ed file here.




Bala Krishnamoorthy
Last modified: Sun Dec 07 02:38:11 PST 2008