sci.op-research

On Feb 13, 8:07 am, saneman wrote:
> 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.

The coefficient of x is c-uD because you have added u(d-Dx) to cx.

R.G. Vickson

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