Dip
Dip copied to clipboard
coin-or
(MILPBlock) "Point violates row" with large relative violation
Issue created by migration from Trac.
Original creator: vejlin
Original creation time: 2010-12-03 06:45:16
I am getting some rather large violations with the unmodified MILPBlock example: "Point violates row 2 -> r(2) LB= 0.0000000 ax= -1017.0750594 UB= INF RelViol= 1017.0750594"
This happened with an unmodified MILPBlock example, the "harp2" instance from miplib and the block file (list format): "0 74 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 106 111"
Constraints 0-71 and 111 are column disjount Special Ordeded Sets (\sum x_i = 1) and constraint 106 is a degenerated 0-1 Knapsack constraint (capacity = 0) covering only a subset of the columns covered by the SOS constraints. I am auto generating my block files so it may not be a very good decomposition, but MILPBlock responds oddly and I cannot figure out why. The knapsack constraint simply fixes some variables to zero, and the remaining SOS constraints should not be that problematic. The problem is bounded, if nothing else then because all variables are binary.
Comment by vejlin created at 2010-12-03 06:48:50
harp2.mps was too large to attach directly. It can be found here: http://kim.hamilton-vejlin.dk/DIPfile/harp2.mps
Comment by @mgalati13 created at 2010-12-05 18:01:12
Looking at the model (use LogDumpModel=2), the coefficients are very big and I suspect the issue is a scaling problem in CLP. It is probably OK to ignore the amount of violation we are seeing. I use relative violation when checking the CLP solution. However, in this case, the RHS is 0, so I use absolute - which, in this case, is not going to work.
I'll change the check to be more liberal, since I don't expect CLP to be that accurate in this case.
: sOG(c_1_r(1)) -1083633040 lam(c_6081,b_0) + 194453760 lam(c_6085,b_0) + 202925650 lam(c_6089,b_0) + 503285650 lam(c_6090,b_0)
- 199510200 lam(c_6094,b_0) + 784740000 lam(c_6095,b_0) + 199510200 lam(c_6096,b_0) + 784740000 lam(c_6097,b_0) + 784740000 lam(c_6098,b_0)
- 989132000 lam(c_6099,b_0) + 989132000 lam(c_6100,b_0) + 989132000 lam(c_6101,b_0) + 989132000 lam(c_6102,b_0) + 989132000 lam(c_6103,b_0)
- 989132000 lam(c_6104,b_0) + 989132000 lam(c_6105,b_0) + 989132000 lam(c_6106,b_0) + 989132000 lam(c_6107,b_0) + 989132000 lam(c_6108,b_0)
- 989132000 lam(c_6109,b_0) + 989132000 lam(c_6110,b_0) + 989132000 lam(c_6111,b_0) + 989132000 lam(c_6112,b_0) + 989132000 lam(c_6113,b_0)
- 989132000 lam(c_6114,b_0) + 989132000 lam(c_6115,b_0) + 989132000 lam(c_6116,b_0) + 989132000 lam(c_6117,b_0) + 989132000 lam(c_6118,b_0)
- 989132000 lam(c_6119,b_0) + 989132000 lam(c_6120,b_0) + 989132000 lam(c_6121,b_0) + 989132000 lam(c_6122,b_0) + 989132000 lam(c_6123,b_0)
- 989132000 lam(c_6124,b_0) + 989132000 lam(c_6125,b_0) + 989132000 lam(c_6126,b_0) + 989132000 lam(c_6127,b_0) + 989132000 lam(c_6128,b_0)
- 300678910 lam(c_6129,b_0) + 989132000 lam(c_6130,b_0) + 989132000 lam(c_6131,b_0) + 989132000 lam(c_6132,b_0) + 989132000 lam(c_6133,b_0)
- 989132000 lam(c_6134,b_0) + 389149000 lam(c_6135,b_0) + 389149000 lam(c_6136,b_0) + 389149000 lam(c_6137,b_0) + 389149000 lam(c_6138,b_0)
- 389149000 lam(c_6139,b_0) + 389149000 lam(c_6140,b_0) + 389149000 lam(c_6141,b_0) + 389149000 lam(c_6142,b_0) + 389149000 lam(c_6143,b_0)
Comment by @mgalati13 created at 2010-12-06 02:35:26
This is now fixed. This case will produce warnings but not fail assertions now.
D-ALGO : 31.7 [CPU: 30.4 ] <--- recomposeSolution() ----- Point violates row 1 -> r(1) LB= 0.0000000 ax= -141.5687225 UB= INF RelViol= 141.5687225 row has a big coefficient -4.87e+07 Point violates row 13 -> r(13) LB= 0.0000000 ax= -2463.6822100 UB= INF RelViol= 2463.6822100 row has a big coefficient -8.38e+07 Point violates row 15 -> r(15) LB= 0.0000000 ax= -0.3283722 UB= INF RelViol= 0.3283722 row has a big coefficient -9.45e+07