[BCP] Dual ray is wrong!

[Laszlo Ladanyi]

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