sci.op-research

Ray Vickson skrev:
> On Feb 12, 2:39 am, saneman wrote:
>> Given the following IP problem:
>>
>> (IP)
>> z = max cx
>> Dx <= d
>> x \in Z+
>>
>> the lagrangian relaxation for u > 0 is:
>>
>> (IP(u))
>>
>> z(u) = max cx + u(d-Dx)
>> x \in Z+
>>
>> In (IP(u)) 'u' is called the Lagrange multiplier or the dual variable
>> associated with the constraint: Dx <= d.
>
> It is called the dual variable, but that is just a more-or-less
> inaccurate name. There really are no duals for most IP problems, at
> least, not so that standard primal/dual relationships must hold. IP
> generally has a so-called 'duality gap', which means that we cannot
> always guarantee getting the optimal solution by optimizing the dual.
> (There are schemes such as Benders decomposition that mix duality and
> cut generation, which do, theoretically, guarantee optimality in
> finitely many steps.)
>
>> But how can a coefficient in the objective function be a dual variable?
>>
>> Comparing (IP(u)) with the below example '4' would be the dual variable
>> associated with constraint 2:
>>
>> max z = 2x1 + 4x2
>> st. 3x1 + x2 <= 1 (y1)
>> x1 + 7x2 <= 3 (y2)
>
> I don't understand what you mean by '4'. Is it the number 'four'? The
> only '4' I see is the objective coefficient of x2, so I have no idea
> where your supposed '4' comes from. When the problem is solved, both
> dual variables come out as 1/2, so that can't even be where the '4'
> comes from.

In (IP(u)) 'u' is the coefficient in front of '(d-Dx)'. Compared to the
above example '4' is the coefficient in front of 'x2'. In the book they
say that 'u' is a dual variable associated with constraint 2 and
therefore I conclude that '4' is a dual variable.

But as I have learned y2 is the dual variable corresponding to constraint 2.