sci.op-research

I am trying to understand how to find the optimal Lagrangian multipliers
for a Lagrangian relaxation of an integer program.

I am reading an example with the below integer program:

(IP)
z = max 7x1 + 2x2
s.t -x1 + 2x2 <= 4
5x1 + x2 <= 20
-2x1 - 2x2 <= -7
-x1 <= -2
x2 <= 4
x1,x2 integer

The optimal solution for (IP) is: (x1,x2) = (4,0) with the value z* = 28.



A Lagrangian relaxation of the first constraint for u >= 0 leads to the
following model (which is an upper bound for (IP)):

(IP(u))
z(u) = max (7+u)x1 + (2-2u)x2 + 4u
s.t 5x1 + x2 <= 20
-2x1 - 2x2 <= -7
-x1 <= -2
x2 <= 4
x1,x2 integer


Where the objective function is rewritten from:

7x1 + 2x2 - u(-x1 + 2x2 - 4)


I would now like to find the best (smallest) upper bound. This means to
find the optimal Lagrangian multipliers 'u'.

In the example they find that u = 1/9 gives the tightest bound for
(x1,x2)=(3,4) with a value 28.88.

But what method is used to find u = 1/9 and why are the solution
(x1,x2)=(3,4) used?


I have read (Wolsey: Integer Programming) that to find the optimal
values for 'u' one must solve the Lagrangian dual problem:

(LD)

w_LD = min{z(u) : u >=0}

But I don't see how that is applied to the above example.