[BCP] Dual ray is wrong!

[Dani]

I was having the same problem.  I'm very grateful too for your anwser,
Laszlo (to Mohamad too for raising the question!). I was not able to fix my
code yet but at least I have some hints :-)

If I understood it well, the problem comes from adding "bound" constraints
(0 <= x_i <= 1)  since eventually one of those became non-basic and bounded
to 1 with a non-negative dual and Bcp (Osi?) was not returning it in the
dual price vector because it concerned the upper bound? Is my understanding
good?

To complement this thread just say that the behavior I was observing was
that cplex command line and glpsol (glpk's counterpart) were returning
non-zero duals whereas Bcp (Osi?) was returning 0.

Thanks,

Dani.

On Fri, Apr 17, 2009 at 10:35 PM, mohamad reisi
<mohamad.reisi at in.iut.ac.ir>wrote:

> Dear Laci,
>
> You are right. I have set the upper bound of variables to DBL_MAX, then
> this problem solved. Nw it is ok.
> Thanks a lot.
>
> Mohamad.
> ----- Original Message -----
> From: Laszlo Ladanyi <ladanyi at us.ibm.com>
> To: mohamad reisi <mohamad.reisi at in.iut.ac.ir>
> Cc: bcp at list.coin-or.org
> Sent: Fri, 17 Apr 2009 23:15:57 +0330 (IRST)
> Subject: Re: [BCP] Dual ray is wrong!
>
> Hi Mohamad,
>
> Then I'm almost sure that my explanation below is the correct one.
> Check if you have any variables out of basis at their upper bound. Add
> together their reduced costs and see if that is the difference.
>
> --Laci
>
> On Fri, 17 Apr 2009, mohamad reisi wrote:
>
> > Dear Laci,
> >
> > I am using binary variables. The problem is that sum of the all dual
> > value must be equal to primal objecctive solution in optimality. But
> > in my case, these values are not equal, and somtimes have a large
> > difference.
> >
> > Mohamad.
> >
> > ----- Original Message -----
> > From: Laszlo Ladanyi <ladanyi at us.ibm.com>
> > To: mohamad reisi <mohamad.reisi at in.iut.ac.ir>
> > Cc: bcp at list.coin-or.org
> > Sent: Fri, 17 Apr 2009 23:06:30 +0330 (IRST)
> > Subject: Re: [BCP] Dual ray is wrong!
> >
> > Hi Mohamad,
> >
> > Well, I need more information... Wrong in what sense? The negative of
> > what you expected? Or you keep regenerating the same column because
> > the duals do not change?
> >
> > One common mistake in column generation schemes is that the newly
> > generated variables have a non-zero bound that can actually be
> > attained (like 0<=x<=1). If in the optimal solution of an LP
> > relaxation any such variable is out of basis at its upper bound then
> > you may have a nonzero dual value that corresponds to the upper bound
> > constraint (in this case the dual value is the reduced cost of the
> > variable) and this dual value is not in the returned dual ray. Since
> > usually for every generated variable there is a clique constraint that
> > contains that variable the clique constraint will implicitly enforce
> > the upper bound thus it's much better to just say 0<=x.
> >
> > --Laci
> >
> > On Fri, 17 Apr 2009, mohamad reisi wrote:
> >
> >> Dear Laci,
> >>
> >> As you said, I am doing column generation.
> >> I transefered my code to version 1.1.3. it seems that the dual value are
> a little better. But they are wrong yet. It is so strange for me! What can I
> do?
> >>
> >> Mohamad.
> >> ----- Original Message -----
> >> From: Laszlo Ladanyi <ladanyi at us.ibm.com>
> >> To: mohamad reisi <mohamad.reisi at in.iut.ac.ir>
> >> Cc: bcp at list.coin-or.org
> >> Sent: Fri, 17 Apr 2009 16:12:37 +0330 (IRST)
> >> Subject: Re: [BCP] Dual ray is wrong!
> >>
> >> Hi Mohamad,
> >>
> >> The cvs version is rather old... There has been relatively little
> >> change in the interfacesince then, but a fair amount under the hood,
> >> and especially clp/OsiClp has changed a lot. If you could port your
> >> code to version 1.1.3 and let us know if you still experience
> >> problems, that would be great. (Since you get the dual rays, I assume
> >> you are doung column generation. versions 1.2.x still have some column
> >> generation related bugs, that's why I suggested 1.1.3.)
> >>
> >> Thanks,
> >> --Laci
> >>
> >> On Fri, 17 Apr 2009, mohamad reisi wrote:
> >>
> >>> Dear all,
> >>>
> >>> I have developed an example in Bcp-cvs2006 package, nased on AAP
> example.
> >>> But in this example the dual ray and sum of them are wrong. (by using
> clp)
> >>> I want to know that this problem is because of Bcp-CVS package or not?
> >>> I have checked every thing but it seems that my codes are right!
> >>>
> >>> Thanks.
> >>> Mohamad Reisi.
> >>>
> >>> _______________________________________________
> >>> BCP mailing list
> >>> BCP at list.coin-or.org
> >>> http://list.coin-or.org/mailman/listinfo/bcp
> >>>
> >>
> >>
> >>
> >
> >
> >
>
>
> _______________________________________________
> BCP mailing list
> BCP at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/bcp
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/bcp/attachments/20090417/95859e0e/attachment-0001.html