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 x₅₁ = px is added).

DKPFEAS gives the default (feasibility) version of DKP: { β₁ ≤ ax ≤ β₂, 0 ≤ x ≤ u}. DKPOPT gives the optimality version: max { ax | ax ≤ β₂, 0 ≤ x ≤ u }. 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 = β | x ≥ 0 }. β^* 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 a_j).

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