[BCP] Dual ray is wrong!

Fri Apr 17 18:59:22 EDT 2009

On Fri, 17 Apr 2009, Dani wrote:

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

Yes, that's exactly the problem.

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

That is entirely possible for the same reason.

Let me defend Osi's (and Bcp) interpretation.

Suppose the upper bounds are set so that no out of basis var will ever 
be at upper bound. Then every dual value corresponding to an upper 
bound constraint is 0 so getting the duals of the constraints is fine 
as the dual ray.

Now suppose the upper bounds are tighter and the true dual ray 
contains a nonzero corresponding to a bound. Now what's the use of 
such a dual ray? I believe nothing whatsoever... at least not for the 
purpose of column generation (which, I think, is the main use of dual 
solutions and rays). The reason is that in column generation the duals 
are used in the objective of the subproblem, and if the bound 
constraint of a specific column is non-zero how can that be 
incorporated into the subproblem's objective? I have thought a lot 
about this, but couldn't come up with any solution that is not the 
kind where you want to find the second (third, etc) best solution for 
a subproblem, which is definitely BAD... I would be very interested in 
ideas. Anyway, if we can't incorporate those duals into the objective 
then we better ensure that they are 0 (e.g., by specifying high upper 
bounds), which in turn means that Osi's interpretation is OK.

So... It's true that the dual ray that Osi returns is no necessarily a 
dual ray. However, for column generation purposes it is the right 
thing to use (after it is ensured that everything else will be 0). And 
if someone needs the full dual ray for other purposes then it is easy 
enough to extract the rest from the reduced costs.

--Laci

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