An optimization problem minimizes ! i fi(zj ) subject to constraint sets C1,..., Cm. Each constraint set uses its own variables, except for a few variables that occur in more than one constraint set....

An optimization problem minimizes !

i fi(zj ) subject to constraint

sets C1,..., Cm. Each constraint set uses its own variables, except for a few

variables that occur in more than one constraint set. Specifically, for each

pair k, (k<),>∈ Jk

in common. Also each zi occurs only in Ci. Show how Lagrangean relaxation

might take advantage of this structure to obtain a lower bound on the optimal

value.