sci.op-research

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.

Anyway, you can write a Lagrangian for the problem as
v(y1,y2) = max L = 2x1 + 4x2 + y1(1 - 3x1 - x2) + y2(3 - x1 - 7x2)
(max over x1,x2 >= 0). Then the final solution is obtained from min
v(y1,y2) subject to y1, y2 >= 0. Usually, though, it is more
convenient to use the standard simplex method.

R.G. Vickson

>
> But I don't think that makes sense. Normally y2 is said to be the dual
> variable associated with constraint 2. How can '4' also be the dual
> variable associated with constraint 2?