[Dip] Extreme rays and artificial column bounds

[kim]

Hi:

I am working with DIP (v0.8.2) and the MILPBlock example to test some 
ideas for automatic block detection and selection. But I have run into 
some problems. From previous messages on the mailing list I get the 
impression that my problems are caused by unboundedness.

The problem can be illustrated with the unmodified MILPBlock example and 
the "atm_5_10_1" instance. If using the block file "atm_5_10_1.block" 
that comes with the example there is no problem. If instead another 
decomposition is chosen with the following block file, the problem arises:
"0 30
1 31
2 82
3 83
4 134
5 135
6 186
7 187
8 238
9 239"
(If using this remember to switch to pair format).
This decomposition relaxes the 10 column-disjoint knapsack constraint 
into 10 pricing problems. This results in the previously reported 
"Error: CBC IP solver 2nd status = 7" error.

If I use artificial column bounds as suggested I instead get (what I'm 
guessing is) precision problems from the large magnitude bounds:

"Point violates row 120 -> demand_def(a_ATM2,d_DATE5) LB= 29.0000000 ax= 
29.2059676 UB= 29.0000000 RelViol= 0.0070522
Point violates row 160 -> demand_def(a_ATM3,d_DATE0) LB= -178.0000000 
ax= -176.8442173 UB= -178.0000000 RelViol= 0.0065356
Point violates row 120 -> demand_def(a_ATM2,d_DATE5) LB= 29.0000000 ax= 
29.4423158 UB= 29.0000000 RelViol= 0.0150231
Point violates row 160 -> demand_def(a_ATM3,d_DATE0) LB= -178.0000000 
ax= -176.4056701 UB= -178.0000000 RelViol= 0.0090379
Point violates row 120 -> demand_def(a_ATM2,d_DATE5) LB= 29.0000000 ax= 
29.3569114 UB= 29.0000000 RelViol= 0.0121577
Point violates row 160 -> demand_def(a_ATM3,d_DATE0) LB= -178.0000000 
ax= -176.7198539 UB= -178.0000000 RelViol= 0.0072439
Point violates row 160 -> demand_def(a_ATM3,d_DATE0) LB= -178.0000000 
ax= -176.7286013 UB= -178.0000000 RelViol= 0.0071941
Point violates row 120 -> demand_def(a_ATM2,d_DATE5) LB= 29.0000000 ax= 
29.2266550 UB= 29.0000000 RelViol= 0.0077551
Point violates row 120 -> demand_def(a_ATM2,d_DATE5) LB= 29.0000000 ax= 
29.3663645 UB= 29.0000000 RelViol= 0.0124757
MasterObj [primal] = 100635
MasterObj [dual]   = 100636
COIN Exception [ Primal and Dual Master Obj Not Matching. ] at 
../../../Dip/src/DecompAlgo.cpp:L2612 in DecompAlgo::checkBlocksColumns"
(the above was obtained with the bounds "ColumnLB = -1.0" and "ColumnUB 
= 3500")

I am unsure how to proceed from here or even if this is indeed a problem 
with unboundedness as it seems. The problem pops up quite often when 
relaxing knapsack constraints, but not always. For some instances the 
artificial column bounds help, but often I get the precision issues 
described. I'm not terribly familiar with the inner workings of DIP so I 
don't know how difficult it would be to implement handling of extreme rays.

- Kim Vejlin
Student at University of Copenhagen