the dual objective computed using dual variables obtained from the primal LP model differs from the optimal primal obj

Hello,

We are using Gurobi (version 11.0.2) as a linear programming solver in the Column Generation (CG) procedure. However, the CG procedure sometimes fails to terminate correctly for certain cases. To address this issue, we closely analyze the dual variables obtained from the primal LP model. These dual variables are crucial for computing the reduced cost, which guides the CG process. Confusingly, the dual objective, computed using these dual variables (with Gurobi generating the dual formulation of the primal model), does not match the primal objective.

Take the following model as an example: The optimal objective value is 90. The non-zero dual variables are as follows:  c1: -6.0, c3: 90, c6: 30, c11: 30, c13: 30, c16: 30, c20: 30, c28: 30, c32: 30, c35: 90, c45: 330, c46: 60, c47: 150, c48: 270, c49: -30.  The dual objective function is given by: - 180 c1 - 2147483647 c2 + c3 + c4 + c6 + c7 + c8 + c9 + c10 + c11 + c12 + c13 + c14 + c16 + c17 + c18 + c20 + c21 + c22 + c23 + c24 + c25 + c26 + c28 + c29 + c30 + c32 + c33 + c34 + c35 + c36 + c37 + c38 + c39 + c40 + c41 + c42 + c43 + c44 - c45 - c46 - c47 - c48 - c49. Surprisingly, the dual objective computed using these dual variables yields 690, rather than the expected 90 from the primal objective.

\ Model obj1
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
  30 x1 + 30 x2 + 30 x3 + 30 x4 + 30 x5 + 30 x6 + 30 x7 + 30 x8 + 30 x9
   + 30 x10 + 30 x11 + 30 x12 + 30 x13 + 30 x14 + 30 x15 + 30 x16 + 30 x17
   + 30 x18 + 30 x19 + 30 x20 + 30 x21
Subject To
 c1: 110 x22 + 180 x23 + 355 x24 + 380 x25 + 160 x26 + 150 x27 + 90 x28
   + 145 x29 + 200 x30 + 95 x31 + 150 x32 + 115 x33 + 155 x34 + 220 x35
   + 75 x36 + 75 x37 + 70 x38 + 180 x39 + 205 x40 + 140 x41 + 60 x42
   + 30 x43 + 100 x44 + 45 x45 + 50 x46 + 90 x47 + 85 x48 + 65 x49 + 45 x50
   + 45 x51 + 75 x52 + 90 x53 + 80 x54 + 110 x55 + 10 x56 + 75 x57 + 30 x58
   + 100 x59 + 110 x60 + 50 x61 + 60 x62 + 40 x63 + 30 x64 + 45 x65
   + 60 x67 + 30 x68 + 30 x69 + 60 x70 + 75 x72 + 45 x73 + 100 x74 + 75 x75
   + 50 x76 + 60 x77 + 30 x78 + 75 x79 + 85 x80 + 40 x81 + 40 x82 + 50 x83
   + 10 x84 + 60 x85 + 50 x86 <= 180
 c2: 30 x1 + 30 x2 + 30 x3 + 30 x4 + 30 x5 + 30 x6 + 30 x7 + 30 x8 + 30 x9
   + 30 x10 + 30 x11 + 30 x12 + 30 x13 + 30 x14 + 30 x15 + 30 x16 + 30 x17
   + 30 x18 + 30 x19 + 30 x20 + 30 x21 <= 2.147483647e+09
 c3: x23 + x26 + x48 + x49 + x51 + x53 + x54 + x63 + x73 + x78 + x82 >= 1
 c4: x1 + x23 + x26 + x48 + x49 + x51 + x53 + x54 + x63 + x73 + x78 + x82
   >= 1
 c5: x25 + x28 + x30 >= 0
 c6: x2 + x25 + x28 + x30 >= 1
 c7: x22 + x24 + x37 + x38 + x39 + x40 + x41 + x42 + x57 + x62 + x67 + x77
   >= 1
 c8: x3 + x22 + x24 + x37 + x38 + x39 + x40 + x41 + x42 + x57 + x62 + x67
   + x77 >= 1
 c9: x26 + x32 + x33 + x34 + x35 + x36 + x53 + x54 + x63 + x64 + x82 + x83
   + x84 + x85 + x66 >= 1
 c10: x4 + x26 + x32 + x33 + x34 + x35 + x36 + x53 + x54 + x63 + x64 + x82
   + x83 + x84 + x85 + x66 >= 1
 c11: x25 + x27 + x28 + x29 + x30 + x31 + x47 + x48 + x49 + x51 + x69 + x79
   + x81 + x71 >= 1
 c12: x5 + x25 + x27 + x28 + x29 + x30 + x31 + x47 + x48 + x49 + x51 + x69
   + x79 + x81 + x71 >= 1
 c13: x23 + x37 + x38 + x39 + x40 + x41 + x52 + x55 + x56 >= 1
 c14: x6 + x23 + x37 + x38 + x39 + x40 + x41 + x52 + x55 + x56 >= 1
 c15: x22 + x43 + x44 + x46 + x58 + x59 + x61 + x64 + x72 + x74 + x76 + x83
   + x84 + x85 + x66 >= 0
 c16: x7 + x22 + x43 + x44 + x46 + x58 + x59 + x61 + x64 + x72 + x74 + x76
   + x83 + x84 + x85 + x66 >= 1
 c17: x25 + x27 + x29 + x31 + x32 + x33 + x34 + x35 + x36 + x47 + x49 + x51
   + x68 + x69 + x79 + x81 + x71 >= 1
 c18: x8 + x25 + x27 + x29 + x31 + x32 + x33 + x34 + x35 + x36 + x47 + x49
   + x51 + x68 + x69 + x79 + x81 + x71 >= 1
 c19: x23 + x52 + x54 + x55 + x56 + x86 >= 0
 c20: x9 + x23 + x52 + x54 + x55 + x56 + x86 >= 1
 c21: x22 + x26 + x42 + x43 + x44 + x46 + x57 + x58 + x59 + x60 + x61 + x62
   + x64 + x67 + x72 + x73 + x74 + x76 + x85 + x66 >= 1
 c22: x10 + x22 + x26 + x42 + x43 + x44 + x46 + x57 + x58 + x59 + x60 + x61
   + x62 + x64 + x67 + x72 + x73 + x74 + x76 + x85 + x66 >= 1
 c23: x25 + x32 + x33 + x34 + x35 + x36 + x47 + x48 + x49 + x50 + x51 + x68
   + x69 + x83 + x84 + x71 >= 1
 c24: x11 + x25 + x32 + x33 + x34 + x35 + x36 + x47 + x48 + x49 + x50 + x51
   + x68 + x69 + x83 + x84 + x71 >= 1
 c25: x24 + x27 + x28 + x29 + x30 + x31 + x52 + x53 + x54 + x55 + x56 + x77
   + x78 + x79 + x80 + x81 + x86 >= 1
 c26: x12 + x24 + x27 + x28 + x29 + x30 + x31 + x52 + x53 + x54 + x55 + x56
   + x77 + x78 + x79 + x80 + x81 + x86 >= 1
 c27: x22 + x23 + x26 + x42 + x43 + x44 + x46 + x57 + x60 + x62 + x67 >= 0
 c28: x13 + x22 + x23 + x26 + x42 + x43 + x44 + x46 + x57 + x60 + x62 + x67
   >= 1
 c29: x25 + x37 + x38 + x39 + x40 + x41 + x47 + x48 + x50 + x58 + x59 + x61
   + x68 + x72 + x73 + x74 + x75 + x76 + x82 + x83 + x84 >= 1
 c30: x14 + x25 + x37 + x38 + x39 + x40 + x41 + x47 + x48 + x50 + x58 + x59
   + x61 + x68 + x72 + x73 + x74 + x75 + x76 + x82 + x83 + x84 >= 1
 c31: x24 + x27 + x28 + x29 + x30 + x31 + x52 + x53 + x56 + x63 + x77 + x78
   + x80 + x81 + x86 >= 0
 c32: x15 + x24 + x27 + x28 + x29 + x30 + x31 + x52 + x53 + x56 + x63 + x77
   + x78 + x80 + x81 + x86 >= 1
 c33: x26 + x42 + x43 + x44 + x45 + x46 + x67 + x70 >= 1
 c34: x16 + x26 + x42 + x43 + x44 + x45 + x46 + x67 + x70 >= 1
 c35: x23 + x25 + x32 + x33 + x37 + x38 + x39 + x40 + x41 + x57 + x58 + x59
   + x60 + x61 + x72 + x73 + x74 + x75 + x76 + x82 >= 1
 c36: x17 + x23 + x25 + x32 + x33 + x37 + x38 + x39 + x40 + x41 + x57 + x58
   + x59 + x60 + x61 + x72 + x73 + x74 + x75 + x76 + x82 >= 1
 c37: x22 + x27 + x28 + x29 + x30 + x31 + x53 + x62 + x63 + x65 + x68 + x77
   + x78 + x80 + x86 >= 1
 c38: x18 + x22 + x27 + x28 + x29 + x30 + x31 + x53 + x62 + x63 + x65 + x68
   + x77 + x78 + x80 + x86 >= 1
 c39: x26 + x42 + x43 + x44 + x45 + x46 + x85 >= 1
 c40: x19 + x26 + x42 + x43 + x44 + x45 + x46 + x85 >= 1
 c41: x24 + x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 + x40 + x41 + x67
   + x70 + x72 + x73 + x74 + x75 + x76 + x82 >= 1
 c42: x20 + x24 + x32 + x33 + x34 + x35 + x36 + x37 + x38 + x39 + x40 + x41
   + x67 + x70 + x72 + x73 + x74 + x75 + x76 + x82 >= 1
 c43: x22 + x23 + x25 + x28 + x30 + x53 + x57 + x58 + x59 + x60 + x61 + x62
   + x63 + x65 + x68 + x77 + x78 + x80 + x86 >= 1
 c44: x21 + x22 + x23 + x25 + x28 + x30 + x53 + x57 + x58 + x59 + x60 + x61
   + x62 + x63 + x65 + x68 + x77 + x78 + x80 + x86 >= 1
 c45: x22 + x27 + x32 + x37 + x42 + x47 + x52 + x57 + x62 + x67 + x72 + x77
   = 1
 c46: x23 + x28 + x33 + x38 + x43 + x48 + x53 + x58 + x63 + x68 + x73 + x78
   + x82 = 1
 c47: x24 + x29 + x34 + x39 + x44 + x49 + x54 + x59 + x64 + x69 + x74 + x79
   + x83 = 1
 c48: x25 + x30 + x35 + x40 + x45 + x50 + x55 + x60 + x65 + x70 + x75 + x80
   = 1
 c49: x26 + x31 + x36 + x41 + x46 + x51 + x56 + x61 + x76 + x81 + x84 + x85
   + x86 + x66 + x71 = 1
Bounds
End

Our question is: Is there something wrong with these dual variables, and how can we address it? We suspect that this discrepancy might be the reason why our CG failed to terminate. Any assistance would be greatly appreciated.

best wishes,

wanzhe