[Dip] Extreme rays and artificial column bounds

[Matthew Galati]

>
> 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.
>


Please update to DIP trunk. There have been several changes and bug fixes
since v0.8.2.







> 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.
>


It looks to me like your subproblems should all be bounded. Is this error
coming from a subproblem or from perhaps solving the IP as master? You are
also using a very old version of DIP (and probably CBC) - so please upgrade
and try again.

With trunk and with no artificial bounds, it does fail to solve Looking at
the master problem, I can see why. The variables with no upper bound
(master-only vars) do wind up entering the master problem with coefficients
= infinity and CBC aborts because of numerical issues. I need to add extreme
rays. It is on my ToDo list - see ticket:
https://projects.coin-or.org/Dip/ticket/54

I will try to work on this soon-ish. In the meantime - using ColumnLB/UB
options in MILPBlock should work.










>
> If I use artificial column bounds as suggested I instead get (what I'm
> guessing is) precision problems from the large magnitude bounds:
>
> 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")
>


Using trunk, this seems to solve fine - although I do get some warnings
about slight row violations (I'll look into that). Trying upgrading.

Thanks,
Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/dip/attachments/20101007/92d43471/attachment.html