[BCP] Dual ray is wrong!

[Laszlo Ladanyi]

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