[Dip] good news

[Matthew Galati]

The "issue" with this model when using the BCP method is that the variable
x1 is free. Because we do not support extreme rays, we have to make sure
that each "block" is bounded. Even though the variable x1 is not part of any
of the defined blocks, internally, it is treated as a special block called
the 'master-only' block. Like the other blocks, we are trying to generate
extreme points of the polytope defined by that block. For your master-only
block, x1 is free and for certain cost vectors can be unbounded.

The easiest way to ensure each polytope is bounded is to bound all your
variables. You can do this manually in your MPS file, or - I have added an
option to the MILPBlock application which can be used to bound all variables
that have no bounds.

Do an svn update (at ~/coin-Dip/Dip) to get the changes. Then in the
parameter file, add a ColumnLB and ColumnUB as follows:

#############################################################################
Settings for MILPBlock application.
  section=MILPBlock
#############################################################################
[MILPBlock]
# Path to instance data.
DataDir        = .

# {Pair,List}: Block file format. See README.txt.
BlockFileFormat = List

# Name of block file (assumed to be in DataDir).
BlockFile       = test_4_1.block

# Name of MPS file for instance (assumed to be in DataDir).
Instance        = test_4_1

ColumnLB        = -1.0e4
ColumnUB        =  1.0e4


This will add the bounds -1000 <= x1 <= 1000 which should fix the issue
related to unboundeness. And you should then be able to solve the problem
using the Price and Cut algorithm.

Let me know if you have any issues.

In a future release, we will add extreme rays - so that the user does not
have to worry about this.

Thanks,
Matt





Hi Ayse,
>
> Replying to the DIP mailing list since this might be relevant to other
> users - although I think you are the only one so far. :)
>
>
> I am assuming the following happens when solving the subproblem - i.e., one
> of your blocks.
> "Coin0508I Presolve thinks problem is unbounded
> Error: CBC IP solver 2nd status = 7"
>
> This is because the BCP method in DIP does not consider extreme rays.
> Rather it assumes that the feasible region is bounded in all directions. I
> have yet to see any real-world example where extreme rays are needed. It
> should be easy to bound your feasible region by giving lower and/or upper
> bounds to all your variables - even if they are artificially big. Try that
> and see if that helps. In some future release of DIP, I will add extreme
> rays so this can be dealt with more naturally.
>
>
>
> "I am kind of confused why one method does not work and the others do and
> also I am wondering how to decide which method to use, is there any
> documentation that I can read about this?"
>
> There is no real documentation to help a user decide this. In fact, that is
> part of why we wrote DIP - so it is easy to try different methods without
> having to recode anything.
>
> See
>  https://coral.ie.lehigh.edu/~magh/decomp/decomp_INFORMS09.pdf<https://coral.ie.lehigh.edu/%7Emagh/decomp/decomp_INFORMS09.pdf> and
>  http://coral.ie.lehigh.edu/~ted/files/papers/DECOMP04.pdf<http://coral.ie.lehigh.edu/%7Eted/files/papers/DECOMP04.pdf>
> for some background information on the different algorithms. There will be
> much more detail in my thesis - which is due out in one month. I will post
> that when it is complete.
>
> Thanks,
> Matt
>
>
>
> From: Ayse Durukan [mailto:adurukan at mail.uh.edu]
> Sent: Thursday, October 29, 2009 2:08 PM
> To: Matthew Galati
> Subject: Re: RE: good news
>
> Hi Mr. Galati,
> I tried converting the mps files using cplex and it worked. Also manually
> removing the lines before NAME header helps too.
> After converting the files, I kept getting the same error until I start
> playing with the main settings. When I solve it with DIP's CPM method it
> works fine.
> When I solve it with DIP's BCP method it gives following error
> Coin0508I Presolve thinks problem is unbounded
> Error: CBC IP solver 2nd status = 7
> When I set doCut=1 and doDirect=1 it works too.
> I am kind of confused why one method does not work and the others do and
> also I am wondering how to decide which method to use, is there any
> documentation that I can read about this?
> Also, please see the attachment for the problem's mps files and block
> files.
>
> Thank You
> Ayse
>
>
>
>
>
> _______________________________________________
> Dip mailing list
> Dip at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/dip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/dip/attachments/20091029/48428e15/attachment.html