Opgave 22
---------

(a)

    maximize 10 y1 + 4 y2 + 14 y3 
    subj. to  3 y1 +   y2 +  4 y3 <= 4                           (1)
                y1,y2,y3 in {0,1}

The lagrangian relaxed problem is (u >= 0)

    maximize 10 y1 + 4 y2 + 14 y3 - u (3 y1 +   y2 +  4 y3 - 4)
    subj. to    y1,y2,y3 in {0,1}

which can be rewritten to

    maximize (10 - 3u) y1 + (4 - u) y2 + (14 - 4u) y3 + 4u       (2)
    subj. to    y1,y2,y3 in {0,1}

As the remaining constraints define the convex hull, the optimal
choice of the lagrangian multiplier u corresponds to the dual 
variable associated with solving (1) to LP-optimality. Thus u = 3.5.

(b) 

We set u0 = 0, mu0 = 1, rho = 0.5

Problem (2) becomes 

    maximize 10 y1 + 4 y2 + 14 y3 
    subj. to    y1,y2,y3 in {0,1}

with optimal solution y1 = y2 = y3 = 1. Now we set

    u1 = max{u0 - mu0(4 - 3 y1 - y2 - 4 y3), 0} 
       = max{0 - 1 (4 - 3 - 1 - 4), 0}
       = max{4, 0} = 4

Problem (2) becomes

    maximize -2 y1 + 0 y2 - 2 y3 + 16
    subj. to    y1,y2,y3 in {0,1}

with optimal solution y1 = y2 = y3 = 0. Now we set

    mu1 = mu0 (rho)^k = 1 * (0.5)^1 = 0.5

    u2 = max{u1 - mu1(4 - 3 y1 - y2 - 4 y3), 0} 
       = max{4 - 0.5 (4 - 0 - 0 - 0), 0}
       = max{2, 0} = 2

Problem (2) becomes

    maximize 4 y1 + 2 y2 + 6 y3 + 8
    subj. to    y1,y2,y3 in {0,1}

with optimal solution y1 = y2 = y3 = 1. Now we set

    mu2 = mu1 (rho)^k = 1 * (0.5)^2 = 0.25

    u3 = max{u2 - mu2(4 - 3 y1 - y2 - 4 y3), 0} 
       = max{4 - 0.25 (4 - 3 - 1 - 4), 0}
       = max{3, 0} = 3

etc.