Problem with 2 representations of a formulation
AnsweredHello,
I have two representations of the same formulation, but the solution and objective value that I get from solving the two problems are different. This does not quite make sense to me why this is the case. Could you kindly please advise?
Model 1: Bounds of all variables are >= 0
\ LP format - for model browsing. Use MPS format to capture full model detail.
Maximize
r
Subject To
R0: 800 y[0] + 650 y[1] + 550 y[2] + 550 y[3] + 650 y[4] + y[5] + y[6]
+ y[7] + y[8] + y[9] + y[10] + y[11] + y[12] + y[13] + y[14] + y[15]
+ y[16] + y[17] + y[18] + y[19] + y[20] + y[21] + y[22] + y[23] + y[24]
+ y[25] + y[26] + y[27] + y[28] + y[29] + y[30] + y[31] + y[32] + y[33]
+ y[34] + y[35] + y[36] + y[37] + y[38] + y[39] + y[40] + y[41] + y[42]
+ y[43] + y[44] + y[45] + y[46] + y[47] + y[48] + y[49] + y[50] + y[51]
+ y[52] + y[53] + y[54] + 16524 z <= 16537
constraint[0]: r - 40 y[0] - 16 y[1] - 38 y[2] - 8 y[3] - 38 y[4] - y[5]
- 560 z <= -560
constraint[1]: - 91 y[0] - 92 y[1] - 39 y[2] - 71 y[3] - 52 y[4] - y[6]
- 1125 z <= -1125
constraint[2]: - 10 y[0] - 41 y[1] - 32 y[2] - 30 y[3] - 30 y[4] - y[7]
- 300 z <= -300
constraint[3]: - 30 y[0] - 16 y[1] - 71 y[2] - 60 y[3] - 42 y[4] - y[8]
- 620 z <= -620
constraint[4]: - 160 y[0] - 150 y[1] - 80 y[2] - 200 y[3] - 170 y[4]
- y[9] - 2100 z <= -2100
constraint[5]: - 20 y[0] - 23 y[1] - 26 y[2] - 18 y[3] - 9 y[4] - y[10]
- 431 z <= -431
constraint[6]: - 3 y[0] - 4 y[1] - 5 y[2] - 6 y[3] - 7 y[4] - y[11] - 68 z
<= -68
constraint[7]: - 12 y[0] - 18 y[1] - 40 y[2] - 30 y[3] - 20 y[4] - y[12]
- 328 z <= -328
constraint[8]: - 3 y[0] - 6 y[1] - 8 y[2] - 4 y[3] - y[13] - 47 z <= -47
constraint[9]: - 18 y[0] - 12 y[2] - 8 y[3] - 3 y[4] - y[14] - 122 z
<= -122
constraint[10]: - 9 y[0] - 12 y[1] - 30 y[2] - 31 y[3] - 21 y[4] - y[15]
- 322 z <= -322
constraint[11]: - 25 y[0] - 8 y[1] - 15 y[2] - 6 y[3] - 4 y[4] - y[16]
- 196 z <= -196
constraint[12]: - y[0] - 2 y[1] - 3 y[3] - y[4] - y[17] - 41 z <= -41
constraint[13]: - y[0] - y[1] - y[2] - 2 y[4] - y[18] - 25 z <= -25
constraint[14]: - 10 y[0] - 23 y[2] - 18 y[3] - 14 y[4] - y[19] - 425 z
<= -425
constraint[15]: - 280 y[0] - 200 y[1] - 100 y[2] - 60 y[3] - 310 y[4]
- y[20] - 4260 z <= -4260
constraint[16]: - 10 y[0] - 20 y[1] - 21 y[3] - 8 y[4] - y[21] - 416 z
<= -416
constraint[17]: - 8 y[0] - 6 y[1] - 20 y[2] - 4 y[3] - 4 y[4] - y[22]
- 115 z <= -115
constraint[18]: - y[0] - 2 y[1] - 3 y[2] - 6 y[4] - y[23] - 82 z <= -82
constraint[19]: - y[0] - y[1] - 2 y[3] - y[4] - y[24] - 22 z <= -22
constraint[20]: - 49 y[0] - 70 y[1] - 40 y[2] - 32 y[3] - 18 y[4] - y[25]
- 631 z <= -631
constraint[21]: - 8 y[0] - 9 y[1] - 6 y[2] - 15 y[3] - 15 y[4] - y[26]
- 132 z <= -132
constraint[22]: - 21 y[0] - 22 y[1] - 8 y[2] - 31 y[3] - 38 y[4] - y[27]
- 420 z <= -420
constraint[23]: - 6 y[0] - 4 y[1] - 2 y[3] - 10 y[4] - y[28] - 86 z
<= -86
constraint[24]: - y[0] - y[1] - 6 y[2] - 2 y[3] - 4 y[4] - y[29] - 42 z
<= -42
constraint[25]: - 5 y[0] - 5 y[1] - 4 y[2] - 7 y[3] - 8 y[4] - y[30]
- 103 z <= -103
constraint[26]: - 10 y[0] - 10 y[1] - 22 y[2] - 8 y[3] - 6 y[4] - y[31]
- 215 z <= -215
constraint[27]: - 8 y[0] - 6 y[1] - 4 y[2] - 2 y[3] - y[32] - 81 z <= -81
constraint[28]: - 2 y[0] - 4 y[1] - 6 y[2] - 8 y[3] - y[33] - 91 z <= -91
constraint[29]: - y[0] - y[2] - 3 y[4] - y[34] - 26 z <= -26
constraint[30]: - 4 y[1] - 5 y[2] - 2 y[3] - y[35] - 49 z <= -49
constraint[31]: - 10 y[0] - 12 y[1] - 14 y[2] - 8 y[3] - 10 y[4] - y[36]
- 420 z <= -420
constraint[32]: - 42 y[0] - 8 y[1] - 8 y[2] - 6 y[3] - 6 y[4] - y[37]
- 316 z <= -316
constraint[33]: - 6 y[0] - 4 y[1] - 2 y[2] - 7 y[3] - y[4] - y[38] - 72 z
<= -72
constraint[34]: - 4 y[0] - 3 y[1] - 8 y[2] - y[3] - 3 y[4] - y[39] - 71 z
<= -71
constraint[35]: - 8 y[0] - y[40] - 49 z <= -49
constraint[36]: - 10 y[1] - 20 y[2] - 3 y[4] - y[41] - 108 z <= -108
constraint[37]: - 10 y[0] - 20 y[3] - 5 y[4] - y[42] - 116 z <= -116
constraint[38]: - y[0] - 6 y[1] - 8 y[3] - 4 y[4] - y[43] - 90 z <= -90
constraint[39]: - 40 y[0] - 28 y[1] - 6 y[2] - 14 y[3] - y[44] - 738 z
<= -738
constraint[40]: - 86 y[0] - 93 y[1] - 12 y[2] - 20 y[3] - 30 y[4] - y[45]
- 1811 z <= -1811
constraint[41]: - 11 y[0] - 9 y[1] - 6 y[2] - 2 y[3] - 12 y[4] - y[46]
- 430 z <= -430
constraint[42]: - 120 y[0] - 30 y[1] - 80 y[2] - 40 y[3] - 16 y[4] - y[47]
- 3060 z <= -3060
constraint[43]: - 8 y[0] - 22 y[1] - 13 y[2] - 6 y[3] - 18 y[4] - y[48]
- 215 z <= -215
constraint[44]: - 3 y[0] - 6 y[2] - y[3] - 3 y[4] - y[49] - 58 z <= -58
constraint[45]: - 32 y[0] - 36 y[1] - 22 y[2] - 14 y[3] - 16 y[4] - y[50]
- 296 z <= -296
constraint[46]: - 28 y[0] - 45 y[1] - 14 y[2] - 20 y[3] - 22 y[4] - y[51]
- 620 z <= -620
constraint[47]: - 13 y[0] - 13 y[1] - 12 y[3] - 30 y[4] - y[52] - 418 z
<= -418
constraint[48]: - 2 y[0] - 2 y[1] - y[2] - 4 y[4] - y[53] - 47 z <= -47
constraint[49]: - 4 y[0] - 2 y[1] - 2 y[2] - y[3] - y[54] - 81 z <= -81
Bounds
End
Model 2:
\ LP format - for model browsing. Use MPS format to capture full model detail.
Maximize
r
Subject To
R0: 800 y[0] + 650 y[1] + 550 y[2] + 550 y[3] + 650 y[4] + y[5] + y[6]
+ y[7] + y[8] + y[9] + y[10] + y[11] + y[12] + y[13] + y[14] + y[15]
+ y[16] + y[17] + y[18] + y[19] + y[20] + y[21] + y[22] + y[23] + y[24]
+ y[25] + y[26] + y[27] + y[28] + y[29] + y[30] + y[31] + y[32] + y[33]
+ y[34] + y[35] + y[36] + y[37] + y[38] + y[39] + y[40] + y[41] + y[42]
+ y[43] + y[44] + y[45] + y[46] + y[47] + y[48] + y[49] + y[50] + y[51]
+ y[52] + y[53] + y[54] + 16524 z[0] + 16524 z[1] + 16524 z[2] <= 16537
constraint[0]: r - 40 y[0] - 16 y[1] - 38 y[2] - 8 y[3] - 38 y[4] - y[5]
+ 1e+34 z[0] - 573 z[1] - 560 z[2] <= -560
constraint[1]: - 91 y[0] - 92 y[1] - 39 y[2] - 71 y[3] - 52 y[4] - y[6]
- 1125 z[0] - 1125 z[1] - 1125 z[2] <= -1125
constraint[2]: - 10 y[0] - 41 y[1] - 32 y[2] - 30 y[3] - 30 y[4] - y[7]
- 300 z[0] - 300 z[1] - 300 z[2] <= -300
constraint[3]: - 30 y[0] - 16 y[1] - 71 y[2] - 60 y[3] - 42 y[4] - y[8]
- 620 z[0] - 620 z[1] - 620 z[2] <= -620
constraint[4]: - 160 y[0] - 150 y[1] - 80 y[2] - 200 y[3] - 170 y[4]
- y[9] - 2100 z[0] - 2100 z[1] - 2100 z[2] <= -2100
constraint[5]: - 20 y[0] - 23 y[1] - 26 y[2] - 18 y[3] - 9 y[4] - y[10]
- 431 z[0] - 431 z[1] - 431 z[2] <= -431
constraint[6]: - 3 y[0] - 4 y[1] - 5 y[2] - 6 y[3] - 7 y[4] - y[11]
- 68 z[0] - 68 z[1] - 68 z[2] <= -68
constraint[7]: - 12 y[0] - 18 y[1] - 40 y[2] - 30 y[3] - 20 y[4] - y[12]
- 328 z[0] - 328 z[1] - 328 z[2] <= -328
constraint[8]: - 3 y[0] - 6 y[1] - 8 y[2] - 4 y[3] - y[13] - 47 z[0]
- 47 z[1] - 47 z[2] <= -47
constraint[9]: - 18 y[0] - 12 y[2] - 8 y[3] - 3 y[4] - y[14] - 122 z[0]
- 122 z[1] - 122 z[2] <= -122
constraint[10]: - 9 y[0] - 12 y[1] - 30 y[2] - 31 y[3] - 21 y[4] - y[15]
- 322 z[0] - 322 z[1] - 322 z[2] <= -322
constraint[11]: - 25 y[0] - 8 y[1] - 15 y[2] - 6 y[3] - 4 y[4] - y[16]
- 196 z[0] - 196 z[1] - 196 z[2] <= -196
constraint[12]: - y[0] - 2 y[1] - 3 y[3] - y[4] - y[17] - 41 z[0]
- 41 z[1] - 41 z[2] <= -41
constraint[13]: - y[0] - y[1] - y[2] - 2 y[4] - y[18] - 25 z[0] - 25 z[1]
- 25 z[2] <= -25
constraint[14]: - 10 y[0] - 23 y[2] - 18 y[3] - 14 y[4] - y[19] - 425 z[0]
- 425 z[1] - 425 z[2] <= -425
constraint[15]: - 280 y[0] - 200 y[1] - 100 y[2] - 60 y[3] - 310 y[4]
- y[20] - 4260 z[0] - 4260 z[1] - 4260 z[2] <= -4260
constraint[16]: - 10 y[0] - 20 y[1] - 21 y[3] - 8 y[4] - y[21] - 416 z[0]
- 416 z[1] - 416 z[2] <= -416
constraint[17]: - 8 y[0] - 6 y[1] - 20 y[2] - 4 y[3] - 4 y[4] - y[22]
- 115 z[0] - 115 z[1] - 115 z[2] <= -115
constraint[18]: - y[0] - 2 y[1] - 3 y[2] - 6 y[4] - y[23] - 82 z[0]
- 82 z[1] - 82 z[2] <= -82
constraint[19]: - y[0] - y[1] - 2 y[3] - y[4] - y[24] - 22 z[0] - 22 z[1]
- 22 z[2] <= -22
constraint[20]: - 49 y[0] - 70 y[1] - 40 y[2] - 32 y[3] - 18 y[4] - y[25]
- 631 z[0] - 631 z[1] - 631 z[2] <= -631
constraint[21]: - 8 y[0] - 9 y[1] - 6 y[2] - 15 y[3] - 15 y[4] - y[26]
- 132 z[0] - 132 z[1] - 132 z[2] <= -132
constraint[22]: - 21 y[0] - 22 y[1] - 8 y[2] - 31 y[3] - 38 y[4] - y[27]
- 420 z[0] - 420 z[1] - 420 z[2] <= -420
constraint[23]: - 6 y[0] - 4 y[1] - 2 y[3] - 10 y[4] - y[28] - 86 z[0]
- 86 z[1] - 86 z[2] <= -86
constraint[24]: - y[0] - y[1] - 6 y[2] - 2 y[3] - 4 y[4] - y[29] - 42 z[0]
- 42 z[1] - 42 z[2] <= -42
constraint[25]: - 5 y[0] - 5 y[1] - 4 y[2] - 7 y[3] - 8 y[4] - y[30]
- 103 z[0] - 103 z[1] - 103 z[2] <= -103
constraint[26]: - 10 y[0] - 10 y[1] - 22 y[2] - 8 y[3] - 6 y[4] - y[31]
- 215 z[0] - 215 z[1] - 215 z[2] <= -215
constraint[27]: - 8 y[0] - 6 y[1] - 4 y[2] - 2 y[3] - y[32] - 81 z[0]
- 81 z[1] - 81 z[2] <= -81
constraint[28]: - 2 y[0] - 4 y[1] - 6 y[2] - 8 y[3] - y[33] - 91 z[0]
- 91 z[1] - 91 z[2] <= -91
constraint[29]: - y[0] - y[2] - 3 y[4] - y[34] - 26 z[0] - 26 z[1]
- 26 z[2] <= -26
constraint[30]: - 4 y[1] - 5 y[2] - 2 y[3] - y[35] - 49 z[0] - 49 z[1]
- 49 z[2] <= -49
constraint[31]: - 10 y[0] - 12 y[1] - 14 y[2] - 8 y[3] - 10 y[4] - y[36]
- 420 z[0] - 420 z[1] - 420 z[2] <= -420
constraint[32]: - 42 y[0] - 8 y[1] - 8 y[2] - 6 y[3] - 6 y[4] - y[37]
- 316 z[0] - 316 z[1] - 316 z[2] <= -316
constraint[33]: - 6 y[0] - 4 y[1] - 2 y[2] - 7 y[3] - y[4] - y[38]
- 72 z[0] - 72 z[1] - 72 z[2] <= -72
constraint[34]: - 4 y[0] - 3 y[1] - 8 y[2] - y[3] - 3 y[4] - y[39]
- 71 z[0] - 71 z[1] - 71 z[2] <= -71
constraint[35]: - 8 y[0] - y[40] - 49 z[0] - 49 z[1] - 49 z[2] <= -49
constraint[36]: - 10 y[1] - 20 y[2] - 3 y[4] - y[41] - 108 z[0] - 108 z[1]
- 108 z[2] <= -108
constraint[37]: - 10 y[0] - 20 y[3] - 5 y[4] - y[42] - 116 z[0] - 116 z[1]
- 116 z[2] <= -116
constraint[38]: - y[0] - 6 y[1] - 8 y[3] - 4 y[4] - y[43] - 90 z[0]
- 90 z[1] - 90 z[2] <= -90
constraint[39]: - 40 y[0] - 28 y[1] - 6 y[2] - 14 y[3] - y[44] - 738 z[0]
- 738 z[1] - 738 z[2] <= -738
constraint[40]: - 86 y[0] - 93 y[1] - 12 y[2] - 20 y[3] - 30 y[4] - y[45]
- 1811 z[0] - 1811 z[1] - 1811 z[2] <= -1811
constraint[41]: - 11 y[0] - 9 y[1] - 6 y[2] - 2 y[3] - 12 y[4] - y[46]
- 430 z[0] - 430 z[1] - 430 z[2] <= -430
constraint[42]: - 120 y[0] - 30 y[1] - 80 y[2] - 40 y[3] - 16 y[4] - y[47]
- 3060 z[0] - 3060 z[1] - 3060 z[2] <= -3060
constraint[43]: - 8 y[0] - 22 y[1] - 13 y[2] - 6 y[3] - 18 y[4] - y[48]
- 215 z[0] - 215 z[1] - 215 z[2] <= -215
constraint[44]: - 3 y[0] - 6 y[2] - y[3] - 3 y[4] - y[49] - 58 z[0]
- 58 z[1] - 58 z[2] <= -58
constraint[45]: - 32 y[0] - 36 y[1] - 22 y[2] - 14 y[3] - 16 y[4] - y[50]
- 296 z[0] - 296 z[1] - 296 z[2] <= -296
constraint[46]: - 28 y[0] - 45 y[1] - 14 y[2] - 20 y[3] - 22 y[4] - y[51]
- 620 z[0] - 620 z[1] - 620 z[2] <= -620
constraint[47]: - 13 y[0] - 13 y[1] - 12 y[3] - 30 y[4] - y[52] - 418 z[0]
- 418 z[1] - 418 z[2] <= -418
constraint[48]: - 2 y[0] - 2 y[1] - y[2] - 4 y[4] - y[53] - 47 z[0]
- 47 z[1] - 47 z[2] <= -47
constraint[49]: - 4 y[0] - 2 y[1] - 2 y[2] - y[3] - y[54] - 81 z[0]
- 81 z[1] - 81 z[2] <= -81
R51: z[0] = 0
R52: z[1] = 0
Bounds
End
Observe that in the second model, functionally we have z[0] = 0 , z[1] = 0, which makes the only valid z variable as z[2]. We can then drop all z[0], z[1] variables, returning the same model as model 1.
Unfortunately, even in this instance, I get that the two problems return a solution of 13 for model 1 and 0 for model 2 respectively, which should not be the case.
Is there any reason to why this is so?
-
Both models, as you posted them, result in the same optimal objective value of 13. I tested with Gurobi Version 12.0.0.
If I change the objective sense to "Minimize", the optimal objective value is 0. Maybe the "maximize" got lost in your test.
Can you please check again and share more information if you see a difference?0 -
Hi Marika,
Thank you for the prompt reply,
it turns out that it was some numerical issue - It seems the moment I changed the coefficient of z[0] to a smaller number, the two models do coincide.
Is there something about numerical issues that we have to take note of as users?
Best
Jerry0 -
Hi Jerry,
Indeed, coefficients of 1e+34 are a bad idea.
Gurobi also prints a warning in the log, which is discussed in the KB article What does "Model contains large matrix coefficient range" mean?Best,
Marika0
Please sign in to leave a comment.
Comments
3 comments