[Dip] Extreme rays and artificial column bounds

[Matthew Galati]

Hi Kim,

I'll take a look soon.

Adding extreme rays is on my ToDo list - which would fix any issue with unbounded subproblems and would remove the need for the artificial column bounds.

You are correct that the large column bounds could be causing numerical issues. It is also possible that this is a bug in CBC (when seeing status=7). I have seen this before and submitted tickets.

I'll investigate and get back to you.

Thanks,
Matt


> -----Original Message-----
> From: dip-bounces at list.coin-or.org [mailto:dip-bounces at list.coin-
> or.org] On Behalf Of kim
> Sent: Thursday, October 07, 2010 4:37 AM
> To: dip at list.coin-or.org
> Subject: [Dip] Extreme rays and artificial column bounds
> 
> 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
> 
> _______________________________________________
> Dip mailing list
> Dip at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/dip